O kom takmičenju se radi?
Treci krug kvalifikacija - 2018
Poruka:
Poceo je treci krug kvalifikacija:
Info -> https://takprog.petlja.org/srednjaskola/post/55
Okruzenje -> https://arena.petlja.org/Competitions/Competition/179
Treci krug kvalifikacija - 2018
Poceo je treci krug kvalifikacija:
Info -> https://takprog.petlja.org/srednjaskola/post/55
Okruzenje -> https://arena.petlja.org/Competitions/Competition/179
Jel za 5. prolazi O(NlogN + Mlog^2N) ?
Implicitno segemntno+binarna?Ja sam tako,msm da su to prva 2 podzadatka…
I ja sam radio isto to. Testirao sam za nasumican test primer dimenzija 300000 i radilo je otprilike 2.2 sekunde.
Trebalo bi da prodje ali ne mogu da garantujem.
Ja sam na stoperici merio vreme, nije mi se bas svidelo haha
Da li neko može da mi kaže kako se radi 4. zadatak?
Segment [L,R] ima sumu s[R]-s[L-1] (s[i] je suma prvih i elemenata). Iz upita dobijes ili s[R]>s[L-1] ili s[L-1]>s[R]
Sada pravis graf tako da postoji veza izmedju R i L-1 (ako je s[R]>s[L-1] onda od R do L-1, ako je s[R]<s[L-1] onda od L-1 do R). Ako graf ima cycle (ne znam kako se na srpskom kaze, ciklus valjda?) onda je -1. Uostalom, za svaki cvor v, s[v] = max(s[u]+1) gde postoji veza od v do u. Onda napravis niz a gde je a[i]=s[i]-s[i-1].
Moze i topolosko sortiranje
E može u O((M+N)logS) gde je S suma P-ova tako što umesto binarne pametno radiš query u segmentnom (trebalo bi da je tačno, kucao sam stress test sa brutom). Nisam siguran da log^2 prolazi pošto je i meni bilo pipavo.
Ne znam cemu sugavi T (mogli su staviti n=10^5),lako se gresi bas ako se ne ocisti bas sve pre novog test primera.
Stavili su T da se ne bi dobijali poeni ako takmicar napise svugde -1. Moja pretpostavka
Moguce ali to je onda trebalo biti radjeno i kod 4. iz 1. kruga,da bude fer.
Slazem se, ja sam tako dobio 20 poena tada na 4.
Ne bi trebalo da prolazi navedena složenost.
E matori imao sam isto resenje kao tvoje samo nisam imao ideju kako da napravim s[v]=max(s[u]+1) zato sto ima nekad situacija kada od prvog idu dva puta do dva cvora, onda od ovog jednog se produzi na jos jedan i vrati ga na ovaj drugi. Malo bolesno ali ovo su veze(a1>a3, a1>a5, a5>a7, a7>a3), e sad ako ja upisem prvo u a3, onda moram da se vracam na njega posle a7, a do tad sam vec iz a3 upisao vrednosti u druge brojeve, moze mala pomoc?
Zaista ne mogu da ti pomognem jer bas i ne razumem tvoje pitanje. Inace, bez tog ‘matori’, ne ide da pises tako ovde
E @matori ja sam za 4. radio isto, napravio sam graf ali nisam uspeo da smislim sta da radim za slucaj kad je tipa a1 > a3, a1 > a5, a5 > a7, a7 > a3 isto kao i andrejko.
Pitaj andrejka, ja ne znam