Google Code Jam 2019 Round 3 Zillionim

For all game states: a lone segment or union of multiple segments, the state is winnable if there is a winning strategy for the player playing the turn, we will note this as W. Identically, a losable state is that there is a losing strategy, noted as L.

If no winning strategy exist, we note it as U. If no losing strategy exists we will note it as V.

A U state always leads to a W state for the adversary (Theorem): Being in U means that after any move, the adversary can using a move land my state back to U (Because if not, there exists a move after which the adversary cannot force me back to U, i.e. whatever he does I will get a W state, which invalidates the definition of initial U state). Let’s build an AI adversary which always does this. If the last turn was taken by the adversary, he won. If it was taken by me, then the last move was performed on a W state, invalidating the above property (The adversary didn’y play the forcing move).

From a W state, there exists a move which forces back to a U state (if not, all move leads to a W state, the adversary could have won with optimal play).

Identically, an V state leads to an L state. L can move to V state.

It is like a debate in which the debater can change subjects but only say one word, and the one with the last word wins. What happens to the winnability when we take the union of two subsets? U+U = U : whatever subject you choose I will reply.

U+U -(any move)-> W+U -(exist move)> U+U; I lose. U+U = U.
W+U -(exist move)> U+U -(any move)-> W+U; I win. W+U = W.
V+V -(any move)-> L+V -(exist move)->V+V
  ...> V+V-(any move)->L+V-(last move)->L+L; V+V = U, L+V = W

Let’s start bottom up, any contingous egment with <10E10 coins is L. So maybe we can do dynamical programming with the segment size as the parameter…? at = 10E10, I win with the only possible move. All the way up to 3x10E10

However, one should realize quickly that in the problem the AI plays randomly, not optimally. We need a way to quantify the size of the phase space that would lead to our victory.

For our turn, if the state is winnable, we should play the winning strategy, the win rate is 100%. If the state is losable, we should choose a move such that the AI will choose a losing move (i.e. leading to a winning state for me) with the biggest probability. Unfortunately it doesn’t have to be the next move that the AI choose a losing move, as long as it chooses one losing move I can win.

We need to do one pass to determine which segment sizes are winnable states. Since 1e12 is huge, I think we can renormalize 1e10 to 1 and work with floats instead, or we would have to represent entire slices of the table by some kind of description. Another way is to start working only when the end is near.

Sizes 0 to 1e10-1 are U, 1e10 to 2e10-1 are W, 2e10 is W up to 3e10 are W. 3e10+1 is L…

Recursively, if a size can be cut (after removing the 1e10 central coins) into an U+U segment, then that size is W. If any cut will yield W+U, then it is U.

The first U segs defined are [0, 1e10-1], using recursion [1e10, 3e10-1] are W. A problem occurs when W+W appears. It’s getting too complicated.

Try again

# the following is a lost state (0 moves till game end)
<1e10:phase space=0, a lost state
# the following all points to a lost state (1 move till game end)
1e10:phase space=1
3e10-1:phase space=2e10, each leading to two <1e10 for the opponent
# the following (2 or 3 till game end)
3e10: phase space=2e10+1, all leading one <1e10 and one >1e10, except one leading to 1e10+1e10

To win against a random computer, you have to strive to maximize the phase space in which you always get an odd number of moves-till-gameover.

When you get the union of two subsets, the parity is the sum of the two parities. We could make a table T of the probability of the parity of remaining moves being odd. But that will be answering the question: what move should I play this turn, such that afterwards if both players play randomly, I will win most of the time?

It is a greedy algorithm but not the optimal one. In case a winning strategy exists then the win rate should be 100%. And not considering moves in which I don’t play the winning strategy. So we see that there is a need to look at a state from the AI’s standpoint and from my standpoint.

To lighten the notations, let us relax the constraint to consider only floats a continuous segment of length 100, each time someone removes a continuous segment of size 1. The original game is this relaxed game restricted to playing segments starting on multiples of 1e-10.

Since there should be of the order of 50 moves, and the problem is a suboptimal one, let’s consider a finite class of situations we would like to force the game into.

Let’s backtrack:

(-1) AI left with only segments of size [0,1[ and loses
(-2) I play a move that breaks the only non [0,1[ into 2 or more [0,1[
(-3a) AI breaks the only none [0,1[ into yet another non-[0,1[ and one [0,1[
(-3b) AI breaks the one of two non-[0,1[ into two [0,1['s

Eureka

I think the segment size 2e10 is very strong against the computer because for sure with probability 0.9999999999 the computer will break it down into two unplayable <1e10’s. But in our turn we could in addition to the above moves, play the move that breaks it down to a 1e10 segment.

First we can co-digest the whole segment into 2e10’s and <1e10’s. If there is an odd number of such segments left in my turn then I will surely win if I continue cutting 2e10 into two <1e10’s. If there is an even number, I cut one of them into 0+1e10, the next time There will be an odd number of playable segments left! In the unlikely event that the computer plays 2e10->0+1e10, then I also play it!

So this is my first Question solved using Golang. Still clumsy! Also, the judge system is only golang 1.7.4, so it was slightly lengthy to write by hand the sort.

package main

import (
	"fmt"
	"sort"
)

type segment struct {
	first, last int
}

func (s *segment) lenth() int {
	return s.last - s.first + 1
}

const unit = 10000000000

func playmove(pq *array, P int) {
	for i, seg := range *pq {
		if P >= seg.first && P < seg.last {
			(*pq)[i] = segment{seg.first, P - 1}
			(*pq) = append((*pq), segment{P + unit, seg.last})
			goto correct
		}
	}
	panic("non found")
correct:
	return
}

// The following was needed in Go v.1.7.4, used by the judge
type array []segment

func (pq array) Len() int {
	return len(pq)
}

func (pq array) Less(i, j int) bool {
	return pq[i].lenth() > pq[j].lenth()
}

func (pq array) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func main() {
	//time.Sleep(10000 *time.Millisecond)
	T := 0
	W := 0
	fmt.Scanf("%d %d", &T, &W)
cases:
	for ti := 1; ti <= T; ti++ {

		pq := make(array, 0, 100)
		pq = append(pq, segment{1, unit * 100})
		//already sorted

		//create as many 2e10 segments as possible
		for {
			//fmt.fmt.Println(pq)
			var P int
			fmt.Scanf("%d", &P)
			switch P {
			case -1:
				continue cases
			case -2:
				continue cases
			case -3:
				break cases
			default:
				playmove(&pq, P)
			}

			sort.Stable(&pq)
			biggest := pq[0]

			move := 0
			switch {
			case biggest.lenth() >= unit*3:
				//playing
				move = biggest.first + unit*2
				fmt.Println(move)
				playmove(&pq, move)
			case biggest.lenth() <= unit*2:
				count := 0
				for _, seg := range pq {
					if seg.lenth() >= unit {
						count++
					}
				}
				switch {
				case count%2 == 0:
					move = biggest.first
					fmt.Println(move)
					playmove(&pq, move)
				case biggest.lenth() > unit && count%2 == 1:
					move = biggest.first + 1
					fmt.Println(move)
					playmove(&pq, move)
				default: //biggest.lenth() == unit && count%2 == 1:
					move = biggest.first
					fmt.Println(move)
					playmove(&pq, move)
				}
			default: // unit*2 <biggest.lenth() <unit*3
				move = (biggest.first + biggest.last - unit) / 2
				fmt.Println(move)
				playmove(&pq, move)

			}
		}

	}
}

Voila! 500 Test cases out of 500! Only 12 points XDDDDDDD Omg…. Took me ages