11311 - Exclusively Edible

[Tomato]

Trying to solve this problem using dp as follows:
d[n][m][pi][pj][player] - stores who is will win if we have field n x m, and the bad piece is at cell (pi,pj) and current turn to cut the cake is at the hensel (player = 0) and at gretel(player = 1). But I'm constantly getting WA. Could this approach be wrong?

[Robert Gerbicz]

Trying to solve this problem using dp as follows:
d[n][m][pi][pj][player] - stores who is will win if we have field n x m, and the bad piece is at cell (pi,pj) and current turn to cut the cake is at the hensel (player = 0) and at gretel(player = 1). But I'm constantly getting WA. Could this approach be wrong?

Is your program works for the sample input? I think it isn't very easy to avoid TLE by dp method. For example you can use:

Code: Select all

d[n][m][pi][pj][1]=1-d[n][m][pi][pj][0]

, so 4 dimensional array is also good.

If you see the times for this problem you'll observe that there are very fast times: 0.000 sec. There is an O(1) method for this problem, not dp.

[Tomato]

yes, it works on sample. thanks for a hint. I'll think of O(1) solution.

[roticv]

Think nim/nim sum.

[aerofoil.kite]

Code: Select all

**removed**

AC

[brianfry713]

Input:

Code: Select all

1
48 47 5 6

AC output:

Code: Select all

Gretel