## 10748 - Knights Roaming

Moderator: Board moderators

Pupirev Sergei
New poster
Posts: 24
Joined: Mon Feb 24, 2003 5:08 pm

### 10748 - Knights Roaming

Hi, everyone!
Can you give me some hints how to solve the problem. My algo is too slow. How can it be done?
Thx

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
The biggest problem is how to deduplicate the covered square quickly.
Use hashing to overcome this problem.
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Pupirev Sergei
New poster
Posts: 24
Joined: Mon Feb 24, 2003 5:08 pm
I used hash, but my program is too slow. I think a best algorithm should has about 100 000000 operations, isn't it? If you've done this problem can you send me solution? pserega@r66.ru

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
Pupirev Sergei wrote:I used hash, but my program is too slow. I think a best algorithm should has about 100 000000 operations, isn't it?
I don't know how you can come up with 100 000000 such a big number.
Consider we have 50 knights where every one can walk 50 steps.
Maximum number of covered square < 50 x 35000 = 1750000
Even you sort all the 1750000 squares in a qsort, the number of operation should be < 1 0000000 (although this is too slow to get accepted)
I use hashing to improve my sorting part to get AC.
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

ditrix
New poster
Posts: 33
Joined: Sat Mar 01, 2003 12:38 am
Location: Paris
I am wondering about my WA. Can anybody give me the answer for this test case (just for know if the mine is wrong or not) :

Code: Select all

``````30
1 1 50
2 2 50
3 3 50
...
29 29 50
30 30 50

0
``````
Some others cases?...
@+!
DitriX

tat tvam asi
New poster
Posts: 30
Joined: Sat Nov 30, 2002 1:04 pm
Lawrence!
it can be done with sorting.
i used hibrid sort: quicksort + insertion.
but hashing is better for this as your
result shows.
csaba noszaly

Pupirev Sergei
New poster
Posts: 24
Joined: Mon Feb 24, 2003 5:08 pm
I don't know how you can come up with 100 000000 such a big number.
Consider we have 50 knights where every one can walk 50 steps.
Maximum number of covered square < 50 x 35000 = 1750000
Even you sort all the 1750000 squares in a qsort, the number of operation should be < 1 0000000 (although this is too slow to get accepted)
But it's number of operations for one test case. We have 50 ones. Its tooooo slow!!!
Anyway, i've got AC (2.3 sec). But there are lots of tests where my program thinks for a minute.
For example, who can fit in time limit in this test:

Code: Select all

``````25
-855 820 24
335 898 33
863 616 24
-569 -592 28
-47 -151 25
-808 -895 33
-47 560 3
83 141 20
613 781 49
-890 -932 1
-566 -209 8
687 857 20
308 753 23
830 798 16
884 21 36
600 -673 18
-376 -287 23
462 -753 33
384 911 47
216 813 30
368 -1 42
843 896 13
789 525 16
-391 -330 26
-743 -806 16

29
55 46 4
-52 82 0
47 7 1
-75 61 25
-93 55 18
56 6 24
-34 -88 3
36 94 49
-64 -11 34
48 -61 8
-45 27 7
4 -9 22
74 -18 15
-92 58 40
-93 67 26
-62 -56 31
-42 58 26
-52 -88 41
94 -67 1
-25 -19 39
-87 63 7
84 -58 8
83 -43 19
-71 71 26
89 3 40
64 53 21
34 52 0
-64 -99 9
-32 38 7

... (repeat 25 times)
0
``````
In fact its too difficult, isn't it?

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
Just for a refernece, my code can solve the 29 kinghts case for 50 times within 10s on my PIII 500 PC.
I think the problemsetter writes "50 test cases" doesn't mean that he wants to challenge people for 50 such cases. Now the judge input can kill naive algorithm, I think that is enough.
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

wiltord
New poster
Posts: 16
Joined: Mon Oct 27, 2003 10:10 am
Location: SiChuan, China
I don't know how you can come up with 100 000000 such a big number.
Consider we have 50 knights where every one can walk 50 steps.
Maximum number of covered square < 50 x 35000 = 1750000
Even you sort all the 1750000 squares in a qsort, the number of operation should be < 1 0000000 (although this is too slow to get accepted)
I use hashing to improve my sorting part to get AC.
I'm interested in your algortihm, especially wonder why a sorting is needed? I solved this problem with a preprocess. In my preprocess, i use hash to store all the coordiates reachable from (0, 0) within the 50 steps limit. Then for each knight i enumerate its surrounding points, just refer to the hash we can get whether this point can be arrived within certain steps.[/quote]
my goal: master algorithms

wiltord
New poster
Posts: 16
Joined: Mon Oct 27, 2003 10:10 am
Location: SiChuan, China
I don't know how you can come up with 100 000000 such a big number.
Consider we have 50 knights where every one can walk 50 steps.
Maximum number of covered square < 50 x 35000 = 1750000
Even you sort all the 1750000 squares in a qsort, the number of operation should be < 1 0000000 (although this is too slow to get accepted)
I use hashing to improve my sorting part to get AC.
I'm interested in your algortihm, especially wonder why a sorting is needed? I solved this problem with a preprocess. In my preprocess, i use hash to store all the coordiates reachable from (0, 0) within the 50 steps limit. Then for each knight i enumerate its surrounding points, just refer to the hash we can get whether this point can be arrived within certain steps.
my goal: master algorithms

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
My idea is first dump out all the reachable squares by each knight, then use sorting to deduplicate. You can use other method to deduplicate.
Sorting is not fastet method, but it is quite easy to code.
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

wiltord
New poster
Posts: 16
Joined: Mon Oct 27, 2003 10:10 am
Location: SiChuan, China
.. wrote:My idea is first dump out all the reachable squares by each knight, then use sorting to deduplicate. You can use other method to deduplicate.
Sorting is not fastet method, but it is quite easy to code.
May i see you code? I can not imagine yours is so fast!
my goal: master algorithms

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
I think you should write to little joey now
I get my runtime now by
1. good hashing on the reachable square so that I can deduplicate quickly
2. heuristic to estimate if a knight will meet other knight on the board, if it won't meet other, just add the number of it's reachable sqaure directly to the answer.
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
What's a good way to hash? I use STL's <set>, but gets TLE. Should I write my own hash class?

wiltord
New poster
Posts: 16
Joined: Mon Oct 27, 2003 10:10 am
Location: SiChuan, China
Larry wrote:What's a good way to hash? I use STL's <set>, but gets TLE. Should I write my own hash class?
I also use STL's<set>, but it is not enough; notice this
.. wrote:2. heuristic to estimate if a knight will meet other knight on the board, if it won't meet other, just add the number of it's reachable sqaure directly to the answer.
combine set and the above impovement, you can avoid TLE.
my goal: master algorithms