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) »

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

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

Re: 11643 - Knight Tour

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

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) »

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_ »

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 »

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

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

Re: 11643 - Knight Tour

Post 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

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) »

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) »

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

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 »

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) »

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 »

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 »

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 »

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)”