Official

C - Reversible Card Game Editorial by evima


Assume that Bob decides the direction in which he wants each card before the game starts, and consider whether he can achieve it.

At the start of each turn, if the number of cards in Bob’s desired direction is even, that number will be odd after Alice flips one card. That is, it can’t be zero, so Bob can pick one card in the desired direction. Then, the next turn starts again with an even number of cards in the desired direction.

Therefore, if the game starts with an even number of cards in Bob’s desired direction, he can pick all cards in his desired direction (similarly, considering parity, if the game starts with an odd number of cards in the desired direction, it is impossible to pick all cards in the desired direction).

If the number of cards with \(A_i > B_i\) is even, it is best to set the side with the larger number as the desired direction for all cards, as this results in an even number of cards in the desired direction. When the number of cards with \(A_i > B_i\) is odd, by setting the side with the smaller number as the desired direction for just the card with the smallest difference, the game can start with an even number of cards in the desired direction. This is the best considering that it is impossible to pick all cards with the larger number side facing up.

(Modified the first draft written by GPT-4.)

posted:
last update: