NewCardTrick
SRM 854 · 2024-04-24 · by misof
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.
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.
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.
Submissions are judged against all 72 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class NewCardTrick with a public method int deckSize(int B, int S) · 72 test cases · 2 s / 256 MB per case