10748 - Knights Roaming

[Pupirev Sergei]

Hi, everyone!
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.

[Pupirev Sergei]

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 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.

[ditrix]

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?...

[tat tvam asi]

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]

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?

[..]

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.

[wiltord]

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]

[wiltord]

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 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.

[wiltord]

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!
Please send to wiltord@eyou.com, thanks!

[..]

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.

[Larry]

What's a good way to hash? I use STL's <set>, but gets TLE. Should I write my own hash class?

[wiltord]

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

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.