|
|
back to boardwhy wa on test 28 Posted by stelan 22 Sep 2007 23:04 4 memory or 30000 memory ? Re: why wa on test 28 Posted by svr 30 Sep 2007 17:01 I have WA 28 Also.
First 27 test I have passed with N=3 using Dejkstra.
But N==4 means very many possible states 27*27*27*27*4*50
and unprocessing. Re: why wa on test 28 optimal program use 4 or less cells Re: why wa on test 28 Posted by svr 1 Oct 2007 22:54 It's evident that using 5 cells we will have better solution for rather long strings, but jury's programm can't
work properly in this situation. Their hight level is 4 when they garantee right answer. I easy found Dejkstra's
solution for N=3. But for N=4 I tried DP,BFS with absolutely
bad characteristics. If solution depend on unproven statements which help diminish cardinality of set of possible states then it is unfair. Re: why wa on test 28 It's possible to work with DP over 27*27*27*4*50 states for 4 modifiable cells. Yes, this uses some interesting assumption but it is provable.
P.S: got AC
Edited by author 14.07.2008 02:52
Edited by author 14.07.2008 03:54 Re: why wa on test 28 Could you tell me what's your assumption?
I think DP should be 27^4 * 4 * 50,
and I assume that we just need modify 3 cells...
so I got wa#28~
could anybody help me?
sorry for my poor English. Re: why wa on test 28 I think you can assume that cell with position 0 <= i < 4 already have needed char. |
|
|
