Analiza

Označimo sa ~R_i~ redni broj učenika koji sedi za računarom ~i~. Na početku je ~R_i = i~ za svako ~i = 1, 2, \ldots, N~. U svakom premeštanju mi praktično menjamo mesta dva elementa niza ~R~ i nakon svakog premeštanja želimo da proverimo da li postoji neki indeks ~i~ za koji važi ~|i - R_i| > K~.

Pomenutu proveru možemo uraditi pravolinijski: u svakom od ~M~ koraka zamenimo dva elementa niza a zatim prođemo kroz ceo niz i uporedimo ~|i - R_i|~ i ~K~. Složenost ovog algoritma je ~O(NM)~ i rešava podzadatak 1 (~20~-~30~ poena) ali je previše spor za ostale podzadatke.

Primetimo da kada vršimo proveru nakon ~i~ premeštanja, za sve indekse ~j~ koji nisu učestvovali u prvih ~i~ premeštanja važi ~R_j = j~; dakle, ne moramo proveravati ceo niz već (u ~i~-tom koraku) samo indekse iz prvih ~i~ premeštanja (~A_1, B_1, A_2, B_2, \ldots, A_i, B_i~; među njima može biti istih). Ovo daje algoritam složenosti ~O(M^2)~ što je dovoljno za prva dva podzadatka (~40~-~50~ poena).

U trećem podzadatku važi ~K = N - 3~. Međutim, jedini indeksi ~i~ za koje je moguće da važi ~|i - R_i| < N - 3~ su ~1, 2, N-1~ i ~N~ (ostali se ne mogu dovoljno "udaljiti"; proveriti!) pa je nakon svake zamene dovoljno proveriti vrednosti ~R_1, R_2, R_{N-1}~ i ~R_N~ što nam daje ukupnu složenost ~O(N+M)~ i rešava ovaj podzadatak (~20~ poena).

Da bismo rešili ceo zadatak, primetimo da nije neophodno stalno proveravati puno indeksa već je dovoljno da u svakom trenutku pamtimo koliko ima indeksa ~i~ za koje važi ~|i - R_i| > K~; označimo tu količinu sa ~x~ (na početku je ~x = 0~). Pomenuti indeks postoji akko je ~x > 0~. Zamenom dva elementa niza vrednost ~x~ se može promeniti najviše za ~2~ i razlikovanjem nekoliko slučajeva lako "update"-ujemo ~x~ (npr. ako je ~|A_i - R_{A_i}| \leq K~ i ~|B_i - R_{B_i}| > K~, a ~|A_i - R_{B_i}| > K~ i ~|B_i - R_{A_i}| > K~, tada se nakon ~i~-tog premeštanja ~x~ povećava za ~1~, itd.) . Složenost ovog rešenja je ~O(N+M)~ i osvaja svih ~100~ poena.