10748  Knights Roaming
Moderator: Board moderators

 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
Can you give me some hints how to solve the problem. My algo is too slow. How can it be done?
Thx
The biggest problem is how to deduplicate the covered square quickly.
Use hashing to overcome this problem.
Use hashing to overcome this problem.
My signature:
 Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.  I HATE testing account.
 Don't send me source code for debug.

 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
I don't know how you can come up with 100 000000 such a big number.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?
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:
 Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.  I HATE testing account.
 Don't send me source code for debug.
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) :
Some others cases?...
Code: Select all
30
1 1 50
2 2 50
3 3 50
...
29 29 50
30 30 50
0
@+!
DitriX
DitriX

 New poster
 Posts: 30
 Joined: Sat Nov 30, 2002 1:04 pm

 New poster
 Posts: 24
 Joined: Mon Feb 24, 2003 5:08 pm
But it's number of operations for one test case. We have 50 ones. Its tooooo slow!!!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)
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
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.
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:
 Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.  I HATE testing account.
 Don't send me source code for debug.
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]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 goal: master algorithms
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.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 goal: master algorithms
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.
Sorting is not fastet method, but it is quite easy to code.
My signature:
 Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.  I HATE testing account.
 Don't send me source code for debug.
May i see you code? I can not imagine yours is so fast!.. 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.
Please send to wiltord@eyou.com, thanks!
my goal: master algorithms
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.
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:
 Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.  I HATE testing account.
 Don't send me source code for debug.
I also use STL's<set>, but it is not enough; notice thisLarry wrote:What's a good way to hash? I use STL's <set>, but gets TLE. Should I write my own hash class?
combine set and the above impovement, you can avoid TLE... 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.
my goal: master algorithms