11643 - Knight Tour

[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

[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)]

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

[_richard_]

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]

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

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

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.

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

[emotional blind]

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

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.

[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]

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

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