11643  Knight Tour
Moderator: Board moderators

 Learning poster
 Posts: 72
 Joined: Tue May 30, 2006 5:57 pm
 Location: bangladesh
11643  Knight Tour
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
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
Last edited by mak(cse_DU) on Tue Sep 15, 2009 7:22 am, edited 1 time in total.
Mak
Help me PLZ!!
Help me PLZ!!
Re: 11643  Knight Tour
16 BFS() is the costly part. You can solve this problem with just 1 precalculated BFS().Complexity: 16 BFS() + O(16* 2^16).

 Learning poster
 Posts: 72
 Joined: Tue May 30, 2006 5:57 pm
 Location: bangladesh
Re: 11643  Knight Tour
Thanks sohel vai.
After your hints now I am getting WA.
someone please verify below input:
My WA output:
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
Mak
Help me PLZ!!
Help me PLZ!!
Re: 11643  Knight Tour
Can u give more hints? Why we need only 1 precalculated BFS?sohel wrote:16 BFS() is the costly part. You can solve this problem with just 1 precalculated BFS().
Thanks.
Re: 11643  Knight Tour
(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.
(2,4) > (4,2) is same as (2,2) > (4,4)
hope this will be enough.
Re: 11643  Knight Tour
I added this test case to your input and my AC output is
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
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
for hints look at this thread
http://forums.topcoder.com/?module=Thre ... 10&start=0

 Learning poster
 Posts: 72
 Joined: Tue May 30, 2006 5:57 pm
 Location: bangladesh
Re: 11643  Knight Tour
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.
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:btw you can try your input outputs at uvatoolkit.comCode: Select all
Case 1: 6
for hints look at this thread
http://forums.topcoder.com/?module=Thre ... 10&start=0
Mak
Help me PLZ!!
Help me PLZ!!

 Learning poster
 Posts: 72
 Joined: Tue May 30, 2006 5:57 pm
 Location: bangladesh
Re: 11643  Knight Tour
I have got AC.
My solution giving 10 for the below case.
but "tryit1's" solution giving 6.
which one is correct solution?
Actually judge data set was wrong.
They missed this case.
My solution giving 10 for the below case.
Code: Select all
4 2
1 1
1 4
which one is correct solution?
Actually judge data set was wrong.
They missed this case.
Mak
Help me PLZ!!
Help me PLZ!!
 emotional blind
 A great helper
 Posts: 383
 Joined: Mon Oct 18, 2004 8:25 am
 Location: Bangladesh
 Contact:
Re: 11643  Knight Tour
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.

 Learning poster
 Posts: 72
 Joined: Tue May 30, 2006 5:57 pm
 Location: bangladesh
Re: 11643  Knight Tour
Actually I wanted to say that there have mistakes.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.
Sorry for wrong English.
Thanks for clarification.
Mak
Help me PLZ!!
Help me PLZ!!

 New poster
 Posts: 48
 Joined: Sun Jun 22, 2014 6:14 am
Re: 11643  Knight Tour
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
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 highquality problems on our UVa.
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

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 11643  Knight Tour
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)?
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)?
Check input and AC output for thousands of problems on uDebug!

 New poster
 Posts: 48
 Joined: Sun Jun 22, 2014 6:14 am
Re: 11643  Knight Tour
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.
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.