Zadaci za savezno takmičenje iz informatike, Novi Sad, 6 juni 1992

Nešto raščišćavam, i naiđem na papir star 34+ godine :)

Prvi nije definisao format fajla. Verovatno pretpostavlja neki standard koji se ucio u to vreme u skoli.
U svakom slucaju, ako zanemarimo nacin citanja, pretpostavljam da mozes samo da na pocetku izracunas sumu brojeva od 1 do 1000000 po formuli n(n+1)/2 i onda citajuci brojeve iz fajla samo oduzimas i na kraju ti ostane onaj koji nije u fajlu.
Drugi.. Me mrzi :)

---

Davno je bilo, a ako se dobro secam, bio sam (verovatno pogresno) pretpostavio da nema toliko velike promenjive da drzi taj max zbir, pa sam simulirao to sabiranje/oduzimanje u nizu. Jbg... Ali ideja je bila bas ta koju si naveo.

Moglo je da se radi u Pascalu ili C jeziku. Secam se da sam se mucio da nadjem editor i da kompajliram program na tom PC-ju, jer sam kod kuce radio na Commodore Amiga 500 C kompajlerima (Lattice C i Aztec C).

C ima long long koji je 64bit integer i moze da prihvati taj zbir.
No, kad malo bolje razmislis, i ne moras imati ceo zbir. Mozes sabirati i oduzimati u istom prolasku kroz petlju.


To je naravno sporije (mada u odnosu na citanje iz fajla zanemarljivo) ali mozes da upotrebis ako hoces manji tip.

---

Ne znam odakle mi to za velicinu tipa. Te 1992 godine C standard bio C89, i mislim da nije bilo nista preko 32bit long int. Ali ne mogu da tvrdim.

Well, ako su brojevi u fajlu poredjani u opadajucem redosledu, nece stati u 32 bitni long.

Mozes da napadnes 1..1000000 sa obe strane, i dodas prvi preostali najmanji ili prvi preostali najveci broj, zavisno od result > 500000.

doh.... XOR

Moguce. Ja sam pogledao na wikipediji. Sa C-om nisam nista radio.. Veoma dugo :)

---

Sad sam priupitao ChatGPT-ja... To je ovo sto je scoolptor rekao - XOR!

// netestirano, samo kopirano

U to doba sam dosta radio sa masinskim jezicima, moguce da mi je XOR-ovanje i bilo palo na pamet, ali nisam bas umeo da primenim u ovu svrhu. XOR sam koristio za neke inverzije bitova i graciku prezentaciju trepereceg teksta, tipa PRESS ANY KEY TO CONTINUE...

moze da se optimizuje:

Može i bez XOR-a.

Dovoljno je vršiti sabiranja po modulu 1000000. Naravno, XOR je brži.



Ovde je long iskoriščen da bi se osiguralo da ima bar 32 bita. Tada je int imao 16 bita. U principu je korišćen Turbo Pascal. On je imao LongInt sa 32 bita.

https://turbopascal.org/wp-con...on_7.0_Language_Guide_1992.pdf

---

Evo mnogo manji fajl, ima samo 99999 brojeva u intervalu od 1 do 100000, jedan broj nedostaje naravno, pa da možete da proverite da li vam rade ti programi, jedva ispisah sve e .. fajl je u attachmentu uz poruku ..

---

Huh, ja sam išao na ta takmičenja, i 1992. godine sam bio u srednjoj školi, ali se nešto ne sećam da sam išao u Novi Sad. Čudno. Poznat mi je prvi zadatak, ali drugog se ne sećam. Trenutno nisam niguran ni kako bih ga rešio. Možda za svaku osobu da pratimo u kojim sve gradovima bi mogla da završi u koraku X, ali kako znati kada stati? Da li posle N, ili 2N, ko zna...

Ovaj drugi je baš zeznut.
Recimo, pretpostavimo da imamo 2 grada i dve osobe, ali u različitim gradovima.
Pošto u svakom potezu moraš da pomeriš sve osobe, te dve osobe bi stalno išle u onaj drugi grad, i nikada se ne bi srele u istom gradu.
Slična situacija je i sa 4 grada 1-2-3-4, dve osobe, jedna u 1 jedna u 4, nikada se ne bi srele.

