10748 - Knights Roaming
Moderator: Board moderators
-
Destination Goa
- Experienced poster
- Posts: 123
- Joined: Thu Feb 10, 2005 4:46 am
There is a better way without any hashing at all (just got AC at 0.295 sec without special optimizations).
First generate all boards (do it only once), i.e. array a[51][201][201] or a[64][256][256] in my case
Then for every knight set y1=y-k*2, y2=y+k*2+1, x1=x-k*2, x2=x+k*2+1, these are [y1;y2), [x2;x2) limits for his board.
Now add control points on Y (start/stop) for each knight-board, and do same for X.
Now, sort both arrays of control points (Y points just tell if it is a start +1, or stop -1). X tells start/stop and also tells index of knight starting/stopping his board at this control absciss/ordinate. Both arrays will contain N*2 elements.
Roam through array of Y and see how many boards on Y slice are in action at given Y. When this number > 0, roam through X adding and deleting boards from doubly-linked lists as their corresponding control points appear (make sure they cross current Y slice). Now, being at some CY/CX and with linked list in according state, check if it's empty. If it is not empty, scan the square [CX;NX - NX;NY) where NX/NY are coordinates on next X/Y control points respectively (nothing happens in this sub-square - the set of boards covering it remains the same).
This way we don't check coordinates which are not needed to check and perform at O(N*log(n) + N*P) where P is the answer.
Testing that amount at Y is positive ensures that we skip empty rows without any operations. Testing that list is not empty ensures that we skip empty columns as well.
First generate all boards (do it only once), i.e. array a[51][201][201] or a[64][256][256] in my case
Then for every knight set y1=y-k*2, y2=y+k*2+1, x1=x-k*2, x2=x+k*2+1, these are [y1;y2), [x2;x2) limits for his board.
Now add control points on Y (start/stop) for each knight-board, and do same for X.
Now, sort both arrays of control points (Y points just tell if it is a start +1, or stop -1). X tells start/stop and also tells index of knight starting/stopping his board at this control absciss/ordinate. Both arrays will contain N*2 elements.
Roam through array of Y and see how many boards on Y slice are in action at given Y. When this number > 0, roam through X adding and deleting boards from doubly-linked lists as their corresponding control points appear (make sure they cross current Y slice). Now, being at some CY/CX and with linked list in according state, check if it's empty. If it is not empty, scan the square [CX;NX - NX;NY) where NX/NY are coordinates on next X/Y control points respectively (nothing happens in this sub-square - the set of boards covering it remains the same).
This way we don't check coordinates which are not needed to check and perform at O(N*log(n) + N*P) where P is the answer.
Testing that amount at Y is positive ensures that we skip empty rows without any operations. Testing that list is not empty ensures that we skip empty columns as well.