PROBLEM LINK:Author: Misha Chorniy DIFFICULTY:EASYMEDIUM PREREQUISITES:None PROBLEM:Consider array $A=\{1,\dots,M\}$. Split it into two arrays of equal size with even and odd indices. Erase in each array number on the place $\left\lfloor \dfrac{SX}{Y}\right\rfloor$ where $S$ is the size of subarray and concatenate arrays after that. Each time size of array reduced by $2$. You have to output xor of values which whill remain when there are only two elements. All indexes are considered to be $0$based. QUICK EXPLANATION:Consider procedure in reverse order. You can trace back positions of remained elements. EXPLANATION:Assume current position of element in the array is $P$ and size before the last step was $2S$. Let's calculate its previous position. At the last step element $W=\left\lfloor \dfrac{SX}{Y}\right\rfloor$ was erased from both subarrays. After that positions of remained elements split into four different groups.
Given that we can in $M$ steps recover initial positions of last two elements and just output their xor. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. RELATED PROBLEMS:
This question is marked "community wiki".
asked 25 Nov '17, 08:51

wth! looking at explanation like a dumb,this was easy as hell. :( answered 28 Nov '17, 19:57
