Page 1 of 1
11311 - Exclusively Edible
Posted: Sun Oct 21, 2007 11:10 am
by 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?
Re: 11311 - EXCLUSIVELY EDIBLE
Posted: Sun Oct 21, 2007 11:35 am
by Robert Gerbicz
Tomato wrote: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.
Posted: Sun Oct 21, 2007 11:41 am
by Tomato
yes, it works on sample. thanks for a hint. I'll think of O(1) solution.
Re: 11311 - Exclusively Editable
Posted: Fri Jul 17, 2009 9:27 am
by roticv
Think nim/nim sum.
Re: 11311 - Exclusively Editable
Posted: Mon Feb 06, 2012 7:35 am
by aerofoil.kite
AC
Re: 11311 - Exclusively Editable
Posted: Wed Feb 22, 2012 8:15 pm
by brianfry713