×

# SHUFFL - Editorial

Author: Misha Chorniy
Tester: Alexey Zayakin
Editorialist: Oleksandr Kulkov

EASY-MEDIUM

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.

1. $[0,W)$. This is even-indexed elements so previous index is $2P$.
2. $[W,S-1)$. This is even-indexed elements and one element before them is erased so previous index is $2P+2$.
3. $[S,S+W)$. This is odd-indexed elements so previous index is $2(P-S)+1$.
4. $[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.

# RELATED PROBLEMS:

This question is marked "community wiki".

2★melfice
71722
accept rate: 0%

18.4k348492529

 1 wth! looking at explanation like a dumb,this was easy as hell. :( answered 28 Nov '17, 19:57 4★des1997 20●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×13,928
×1,322
×96
×43

question asked: 25 Nov '17, 08:51

question was seen: 997 times

last updated: 28 Nov '17, 19:57