|
|
If you can store the closest base in the same column for each cell, then can you process the solution for each row? Look up "convex hull trick". 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 .... DP. I select min answers from nearest cells to depth <= 3 (i.e. manhatten distance), calculated left-down to up-right.
Sorry for my wrong Englisish - answer from nearesr cels calculated from left-down to up-right and wise versa. 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 ??? 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); } puts(ans); 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 ? My solution jumped from TL 19 to AC in under 0.3s when i replaced output via printf with writing each digit of a number via putchar. That just blew my mind. |
|
|