Analiza

Potproblem 1

Pravolinijsko rešenje se dobija tako što se svaka atrakcija posmatra kao poslednja na turi koju je obišla Ana. Ako je fiksirana poslednja atrakcija, onda se kompletna tura dobija tako što se krene poslednje atrakcije i 'vraća unazad' pomerajući se svaki put do atrakcije od koje vodi jedini put do atrakcije u kojoj se trenutno nalazimo. Naravno, tokom pomeranja se sabiraju lepote atrakcija koje je Ana posetila. Postupak se prekida u trenutka kada bi se narednim korakom vraćanja premašilo ukupno vreme koje Ana ima na raspolaganju.

Potproblem 2

Rešenje se dobija uz malu doradu rešenja za potproblem 1. Polazeći od atrakcije ~A~ i vraćajući se duž puta koji vodi do trenutne atrakcije, pre ili kasnije ćemo zatvoriti petlju. Može se odrediti vreme da se obiđu sve atrakcije na petlji, a zatim i koliko puta se ta petlja može obići a da se ne premaši vreme ~T~. Na kraju ako je ostalo vremena treba započeti još jedan prolaz kroz petlju i zaustaviti se u trenutku kada vreme premaši vreme ~T~. Naravno, tokom postupka je određivana suma lepota atrakcija koje su obiđene.

Potproblem 3

Ovaj potproblem se može rešiti kao i potproblem 2, pri čemu ne krećemo svaki put od atrakcije koja je na kraju ture, već koristimo rezultate od prethodnog obilaska.

Potproblem 4

Ako je niz ~X~ permutacija brojeva od ~1~ do ~N~, onda svi putevi obrazuju kolekciju petlji (ciklusa). Za svaku petlju je dovoljno odrediti čvor od koga treba krenuti kako bi se dobila maksimalna suma lepota atrakcija koje su posećene. To se može obaviti i linearnom vremenu (linearnom po broju atrakcija na petlji), korišćenjem dva pokazivača (indeksa): jedan za početak ture, a drugi za kraj ture.

Potproblem 5

Maksimalni broj poena se dobija tako što se za svaku atrakciju ~A~ odredi suma lepota atrakcija (kao i vreme potrebno da se obiđu te atrakcije) na turi koja se završava na atrakcija ~A~ i čija je dužina ~2^I~ (~I=0, 1, 2, ... \lfloor \log T\rfloor~). Dužina ture je jednaka broju atrakcija na turi. To se može obaviti u složenosti ~O(N \times \log T)~. Naime, ako znamo sume atrakcija za ture dužine ~2^{I-1}~, onda sumu za turu dužine ~2^I~ koja se završava na atrakciji ~A~ dobijamo tako što nadovežemo dve ture dužine ~2^{I-1}~: turu koja se završava na atrakciji ~A~ i turu koja se završava u čvoru od koga vodi put do početka ture dužine ~2^{I-1}~ koja se završava na atrakciji ~A~.

Kada smo odredili opisane sume tura, onda je potrebno za svaku atrakciju odrediti turu maksimalne dužine koja se završava u toj atrakciji. To obavljamo tako što kombinujemo ture određene u prethodnom pasusu. Počinjemo sa turom dužine ~2^{\lfloor\log T\rfloor}~. Ako je vreme potrebno za njen obilazak veće od dozvoljenog prepolovimo dužinu (tj. podelimo sa 2). Ako vreme nije veće, dodajemo tu turu na kompletnu turu, pomeramo se na atrakciju na kojoj ta tura počinje (tačnije na atrakciju koja prethodi atrakciji na kojoj ta tura počinje) i nastavljamo sa turom dvostruko kraćom od one koja je dodata.