Ovako, na prvi pogled, deluje mi da dve osobe mogu da se sretnu u istom gradu, samo ako je udaljenost izmeću dve osobe paran broj.
Možda?

Uzgred, najkarći put između bilo koja dva grada je trivijalno da se nađe, ali pitanje je da li bi osobe trebale da biraju najkraći put, ili bi bilo potrebno da idu napred-nazad, da bi se srele u istom gradu.

Drugi zadatak je verovatno nešto sa grafovima, dakle teorijsko računarstvo sa primenom na konkretan problem.

Prvi zadatak može na više načina, pitanje je da li postoji ograničenje memorije, ako to nije problem, učista se ceo fajl u memoriju, kreira heš tabela... ali, svakako je brže sa XOR, pošto se radi o INT brojevima, posebno što se verovatno čita linija po linija iz fajla, odnosno broj po broj.

Uopšteno, kad su u pitanju takvi problemi, u obe knjige "Programming Pearls" dati su primeri rešavanja nekih praktičnih problema, jedan od njih je bio da se sortira 27000 brojeva, pri čemu u memoriju može istovremeno da se smesti samo 1000 brojeva. Nekome možda to izgleda kako zezanje iz današnje perspektive, ali taj algoritam je kasnije našao primenu kod Big Data, kao i mnogi drugi.

---

Nije tada bilo ni interneta, uglavnom se kroz casopise saznavalo ko je ko, ali se secam da je Jozef Kratica bio u organizaciji (čuveni autor "nerešivih zadataka"), a secam se da je na takmicenju bio i Ranko Lazić, koji je bio napisao i neku knjigu o programiranju na C jeziku.

Drugi bi bio zeznut da ima samo dva ili tri sata da se reši na takmičenju, ne bi ga ni načeo, a ovako ..

ma kako bili raspoređeni gradovi ako je topologija takva da su bar tri grada raspoređeni "u trougao" na primer a, b, i c, i povezani međusobno, uvek svi mogu da se nađu u istom gradu, jer recimo mogu oni iz a da idu u b, i obrnuto, dok ne pričekaju sve iz svih gradova, i onda u jednom potezu nađu se u gradu c.

Nezgodno je ako bi svi gradovi bili poređani na jednoj liniji, uslov da svaki bude povezan sa susednim je i dalje ispoštovan, mogli bi da se svi sretnu u istom gradu ako između bilo koje dve osobe postoji neparan broj gradova u kome nema niko u tom trenutku (ili udaljenost između dve osobe paran broj, kao kod djoka_I), ako postoji bar jedna situacija da je paran broj gradova u kojima nema niko u tom trenutku između dve osobe - nikad se svi ne sretnu u istom gradu.

I još ako su gradovi poređani u prsten, i svaki povezan sa dva susedna, ako je broj gradova u prstenu paran, isto kao prethodno, mora između bilo koje dve osobe da bude neparan broj praznih gradova da bi uspeli da se nađu svi u istom gradu. Ako je broj gradova u prstenu neparan, onda uvek mogu da se nađu u istom gradu, jer ako ne mogu na jednom kraju prstena, upite se u suprotnim smerovima pa se nađu na onom drugom "kraju" prstena .. ako nisam nešto smandrljao.

I na sve to još najkraće i najracionalnije trase ..

---

Da dam ideju za rešavanje drugog.

1. Odrediti komponente povezanosti grafa. Ako se na početku ne nalaze svi ljudi u istoj komponenti povezanosti, onda se ne mogu sresti. U suprotnom obrisati sve gradove koji se nalaze van komponente povezanosti u kojoj su ljudi na početku, kao i puteve u kojima je bar jedan od krajeva takav grad i preći na sledeći korak.

2. Ako se svi mogu sresti u jednom gradu, onda mogu nakon toga svi zajedno da odu u bilo koji drugi grad. Prema tome, odgovor na pitanje da li se mogu sresti u gradu X ne zavisi od izbora grada X.

