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
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.
1 Like
Ja sam na stoperici merio vreme, nije mi se bas svidelo haha
1 Like
Da li neko može da mi kaže kako se radi 4. zadatak?
1 Like
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].
1 Like
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
1 Like
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.
1 Like
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
1 Like
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.
4 Likes
Pitaj andrejka, ja ne znam
1 Like