ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1976. Game Optimization

Easy ?
Posted by ZamNick 17 Jan 2014 22:26
When I've written bfs I've got TL29, when I've written Kd-tree, I've got TL26 ....
Hey, guys, give me some hints how to solve this problem, please ....
Re: Easy ?
Posted by shad 17 Jan 2014 22:58
DP. I select min answers from nearest cells to depth <= 3 (i.e. manhatten distance), calculated left-down to up-right.
Re: Easy ?
Posted by shad 17 Jan 2014 23:11
Sorry for my wrong Englisish - answer from nearesr cels calculated from left-down to up-right and wise versa.
Re: Easy ?
Posted by ZamNick 18 Jan 2014 02:12
Ha-ha ..... my DP give me WA5 :)
Can you explain me how to build DP in this problem, what the base of DP and so on ???
Re: Easy ?
Posted by shad 18 Jan 2014 10:47
In direction :
for(j=2; j<m1; j++){
for(i=2; i<n1; i++){

look best from cells in quadrant :
int n2 = i-3, m2 = j-3;
for(int i1=i; i1>n2; --i1){
for(int j1=j; j1>m2; --j1){
...
b[i][j] = best;
and repeat 4 times for all 4 directins and corresponding quadrant.