You are not logged in. Please login at www.codechef.com to post your questions!

×

SHUFFL - Editorial

1
1

PROBLEM LINK:

Practice
Contest

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.

  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".

asked 25 Nov '17, 08:51

melfice's gravatar image

2★melfice
71932
accept rate: 0%

edited 27 Nov '17, 18:03

admin's gravatar image

0★admin ♦♦
19.0k348495533


wth! looking at explanation like a dumb,this was easy as hell. :(

link

answered 28 Nov '17, 19:57

des1997's gravatar image

1★des1997
203
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×14,512
×1,417
×96
×43

question asked: 25 Nov '17, 08:51

question was seen: 1,071 times

last updated: 28 Nov '17, 19:57