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 looks like

\(\text{A B A B A B A B A B . . .}\)

Now, we need to shuffle this deck again. Let’s assume that \(N\) is even. (We will cover the odd case later.) Divide the deck into two piles.

\(\text{A B A B A B …}\)
\(\text{A B A B A B …}\)

The result after interleaving the above piles is given to us as input. Note that the two piles shown above are not exact i.e for any of the above piles we can take any permutation of the cards for interleaving. But, one condition still holds:

In any pile, the number of \(A\)s is equal to the number of \(B\)s.

After interleaving, all cards in the top pile will appear at even indices (assuming 0-based indexing). So, we need to check all even indices of the given array/vector and count the number of \(A\)s and \(B\)s. If they are equal, then return "Possible" otherwise return "Impossible".

As I have said before, this solution is valid only if \(N\) is even. When \(N\) is odd the number of \(A\)s and \(B\)s need not be same. In fact, the number of \(A\)s will be 1 greater than the number of \(B\)s.

Here’s the final code in C++:

string shuffle (vector<int> permutation) {
  int countA, countB;
  int n = permutation.size();
  for (int i = 0; i < n; i += 2) {
    if (permuation[i] <= (n / 2))
      ++countA;
    else
      ++countB;
  }

  if ((n / 2) % 2) {
    if (countA - 1 == countB)
      return "Possible";
    else
      return "Impossible";
  } else {
    if (countA == countB)
      return "Possible";
    else
      return "Impossible";
  }
}