Izabrati jedan od gradova (recimo onaj u kome se nalazi pr i čovek) i ispitati udaljenosti svih ljudi od tog grada. Ako su sve udaljenosti iste parnosti, onda je sretanje u tom gradu moguće za onoliko koraka koliko je najudaljeniji čovek udaljen od njega. Recimo, svi idu najkraćim putem u taj grad, pri čemu oni koji stignu ranije od nekog drugog, nakon što su stigli u taj grad najpre pređu iz tog grada u susedni, a potom se vrate i na taj način "čekaju" ostale. U suprotnom (ako ima udaljenosti iste parnosti), preći na sledeći korak.

3. Ako je jedno lice udaljeno paran broj koraka, a drugo lice udaljeno neparan broj koraka, onda da bi se sreli, jedno lice treba da stigne u taj grad putem iste dužine kao drugo lice, odnosno putem čija je dužina različita od parnosti najkraćeg puta. Dakle, ta osoba ima dva puta do tog grada različite parnosti, pa ako bi jednim od ta dva puta otišla u taj grad, a drugim se vratila, napravila bi ciklus neparne dužine. Obrnuto, ako postoji put neparne dužine, onda svaka osoba može otići do grada tog ciklusa, "obrnuti krug" i vratiti se na početno mesto i onda najkraćim putemmotići do grada u kome se svi sreću, čime "koriguje" parnost svog puta, pa je onda sretanje moguće.

Prema tome, treba ispitati da li postoji ciklus neparne dužine i to nam daje odgovor na pitanje da li se mogu sresti u istom gradu.

Ako postoji ciklus neparne dužine koji više od jednom prolazi kroz isti čvor, onda taj ciklus sadrži podciklus. Ako je taj podciklus neparne dužine, onda je on kraći ciklus neparne dužine, a ako je taj podciklus parne dužine, onda njegovim izbacivanjem iz većeg ciklusa dobijamo manji ciklus (od većeg ciklusa) koji je takođe neparne dužine. Najkraći ciklus neparne dužine ne prolazi dva puta kroz isti grad.

Najkraći ciklus neparne dužine nema dužinu manju od 3, niti veću od m=(n-1)/2*2+1 jer je to najveći neparan broj koji nije veći od n. Ako neki grad pripada tom clikusu, on pripada ciklusu dužine ne veće od m. Ako grad X ne pripada tom ciklusu, onda se iz njega može stići najkraćim putem dužine k koja nije veća od n-m do tog ciklusa, recimo grada Y, pa napraviti ciklus dužine m, pa se onda vratiti istim putem dužine k iz grada Y u grad X. Grad X pripada ciklusu dužine ne veće od 2*k+m<=2*(n-m)+m=2*n-m<=2*n-3.

Kako ispitati postojanje ciklusa neparne dužine? Izaberemo jedan grad X. Formiramo niz P dužine n takav da je P[ i ] bulovska vrednost koja nam govori da li se u određenom koraku osoba iz mesta X može naći u i-tom gradu. Recimo da je X nulti grad. Onda je na početku P[0]=true i P[ i ]=false za ostale vrednosti i jer na početku niz P opisuje stanje nakon 0 koraka. Ako niz u nekom trenutku opisuje skup gradova u kojima se osoba mogla naći nakon j koraka, onda se skup gradova u kojima se osoba mogla naći posle j+1 koraka određuje kao skup svih gradova koji su susedni nekom od gradova u kome je osoba mogla biti nakon j koraka. To radimo najviše 2n-3 puta, a zaustavljamo se kada nakon neparnog broja koraka grad X bude u skupu gradova opisanim sa P.

Dakle svaka osoba može da koriguje parnost svog puta gubljenjem vremena sa najviše 2n-3 koraka, nakon čega joj treba najviše n-1 koraka da stigne u grad susreta, pa se svi mogu sresti u istom gradu u najviše 3n-4 koraka.

4. Ako je sretanje moguće, ono je moguće u najviše 3n-4 koraka za n>=3 (da bi postojao ciklus neparne dužine), odnosno n-1 koraka u suprotnom. Najkraći putevi se određuju na sledeći način: Za svaku osobu se formura po jedan niz nalik na niz P iz prethodne tačke. To je zapravo matrica. Onda se to računa za svaku osobu kao niz P. Stajemo u koraku kada skupovi gradova u kojima se osobe mogu naći obuhvataju jedan isti grad (imaju neprazan presek). Da bismo pamtili puteve, trebaće nam zapravo trodimenzioni niz.

---