262B

262B is a programming problem that appeared in a Codeforces contest. The task is titled “Ciel and Duel” and presents a duel between two players in which each player starts with a hand of cards whose values are integers between 0 and 10. In each round, both participants simultaneously choose a card from their hands. The card with the higher value wins the round. When the values are equal, both players gain a new card whose value is the value of the used card plus one. The winner of a round gains a new card equal to the absolute difference of the two values used in that round. A player may run out of cards, at which point the duel ends. The challenge is to determine which player can finish the duel having collected more “active” cards, assuming both play optimally.

The solution requires analyzing the state of the decks after each possible play. A key observation is that the game depends only on the multiset of card values each player possesses at any point. Therefore a greedy strategy can be applied: always pair the highest remaining cards in the two hands. It turns out that this strategy guarantees that the total number of cards each player will win is just the sum of all values in the opponent’s hand that exceed the corresponding values in the player’s hand. Thus the winner can be decided by comparing the sum of cards that can be taken from the opponent.

The official editorial outlines a linear‑time algorithm. It first sorts both players’ lists of card values. Then, using two pointers, it counts how many cards of the opponent exceed the current card of the player. The sum of these exceedances gives the number of cards the player can win. The same is done for the other player. The player with the larger count is declared the winner; in case of equal counts the duel ends in a draw. This algorithm runs in O(n log n) time due to the initial sorting and uses O(1) additional space.