ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
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.
print answer :
    for(i=2; i<n1; i++){
        int sh=0;
        for(j=2; j<m1; j++){
            P p=P(i,j);
            int d = p.dist(b[i][j]);
            sh += sprintf(ans+sh,"%d ", d);
//            printf("%d ", d);
Re: Easy ?
Posted by ZamNick 18 Jan 2014 15:30
And finally, I've got AC .... Thanks for your help, guy, you've taught me cool trick .... But, nevertheless, can you explain, why it is work, when we look in 4 direction, maybe 3 is enough (but it's not enough, 'cause I've got WA :)  ) ? Do you have mathematical evidence ?