Deceitful War, Qualification Round 2014.
This was a fun one. There are three strategies that we need to figure out and take into account when we’re writing our solution:
- Ken’s optimal strategy for playing normal War.
- Naomi’s optimal strategy for playing normal War.
- Naomi’s optimal strategy for playing Deceitful War.
Let’s start with Ken’s strategy. As far as he knows, Naomi accurately tells him the weight of the block she has chosen, and then he gets to pick one of his blocks to play. Which block should he pick? Well, he always wants to win. So if he can, he should pick a block of his that is larger than . Of those blocks that are larger, he should use the smallest, because that will allow the larger blocks to be used later and potentially win more rounds. If he has no blocks larger than , then he should just use the smallest block he has. He can’t win this round, so he may as well avoid wasting any of his heavier blocks.
When Naomi plays normal War, she gets to pick the order in which she plays her blocks. Which block should she pick? We know that if she picks a block which Ken can beat, he’ll play the smallest block that can beat it. Otherwise, he’ll play his smallest block. She wants to force Ken to play his highest blocks, and the best way to do that is to play her highest blocks. So she’ll play her blocks in order from largest to smallest, giving her the best possible score without knowing the weights of Ken’s blocks.
But when Naomi plays Deceitful War she not only gets to choose the order of her blocks, she also gets to lie to Ken about the weight of her blocks. She can’t lie to win matches that she otherwise would have lost, because then Ken will figure out that she’s cheating. But she can lie to force Ken to use different, larger, blocks than he otherwise would have. Start with Naomi’s smallest block. If it’s smaller than Ken’s smallest block, then she can’t possibly win with it. But she can lie about its weight and force Ken to use his largest block to beat it, by telling Ken its weight is between his largest and his second-largest block. If it’s larger than Ken’s smallest block, then she can win by lying about its weight, telling Ken it’s bigger than his biggest block. Ken will then play his smallest block, and Naomi will win. Naomi can keep going through her blocks like this from smallest to largest, systematically lying and get the most wins possible without Ken finding out about her deceit.
def ken_choice(told_naomi, ken): for j in range(len(ken)): if ken[j] > told_naomi: return ken.pop(j) return ken.pop(0) def normal_war(naomi, ken): score = 0 for i in range(len(naomi))[::-1]: if naomi[i] > ken_choice(naomi[i], ken): score += 1 return score def deceitful_war(naomi, ken): score = 0 for i in range(len(naomi)): if naomi > ken: score += 1 ken.pop(0) else: ken.pop(-1) naomi.pop(0) return score def solve_case(case): naomi, ken = case naomi.sort() ken.sort() normal = normal_war(naomi.tolist(), ken.tolist()) deceitful = deceitful_war(naomi.tolist(), ken.tolist()) return "%i %i" % (deceitful, normal)