Solving Problem , I got recurrence as f(n)= @f((n+1)/2) + @f(n-1) ,here @ denotes negation, f(x) is 0 if player with x stones loose and 1 if player left with x stones wins.As n can be high as 1018 so matrix exponentiation would do this,
| @ @ | x | f(n) | = | f(n+1) |
| 1 0 | | f(n/2+1) | | f(n) |
but I am unable to do algebra with this @ operation.
Auto comment: topic has been updated by tatya_bichu (previous revision, new revision, compare).
Auto comment: topic has been updated by tatya_bichu (previous revision, new revision, compare).
Suppose that the number of stones on the table before an m-turns game is represented by the integer vector X = [ x(1) x(2) .... x(m) ], where x(k) > 1 for k in [1,m]. The moves made by players Huseyn and Ziya can be represented as two m-bit vectors H = [ h(1) h(2) .... h(m) ] and Z = [ z(1) z(2) .... z(m) ], respectively. Suppose that the number of stones on the table after Huseyn and Ziya make the moves are represented as two integer vectors U = [ u(1) u(2) .... u(m) ] and V = [ v(1) v(2) .... v(m) ], respectively.
The initial condition can be represented as v(0) = N, and the winning condition for Ziya can be represented as v(m) = 1, where u(k) > 1 for k in [1,m].
The relation between the vectors X, H, Z, U, and V can be expressed as follows for k in [1,m].
x(k) = v(k-1)
u(k) = h(k) [ x(k)-1 ] + [ 1-h(k) ] [ ( x(k)+1 ) div 2 ]
v(k) = z(k) [ u(k)-1 ] + [ 1-z(k) ] [ ( u(k)+1 ) div 2 ]
The answer to the problem is Yes if the winning condition can be satisfied for any m-bit vector H. Otherwise, the answer is No.
Finally, it should be noted that as X is equal to V shifted by one turn, the first and the third equations can alternatively be combined in order to eliminate V as
x(k+1) = z(k) [ u(k)-1 ] + [ 1-z(k) ] [ ( u(k)+1 ) div 2 ]
In this case, the initial condition is x(1) = N and the winning condition for m-turns game is x(m+1)=1.
P.S. The inverse relation can also be expressed by reversing the k-axis as
u(k) = z(k) [ x(k)+1 ] + [ 1-z(k) ] [ 2 x(k)-t(k) ]
x(k+1) = h(k) [ u(k) + 1 ] + [ 1-h(k) ] [ 2 u(k)-w(k) ]
where T = [ t(1) t(2) .... t(m) ] and W = [ w(1) w(2) .... w(m) ] are two m-bit vectors.
The initial condition in the inverse relation is x(1) = 1, the final condition is x(m) = N, and u(k) > 1 for all k in [1,m].
As I'm an author of the problem I can give you some hints. We can do simply dynamic-programming for O(N) solution as you did:
Now, notice that for all even i, dp[i] = 1. So, for finding answer for odd i, we need to calculate just dp[(i + 1) / 2] as i - 1 is even and dp[i - 1] = 1.
You do not need any matrix exponentiation, just a simple 1 line recursion will do it.
Yeah , tag was trap, thx!