|
|
Show all threads Hide all threads Show all messages Hide all messages | Hint | Md sabbir Rahman | 1976. Game Optimization | 14 Nov 2018 20:32 | 1 | Hint Md sabbir Rahman 14 Nov 2018 20:32 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". | Easy ? | ZamNick | 1976. Game Optimization | 18 Jan 2014 15:30 | 6 | Easy ? 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 .... 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 ? | How do i wrote integers | Chitanda Eru | 1976. Game Optimization | 9 Dec 2013 18:46 | 1 | 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. | some test data added? | suiyuan | 1976. Game Optimization | 9 Aug 2013 19:37 | 1 | |
|
|
|