Editorial for Igra na Matrici


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.

Author: Pajaraja

Posmatrajmo igru gde se ne pojavljuje ni jedno specijalno polje, to jest gde su sva polja neobojena. Obojimo tablu šahovski bordo-ciklama (to jest. šahovski crno-belo, ali da ne zovemo polja crna i belo, jer se oni već pojavljuju u tekstu), pri čemu je polje (m,n) ciklama. Posmatrajmo vrednost koja se dobija uzmemo bitovski xor kad na svim poljima bordo boje. Ideja je da će se moći igrati u suštini NIM (https://en.wikipedia.org/wiki/Nim) na ovim poljima.

Ako bitovski xor nije 0, aktuelni igrač može isto kao u NIMu da izabere jednu gomilu i napravi da taj xor bude 0. Ako xor jeste 0, šta god igrač odigrao xor nadalje neće biti 0: ako premesti nešto sa bordo polja, moraće da promeni xor, isto kao i u običnom NIMu, dok ako premesti nešto sa ciklama polja, samo će dodati nešto na neko bordo polje, opet menjajući xor. Kako na kraju mora na ovim poljima da xor bude 0, ispostavlja se da ova igra ima istog pobednika ko NIM nad bordo poljima. Ako na početku taj xor nije 0 onda pobedjuje prvi igrač, koji nakon svog poteza uvek napravi da xor bude nula, a ako je xor 0, pobedjuje drugi igrač jer u prvom potezu, prvi igrač poremeti taj xor da ne bude 0 pa nadalje drugi igrač u svakom potezu igra tako da posle njegovog poteza xor bude 0.

Ispostavlja se da je ovakva analiza tačna za celu igru; to jest da specijalna polja uopšte nisu bitna. Naime, po uslovu zadatka, belo polje može da bude samo na bordo polju, dok crno polje može da bude samo na ciklama polju. Znači kad skidamo nešto sa belog bordo polja, opet samo menjamo xor za onoliko koliko smo skinuli sa te gomile, jer nije bitno da li na jedno ili oba ciklama polja stavljamo t njih, kao i što ni na šta ne utiče pri skidanju belog na crno ciklama da li se pola njih unište.

Sada se rešenje lako implementira u O(k+t+s).

Zadatak je preuzet sa \texttt{Moscow} \texttt{Autumn} \texttt{Workshop} \texttt{2019} \texttt{Day} \texttt{2}, takmičenje \texttt{In} \texttt{A} \texttt{Galaxy} \texttt{Far} \texttt{Far} \texttt{Away}


Comments

There are no comments at the moment.