Can anyone post the solution/editorial of “A Simple Game” (as it is removed from the contest)
I have tried using DP but it is inefficient
- What are some good problems for beginners on “Combinatorial Game Theory”?
The solution I came up with doesn’t involve dp, it’s more along the lines of Game theory. The basic idea is that in each row the of size n, the left n/2 elements are more in vicinity to Alice whereas the right n/2 elements are closer to Bob. If both are rational players they necessarily end up picking these elements. This can be justified by a very simple observation, let’s suppose Alice wants to get a better score than the current, it would require giving up one in closer vicinity to Alice in order to swap it with one with closer vicinity to Bob in some other row. This would never happen because Bob is the minimiser and holds by virtue of his vicinity, the ability to avoid it. This leaves us with only the odd length rows. Let us suppose there are k odd length rows, in each of them the middle element is up for grabs. Since Alice starts, he can choose the largest of them and Bob chooses the second largest middle element and so on. This goes on until all the middle elements are distributed.
5 Likes
thanks !!!