I am struggling to get the optimal subtructure to solve the problem i.e. the recurrence that has to be followed and upon which Dynamic Programming Solution can be build for optimizing the Time Complexity.
Suppose A and B have 2 kinds of Stones. There are A stones of the first type and B of the second type. They decide to play a game according to rules such in each turn one of the following valid moves can be done:
They have to pick atleast one Stone in each turn. Whoever makes the last move wins the game. Both play optimally. However while telling the rules of the competition, Alice cheated a bit to ensure that she wins the game by deciding who will take the first move.
Given the Stones, determine if Alice takes the first move or not.
Posting this as a separate answer because it so different from the other. I'll leave that answer too because this technique is probably not very useful for similar problems.
By running an example with 10 stones of each type by hand, I found that the only losing positions are (1, 2), (3, 5), (4, 7), (6, 10)
. There is a search engine for integer sequences where one can search for known formulas given the start of the sequence, called OEIS
So there is sequence A072061, which matches this one. This teaches us two things:
(a(2*k), a(2*k+1))
for some integer k
and a(n) = n*(1+(-1)^n)/4+floor((2*n+1-(-1)^n)*(1+sqrt(5))/8)
So to determine if Alice should start, you can compute if (A, B)
is a losing position using the given formula.