PROBLEM LINK:
Author: Misha Chorniy
Tester: Alexey Zayakin
Editorialist: Oleksandr Kulkov
DIFFICULTY:
EASY-MEDIUM
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.
- [0,W). This is even-indexed elements so previous index is 2P.
- [W,S-1). This is even-indexed elements and one element before them is erased so previous index is 2P+2.
- [S,S+W). This is odd-indexed elements so previous index is 2(P-S)+1.
- [S+W,2S-1). This is odd-indexed elements and one element before them is erased so previous index is 2(P-S)+3.
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.
Tester’s solution can be found here.
