Can anyone help me with some advice or some resource on how to tackle these OPTIMAL STRATEGY questions,
To solve A simple game I learned a lot of game theory ,But on seeing the solutions i felt heart broken
can anyone help me out to understand how to approach such problems
1 Like
As with anything else, PRACTICE.
There are lots of problems on Games and Game Theory.
Codeforces - Problemset - Codeforces
Hackerrank - Solve Algorithms | HackerRank
SPOJ - Sphere Online Judge (SPOJ)
Codechef -
Game Theory Coding Problems - CodeChef
3 Likes
Any materal/docs for learning about Game Theory ? Please share
1 Like
The best materials are probably the past questions and editorials…
Btw for game related questions think from bottom, usually there are winning and losing states. And each player wants to throw other player into a losing state. Think using this for any new problem
4 Likes
my approach
suppose in total there are k (considering all rows together)coins , so if k is even p1 will take k/2 coins and p2 will take k/2 coins ,but if k is odd p1 will get k/2+1 coins.
so for each particular row we can imagine all left elements from middle belong to p1 and right to p2 and posession of middle element depends upon who started that row first,also for imagination part why i assumed boundary division was because ,proof by contradiction -
suppose p1 enters p2 area than p2 also must enter p1 area for some row so as to get k/2-1 coins for p2 and k/2 +1 coins for p1 ,and why will p1 enter p2 area , because there is larger element,so if there is larger element on right side than p2 will defend it as he is playing optimally, so he wont let p1 take that away ,so p1 will operate on left side and p2 on right side , so middle elements will make difference and it goes to player who start that row first, so p1 for max profit will select row with greatest middle element and now knowing p1 has selected largest middle valued row, p2 should select second largest row for himself, so it will continue like this.
2 Likes
I agree with @s5960r, the best materials are questions themselves. Try to solve them, if stuck, look at the editorial. The way I see it, the more problems you solve, the better you become at picking up patterns and if you have solved a large number of problems, you may even realise that ‘Oh, I have solved the problem somewhere… and the solution goes like…’. The fact that the problem was similar to a Codeforces problem and it being similar was purely coincidental and unintentional tells that if you solve a large number of problem, you may eventually start finding similarity within problems 
Anyway, on a more serious note- Many(if not all) Game-Theory problems eventually boils down to Grundy Numbers and Game of Nim. You may want to have a look at these topics-
3 Likes
you got to check check for not only middle element but for the sum of k/2+1
for example there are two rows
1 2 5 2 2
6 4 7
if you only check for larger mid term you’ll get wrong answer
assuming
1 2 5 2 2 (5coins in row 1) and same for 6 4 7(3 coins in row2)
p1 will get(1+2+6) because it belongs to p1 region and (+5) because it is largest middle value so answer will be(1+2+6+5=14) , i got AC using this approach.