Page 1 of 1

11643 - Knight Tour

Posted: Fri Aug 28, 2009 11:38 am
by mak(cse_DU)
Give me hints to solve this problem.
My solution is TLE.
Complexity: 16 BFS() + O(16*16 * 2^16).

Some optimization may be helpful. But i am unable to find out.
PLEASE help me.

Thanks in advance

Re: 11643 - Knight Tour

Posted: Fri Aug 28, 2009 12:37 pm
by sohel
Complexity: 16 BFS() + O(16* 2^16).
16 BFS() is the costly part. You can solve this problem with just 1 precalculated BFS().

Re: 11643 - Knight Tour

Posted: Fri Aug 28, 2009 6:18 pm
by mak(cse_DU)
Thanks sohel vai.

After your hints now I am getting WA.
someone please verify below input:

Code: Select all

9
4 2
1 1
1 4

42 3
2 2
2 3
1 1
963 15
6 6
13 2
12 2
3 11
7 13
10 7
4 3
8 8
12 7
6 9
7 3
4 12
8 10
5 3
10 11
704 7
3 5
3 6
5 1
2 2
2 5
5 1
1 4
724 7
2 6
5 4
2 1
7 2
4 4
4 1
6 7
891 10
1 1
2 7
9 4
4 10
5 5
1 7
7 7
9 2
10 5
4 7
538 14
11 5
8 12
8 4
7 6
5 11
11 6
1 6
4 10
5 3
6 13
6 10
7 2
5 5
3 6
356 3
2 1
2 3
2 3
942 5
1 2
2 3
3 3
3 3
4 4

My WA output:

Code: Select all

Case 1: 10
Case 2: 8
Case 3: 34
Case 4: 14
Case 5: 18
Case 6: 24
Case 7: 26
Case 8: 4
Case 9: 8

Re: 11643 - Knight Tour

Posted: Fri Aug 28, 2009 8:27 pm
by _richard_
sohel wrote:16 BFS() is the costly part. You can solve this problem with just 1 precalculated BFS().
Can u give more hints? Why we need only 1 precalculated BFS?

Thanks.

Re: 11643 - Knight Tour

Posted: Sat Aug 29, 2009 1:34 am
by crip121
(2,2) -> (4,4) is same as (1,1) -> (3,3)

(2,4) -> (4,2) is same as (2,2) -> (4,4)

hope this will be enough.

Re: 11643 - Knight Tour

Posted: Sat Aug 29, 2009 9:08 pm
by tryit1
I added this test case to your input and my AC output is

Code: Select all

5 8 1 1 2 2 4 4 5 5 1 5 2 4 5 1 4 2


Case 1: 6
Case 2: 8
Case 3: 34
Case 4: 12
Case 5: 18
Case 6: 24
Case 7: 26
Case 8: 4
Case 9: 6
Case 10: 16
btw you can try your input outputs at uvatoolkit.com

for hints look at this thread
http://forums.topcoder.com/?module=Thre ... 10&start=0

Re: 11643 - Knight Tour

Posted: Mon Sep 14, 2009 1:17 pm
by mak(cse_DU)
Thanks "tryit1" for your reply.

I am confused about the first case.
4 2 (4x4)
1 1
1 4

how can the output be only 6?
In 4x4 matrix the cost matrix from 1,1 position is below

4| 5 2 3 2
3| 2 1 4 3
2| 3 4 1 2
1| 0 3 2 5
------------------
--> 1 2 3 4

That means from (1,1)-> (1,4) cost is 5.
so total cost of tour should be 10.

Am I right?
Thanks in advance.
tryit1 wrote:

Code: Select all

Case 1: 6
btw you can try your input outputs at uvatoolkit.com

for hints look at this thread
http://forums.topcoder.com/?module=Thre ... 10&start=0

Re: 11643 - Knight Tour

Posted: Tue Sep 15, 2009 7:18 am
by mak(cse_DU)
I have got AC.
My solution giving 10 for the below case.

Code: Select all

4 2
1 1
1 4
but "tryit1's" solution giving 6.

which one is correct solution?

Actually judge data set was wrong.
They missed this case.

Re: 11643 - Knight Tour

Posted: Fri Sep 18, 2009 3:52 pm
by emotional blind
mak(cse_DU) wrote:Actually judge data set was wrong.
They missed this case.

One particular case or one critical case is not covered by judge data does not imply that judge data set is wrong. I should admit that judge data could have been stronger, but I merely believe data is correct.

Re: 11643 - Knight Tour

Posted: Fri Sep 18, 2009 4:34 pm
by mak(cse_DU)
emotional blind wrote:
mak(cse_DU) wrote:Actually judge data set was wrong.
They missed this case.

One particular case or one critical case is not covered by judge data does not imply that judge data set is wrong. I should admit that judge data could have been stronger, but I merely believe data is correct.
Actually I wanted to say that there have mistakes.
Sorry for wrong English.
Thanks for clarification.

Re: 11643 - Knight Tour

Posted: Sun Jun 22, 2014 6:19 am
by red_apricot
Sohel is undoubtedly a great contributor to our community, but this particular problem's data is wrong. The output for the above case should actually be

Code: Select all

Case 1: 10
Case 2: 8
Case 3: 32
Case 4: 14
Case 5: 18
Case 6: 23
Case 7: 26
Case 8: 6
Case 9: 6
Case 10: 16
Since many people may have wasted their time on this one, I move that the solutions should be rejudged, in order for the incorrect solutions to be unaccepted again, otherwise it is misleading. And we need only high-quality problems on our UVa.

Re: 11643 - Knight Tour

Posted: Tue Jun 24, 2014 1:44 am
by brianfry713
Case 4, 8, and 9 from this thread have duplicate interesting cells. The judge's input contains no cases with duplicates.
Case 1 should be 10.
Can you explain how you got 32 for case 3 (I got 34), and 23 for case 6 (I got 24)?

Re: 11643 - Knight Tour

Posted: Tue Jun 24, 2014 11:59 am
by red_apricot
Yes, cases 3 and 6 should be 34 and 24, indeed -- my bad! Still WA. Sent you my code as PM, in case you are getting WA too. It may help at least one of us :)
EDIT: Just got AC. The strategy was to actually perform the bfs if the manhattan distance between two cells is less than a certain number.