11643 - Knight Tour

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

Moderator: Board moderators

Post Reply
mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm
Location: bangladesh

11643 - Knight Tour

Post by mak(cse_DU) » Fri Aug 28, 2009 11:38 am

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
Last edited by mak(cse_DU) on Tue Sep 15, 2009 7:22 am, edited 1 time in total.
Mak
Help me PLZ!!

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 11643 - Knight Tour

Post by sohel » Fri Aug 28, 2009 12:37 pm

Complexity: 16 BFS() + O(16* 2^16).
16 BFS() is the costly part. You can solve this problem with just 1 precalculated BFS().

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm
Location: bangladesh

Re: 11643 - Knight Tour

Post by mak(cse_DU) » Fri Aug 28, 2009 6:18 pm

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
Mak
Help me PLZ!!

_richard_
New poster
Posts: 1
Joined: Fri Aug 28, 2009 8:24 pm

Re: 11643 - Knight Tour

Post by _richard_ » Fri Aug 28, 2009 8:27 pm

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.

crip121
New poster
Posts: 29
Joined: Tue Jul 08, 2008 9:04 pm

Re: 11643 - Knight Tour

Post by crip121 » Sat Aug 29, 2009 1:34 am

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

User avatar
tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

Re: 11643 - Knight Tour

Post by tryit1 » Sat Aug 29, 2009 9:08 pm

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

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm
Location: bangladesh

Re: 11643 - Knight Tour

Post by mak(cse_DU) » Mon Sep 14, 2009 1:17 pm

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
Mak
Help me PLZ!!

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm
Location: bangladesh

Re: 11643 - Knight Tour

Post by mak(cse_DU) » Tue Sep 15, 2009 7:18 am

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.
Mak
Help me PLZ!!

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Re: 11643 - Knight Tour

Post by emotional blind » Fri Sep 18, 2009 3:52 pm

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.

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm
Location: bangladesh

Re: 11643 - Knight Tour

Post by mak(cse_DU) » Fri Sep 18, 2009 4:34 pm

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.
Mak
Help me PLZ!!

red_apricot
New poster
Posts: 48
Joined: Sun Jun 22, 2014 6:14 am

Re: 11643 - Knight Tour

Post by red_apricot » Sun Jun 22, 2014 6:19 am

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.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11643 - Knight Tour

Post by brianfry713 » Tue Jun 24, 2014 1:44 am

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)?
Check input and AC output for thousands of problems on uDebug!

red_apricot
New poster
Posts: 48
Joined: Sun Jun 22, 2014 6:14 am

Re: 11643 - Knight Tour

Post by red_apricot » Tue Jun 24, 2014 11:59 am

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.

Post Reply

Return to “Volume 116 (11600-11699)”