Problem Statement
Alice and Bob came up with a new twist on an old magic trick. Their version of the trick looks as follows:
- Alice is locked in an opaque box.
- Bob has a spectator select B cards out of a deck of N mutually distinct cards. The spectator has a completely free choice.
- Bob selects one of the B cards to be the hidden one and places it face-down.
- Bob arranges the remaining B-1 cards into a sequence.
- The spectator now gets to modify Bob's sequence by choosing a number between 0 and S, inclusive, and then making that many "local swaps", one after another. In each local swap the spectator exchanges the positions of two adjacent cards in the face-up sequence.
- Bob is locked in a second opaque box to prevent him from cheating (i.e., secretly communicating the hidden card to Alice somehow). Then, Alice is released from her box.
- Alice examines the resulting sequence of B-1 face-up cards and then correctly guesses the face-down card.
Bob and Alice want to have a strategy that guarantees that Alice will always correctly identify the face-down card, regardless of the choices made by the spectator.
Determine and return the maximum value of N - that is, the maximum size of a deck of cards for which such a strategy exists and the card trick can be performed as described above.
Return -1 if there are arbitrarily large values of N that work, and return -2 if for the given values B and S there is no valid deck size.
Definition
- Class:
- NewCardTrick
- Method:
- deckSize
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int deckSize(int B, int S)
- (be sure your method is public)
Notes
- If the spectator is allowed to perform swaps but there are fewer than two face-up cards, the spectator cannot and therefore does not make any swaps.
- Don't miss that the spectator can only swap adjacent cards in Bob's sequence in each step.
- E.g., if S = 1 and Bob places down the visible sequence [3, 7, 5], the spectator can keep it as [3, 7, 5], rearrange it to [7, 3, 5], or rearrange it to [3, 5, 7]. Those are the only three options the spectator can choose to do in this example scenario.
- The spectator can only change the order of the cards Bob placed face-up. They don't get to change which card is face-down.
Constraints
- B will be between 1 and 6, inclusive.
- S will be between 0 and 10, inclusive.
Examples
1
2
Returns: 1
Spectator selects one card. Bob places the card face-down. There is an empty sequence of visible cards. The spectator performs no swaps. (They have the option to do at most S = 2 swaps, but as there are no face-up cards, there's nothing the spectator can swap.) Alice is released from her box. All she sees is a face-down card. If the deck size is N = 1, she can determine what card that is. For any greater N she has no way to tell which card it is.
2
0
Returns: 3
Spectator selects two cards. Bob places one card face-down and the other face-up. The spectator performs no swaps. Once Alice is released from her box, she sees a face-up and a face-down card. The trick can obviously be performed for N = 2, Alice would announce that the face-down card is the only remaining card in the deck. However, N = 2 is not optimal. The optimal value of N for this test case is N = 3. The best strategy will already involve Bob: he will have to observe what cards the spectator chose and cleverly choose what to do based on that observation. Suppose the cards are numbered from 0 to N-1 There are three possible sets of cards the spectator can select in step 2 of the trick: {0, 1}, {1, 2}, or {0, 2}. We can notice that each of these three sets has the form {x, y}, where y = (x+1) mod 3. In particular, in the set {0, 2} we have x = 2 and y = 0. For each set {x, y}, Bob will place the card y face-down and then the card x face-up. Once Alice is released from the box, she sees the face-up card x and she can add 1 to its number (computing modulo 3) to determine the hidden card y.
4
3
Returns: 7
In step 5 of the trick the spectator gets to rearrange Bob's chosen sequence into any other sequence of their liking: three swaps of consecutive cards are enough to rearrange one sequence of three cards into any other sequence. Thus, essentially, in this test case Alice is shown the set of B-1 cards Bob did not place face-down. She gets no useful information from their specific order in the sequence.
5
1
Returns: 29
5
0
Returns: 124
A "traditional" version of the trick involves the spectator selecting five cards but making no swaps: the sequence Bob produces is directly shown to Alice. Even though the trick is commonly performed with a standard 52-deck of cards, it can be done with a much bigger deck as well.
4
1
Returns: 11
If the spectator is given fewer chances to disrupt Bob's actions, the couple can perform the trick with a bigger deck.
1
0
Returns: 1
1
1
Returns: 1
1
2
Returns: 1
1
3
Returns: 1
1
4
Returns: 1
1
5
Returns: 1
1
6
Returns: 1
1
7
Returns: 1
1
8
Returns: 1
1
9
Returns: 1
1
10
Returns: 1
2
0
Returns: 3
2
1
Returns: 3
2
2
Returns: 3
2
3
Returns: 3
2
4
Returns: 3
2
5
Returns: 3
2
6
Returns: 3
2
7
Returns: 3
2
8
Returns: 3
2
9
Returns: 3
2
10
Returns: 3
3
0
Returns: 8
3
1
Returns: 5
3
2
Returns: 5
3
3
Returns: 5
3
4
Returns: 5
3
5
Returns: 5
3
6
Returns: 5
3
7
Returns: 5
3
8
Returns: 5
3
9
Returns: 5
3
10
Returns: 5
4
0
Returns: 27
4
1
Returns: 11
4
2
Returns: 7
4
3
Returns: 7
4
4
Returns: 7
4
5
Returns: 7
4
6
Returns: 7
4
7
Returns: 7
4
8
Returns: 7
4
9
Returns: 7
4
10
Returns: 7
5
0
Returns: 124
5
1
Returns: 29
5
2
Returns: 14
5
3
Returns: 9
5
4
Returns: 9
5
5
Returns: 9
5
6
Returns: 9
5
7
Returns: 9
5
8
Returns: 9
5
9
Returns: 9
5
10
Returns: 9
6
0
Returns: 725
6
1
Returns: 125
6
2
Returns: 41
6
3
Returns: 17
6
4
Returns: 17
6
5
Returns: 11
6
6
Returns: 11
6
7
Returns: 11
6
8
Returns: 11
6
9
Returns: 11
6
10
Returns: 11