GCJ – Deceitful War

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:

  1. Ken’s optimal strategy for playing normal War.
  2. Naomi’s optimal strategy for playing normal War.
  3. 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 Told_{Naomi} . 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 Told_{Naomi} , 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[0] > ken[0]:
            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)
Advertisements

2 thoughts on “GCJ – Deceitful War

  1. About “2. Naomi’s optimal strategy for playing normal War.”, I think that there is no such thing like that. As long as Ken uses his optimal strategy, the result will always be the same, no matter what strategy is used by Naomi.
    A kind of proof for this can be that in my solution Naomi is choosing her blocks from smallest to largest, and my solution is still judged as correct.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s