Editorial for Premestanja


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

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.


Comments

There are no comments at the moment.