BC 11 Q2 - Diskusija
Upravo se završila 2. runda kvalifikacija za BubbleCup 11.
Pišite svoje utiske, rešenja zadatka ili pitajte ako vas zanima neko rešenje! Evo, ja ću da počnem. Koja je strategija za \geq 45 poena na zadatku Seedlings?
1 Like
Zanima me SIO drugi dan, zadatak Taman 
3 Likes
Iskreno, i mene haha
4 Likes
Zanima me ada i homework. Onaj sa gcd.
Šta zapravo treba da uradim?
Brza faktorizacija za brojeve koji nisu prosti
Provera da li je prost
To su tri stvari koje sam koristio.
1 Like
I ja sam isto to radio samo nisam skontao da postoji ovako prost izraz za ono što se traži nego sam ga računao okolo naokolo
Zasto resenje sa LiChao segmentim stablom za zadatak This Means War daje wa. Resenje je bilo tacno pre regrading-a.
1 Like
Kako se radi winter is here?
Ne znam, ja sam svoje rešenje koje je davalo WA samo poslao opet i radilo je. I ja sam koristio LiChao, mnogo je prosto.
1 Like
Takođe mi prošlo LiChao segmentno, verovatno je greška u kodu.
1 Like
Nisam koristio LiChao, ali takodje mi je prolazilo pre regradinga, a da bi proslo posle, morao sam da modifikujem. Je l’ zna iko sta je bila greska pre?
Winter is here
Online, O(\log^3(n)) po upitu (ili O(\log^2(n)) očekivano sa randomizacijom) sa O(n \log^2 n) preprocesiranja
Vrlo je lepo znati da čvorove nekog stabla možemo strukturno urediti tako da svako podstablo bude podsegment tog uređenog niza. Ovo se može uraditi prostim dfs-om i dodeljivanjem vrednosti čvorovima redom kako uđemo u čvor. Zamislimo sada n \times n retku matricu gde je u polju (i, dfs(i)) imamo vrednost dub(i), ostala polja su prazna. Napravićemo sada neku strukturu podataka koja će nam omogućiti da izvučemo najveće dve vrednosti iz proizvoljnog pravougaonika tj. podmatrice ove matrice. Efektivno, mi biramo neko podstablo i neki segment indeksa čvorova (ono što se traži u zadatku). Sada, upit rešavamo na sledeći način. Uzmimo da čvor v ima k dece. U slučaju k = 0, rešenje je -1. U slučaju k=1, rešenje je najdublji čvor tog postabla čiji je indeks između L i R (ako postoji), što lako nalazimo upitom u opisanu strukturu. U slučaju k \geq 2, treba da nađemo dva čvora koji zadovoljavaju pomenute osobine, imaju najveću ukupnu dubinu i nalaze se u podstablima različitih sinova. Da bismo to rešili, radimo sledeći divide and conquer postupak. Podelimo svu decu u dve skoro jednake grupe. Lepa stvar je što uzastopna deca imaju uzastopne segmente u dfs-orderu pa je njihova unija takođe segment. Izvucimo najveća dva iz svakog segmenta. Ako za oba važi da je druga najveća vrednost manja od najveće vrednosti u drugom segmentu, onda su ta dva najveća upravo rešenje. Svakako prihvatamo max iz jednog i max iz drugog kao jedno potencijalno rešenje. U suprotnom, druga najveća vrednost jednog segmenta je veća od najveće u drugom pa taj drugi segment odbacujemo i rekurzivno idemo u polovinu gde su obe veće vrednosti i postupak ponavljamo rekurzivno. Ovaj postupak traje O(\log k) koraka. Može se pokazati da, ako se randomizuje redosled dfs poseta čvorovima ovaj postupak traje u proseku O(1) korak, što spušta složenost celog algoritma za faktor O(\log n).
Statička struktura za odgovor na 2D upite
Po jednoj, npr. spoljnoj dimenziji dignemo segmentno. Po unutrašnjoj, odnosno, u svakom čvoru tog segmentnog čuvamo sortiran niz svih vrednosti koje sadrži taj čvor segmentnog, i sad nad svakim od tih sortiranih nizova dignemo max-segmentno (ukupno vreme konstrukcije je O(n \log^2 n) a memorija O(n \log n). Na upite odgovaramo tako što se krećemo po spoljnom segmentnom upravljajući se po parametrima prve dimenzije, a za svaki čvor koji ceo upada u upit radimo upit u segmentno koje se nalazi u tom čvoru po drugoj dimenziji.
3 Likes
Mozes kod da posaljes?
ne.⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
4 Likes
Winter is Here
Моје решење јe сложености O(nlog^2n+qlogn).
Структуре података које сам користио
1.Инмплицитна сегментна стабла.
2.Модификовано имплицитно сегментно стабло.
У модификована стабла постављам дубину чвора и подстабло а стабло враћа 2 највеће дубине које нису из истог подстабла.
Ad Hoc
Користим трик број 1 са линка испод.
http://codeforces.com/blog/entry/48417
Решење
Решавам све упите Offline са једним DFS-ом. Прво рекурзивно решим суседе тренутног чвора, затим одредим чије подстабло је највеће. Сва подстабла осим тог убацујем у структуру број 2. Рекурзија за подстабла је већ направила структуре број 1 за свако подстабло (макс сегментно стабло). Сада решавам све упите тренутног чвора. Кандидати за решење су 2 највеће дубине из структуре број 2, највећа дубина из структуре број 1 за највеће подстабло и тренутни чвор (ако је у интревалју L R). Након решавања упита све чворове мањих подстабала убацујемо у структуру број 1 највећег подстабла и запамтимо да је та структура сада структура тренутног чвора.
2 Likes