10748 - Knights Roaming

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10748 - Knights Roaming

Post by Pupirev Sergei » Sun Oct 17, 2004 8:15 pm

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

Post by .. » Sun Oct 17, 2004 9:09 pm

The biggest problem is how to deduplicate the covered square quickly.
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.

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

Post by Pupirev Sergei » Mon Oct 18, 2004 4:50 am

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

Post by .. » Mon Oct 18, 2004 5:01 am

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

ditrix
New poster
Posts: 33
Joined: Sat Mar 01, 2003 12:38 am
Location: Paris

Post by ditrix » Mon Oct 18, 2004 10:59 am

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

Post by tat tvam asi » Mon Oct 18, 2004 11:56 am

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

Post by Pupirev Sergei » Mon Oct 18, 2004 4:15 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

Post by .. » Mon Oct 18, 2004 5:22 pm

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

wiltord
New poster
Posts: 16
Joined: Mon Oct 27, 2003 10:10 am
Location: SiChuan, China

Post by wiltord » Tue Oct 19, 2004 11:37 am

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

Post by wiltord » Tue Oct 19, 2004 11:38 am

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

Post by .. » Tue Oct 19, 2004 11:46 am

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

wiltord
New poster
Posts: 16
Joined: Mon Oct 27, 2003 10:10 am
Location: SiChuan, China

Post by wiltord » Tue Oct 19, 2004 4:37 pm

.. 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!
Please send to wiltord@eyou.com, thanks!
my goal: master algorithms

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Tue Oct 19, 2004 5:22 pm

I think you should write to little joey now :wink:
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.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Wed Oct 20, 2004 12:53 am

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

Post by wiltord » Wed Oct 20, 2004 5:43 am

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

Post Reply

Return to “Volume 107 (10700-10799)”