AliceBobShuffle
SRM 544 · 2011-11-22 · by pieguy
Problem Statement
Alice and Bob decide to play a game with a deck of cards. Each card has a single positive integer written on it. Multiple cards may have the same number. Cards with the same number are indistinguishable. Alice and Bob begin by splitting the deck into two piles. They each take one pile. Then each of them writes down the sequence of numbers on the cards in his/her pile, in order from bottom to top.
Then comes the first phase of the game. In this phase Alice and Bob build a third pile of cards, designated the "community" pile. Initially, the community pile is empty. The phase consists of multiple turns. In each turn, either Alice or Bob takes the top card from his/her pile and places it on top of the community pile. This continues until all the cards are in the community pile. (Note that Alice and Bob are not required to alternate. They may take the turns in any order they like.)
Afterwards there is the second phase of the game. In this phase Alice and Bob take the cards from the community pile to their personal piles. Again, this happens in turns. In each turn, either Alice or Bob takes the top card from the community pile and places it on top of his/her personal pile. This continues until there are no more cards in the community pile. (Again, Alice and Bob are not required to alternate. They may take the turns in any order they like. They are each allowed to take any cards to their pile, not just those they had at the beginning. They are also each allowed to take any number of cards, regardless of how many they had at the beginning.) Finally, they again write down the sequence of numbers on the cards in each pile, from bottom to top.
Later, Alice and Bob decide to double-check what they wrote down. Given the starting and ending lists of cards, they wonder how many ways the game could have progressed. You will be given 4
Notes
- Each card movement can be described by the source pile, the destination pile, and the number on the card.
- Two games are considered different if their sequences of card movements differ.
Constraints
- AliceStart, BobStart, AliceEnd, and BobEnd will each contain between 1 and 50 elements, inclusive.
- Each element of AliceStart, BobStart, AliceEnd, and BobEnd will be between 1 and 100, inclusive.
{1, 3}
{2, 4}
{2, 3}
{1, 4}
Returns: 4
There are 4 possible orders for the community pile at the end of the first phase: {4, 3, 2, 1}, {3, 4, 2, 1}, {4, 3, 1, 2}, {3, 4, 1, 2}. (All of these are listed from bottom to top.) Each of these uniquely determines one possible game.
{1, 2, 1}
{1, 2}
{1, 2, 1}
{2, 1}
Returns: 4
The only possibility for the order of the community pile at the end of the first phase is {1, 2, 1, 2, 1}. Still, there are 4 ways this game could have been played. (For instance, the bottommost 1 must have come from Alice's deck, but the 2 above it could have been placed by either player.)
{1}
{2}
{3}
{4}
Returns: 0
This is impossible.
{1, 2}
{3}
{3}
{2, 1}
Returns: 0
Also impossible.
{3, 3, 2, 4, 1, 3, 1, 2, 1, 1, 5, 5, 1, 2, 3, 1, 2, 1, 2, 1, 1, 1, 2}
{4, 1, 4, 3, 4, 4, 4, 3, 2, 1, 6, 2, 2, 3, 2, 2, 1, 3, 2, 3}
{4, 1, 4, 3, 4, 4, 4, 1, 3, 1, 2, 2, 2, 3, 2, 1, 2, 1, 2, 2, 2}
{3, 3, 2, 3, 4, 2, 1, 2, 1, 1, 5, 6, 5, 1, 3, 1, 2, 3, 1, 1, 1, 3}
Returns: 314159265
Submissions are judged against all 60 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class AliceBobShuffle with a public method int countWays(vector<int> AliceStart, vector<int> BobStart, vector<int> AliceEnd, vector<int> BobEnd) · 60 test cases · 2 s / 256 MB per case