Može li neko da mi ukratko objasni ideju za rešenje ovog zadatka?
Hvala
https://petlja.org/biblioteka/r/problemi/takmicenja-srednje-skole/05_prorok
2 Likes
Najjednostavnije rešenje u \mathcal{O}(N^2) je da za svako K prođemo kroz sve odgovore, “okrenemo” svaki K-ti i za svako pitanje brojimo koliko je odgovora bilo “da” a koliko “ne”. Ako nemamo pitanja za koja imamo i “da” i “ne” odgovore, to K je validno i našli smo rešenje.
Ideja za drugi podzadatak je slična, ali izbegava prolaženje kroz ceo niz svaki put: na početku izbrojimo odgovore za ulaz (bez grešaka), a onda za svako K prođemo kroz svaki K-ti element ulaza i “prebacimo” taj odgovor (smanjimo jedan od dva brojača za 1 i povećamo drugi). Nakon toga možemo da prođemo kroz sva pitanja (jer Q_i \leq 200) i proverimo da li je ovo K validno.
Ovo rešenje, pored početnog \mathcal{O}(N) preprocesiranja, ima složenost \mathcal{O}(N + N/2 + N/3 + \dots) = \mathcal{O}(N \log{N}) za prolaženje kroz delove niza i \mathcal{O}(NQ) za provere, ukupno \mathcal{O}(N \log{N} + NQ).
Za konačno rešenje zadatka je potrebno da eliminišemo \mathcal{O}(NQ) iz složenosti, tj. da ne prolazimo kroz sva pitanja svaki put. Jedna mogućnost je da prođemo samo kroz ona pitanja koja smo “videli” dok smo išli kroz svaki K-ti da bi videli da li su ona validna na kraju, i da na početku izbrojimo koliko ima pitanja koja imaju i odgovor “da” i odgovor “ne” u ulazu da bi proverili da nismo neko propustili.
1 Like