Posts

Showing posts from December, 2014

Problem discussion: ShufflingCardsDiv2 - Topcoder SRM 641 900pt

Topcoder SRM 641 happened a few days ago and featured an unusually easy problem set for division 2. Before continuing reading the post, please read the problem statement (login required). Now that you have read the problem statement, let me state the most important fact in the problem statement The cards are shuffled exactly twice. This is very important because it makes the problem much easier. Since there are only two shuffles, there are a limited number of steps to be followed. Let’s analyze the shuffling procedure closely. In the beginning we have $$2N$$ cards numbered from $$1$$ to $$2N$$. These cards are divided into two piles: one containing the first half cards $$1 \cdots N$$ and the other containing the remaining cards. Let’s denote the cards which have number less than or equal to $$N$$ as $$A$$ and the others as $$B$$. Now, the two piles will look like this $$\text{A A A A A …}$$ $$\text{B B B B B …}$$ After performing the interleaving, we will get a deck that look