10068 - The Treasure Hunt

[incin]

Ive tested my program, it seems to work fine. It does find a slightly different path, but it has the same calorie expenditure and goes to each treasure in the same order. anyone have a good test data? am I to assume the total calories might exceed 2^32? Any help would be greatly appreciated.

[Dmytro Chernysh]

10068 is famous NP-complete problem. So it can be solved only by backtracking in general (therefore, in O(n!)).
However, is it possible to solve it in O(2^n), because all the numbers are integers?

[junjieliang]

Could you tell me which NP problem is it? It doesn't look like any I know... and I think the trick to this problem is that there are at most 10 treasures...

Maybe I should try it...

[Dmytro Chernysh]

It's a special case of TSP - traveling salesman problem, which is very close to the Hamiltonian path, which is definitely NP-complete.

[Whinii F.]

But you should focus on that in this instance of the TSP problem, the solution space is very small so you can enumerate them all. I believe it will size about 20 * 20 * 2^10, so you can "brute-force" them all.

Good luck

edit) Yes, you can reduce it down to 12 * 2^10.

[bugzpodder]

here is my loop routine. if you could fix the PE, that'd be great
[cpp]

for(j=0;!cin.eof();j++){
if (j>0){
cout<<endl;
}

...

for (i=0;arr[ind]>0;i++)
cout<<ind<<" "<<arr[ind]<<endl;
while (cin.peek()=='\n' || cin.peek()=='\r') cin.ignore();
}
[/cpp]

[Joseph Kurniawan]

I think your P.E. is caused by the extra blank line your program output in the last output line.

Your output:

Code: Select all

output 
<blank line>
output
<blank line>
output 
<blank line>
output
<blank line>

while the correct one:

Code: Select all

output 
<blank line>
output
<blank line>
output 
<blank line>
output

See the difference? the blank line in the last line!!
Good Luck!!

[Joseph Kurniawan]

I think your P.E. is caused by the extra blank line your program output in the last output line.

Your output:

Code: Select all

output 
<blank line>
output
<blank line>
output 
<blank line>
output
<blank line>

while the correct one:

Code: Select all

output 
<blank line>
output
<blank line>
output 
<blank line>
output

This is the most common prob that causes P.E.
Or maybe you don't have to check for the /n and /r (since /n signals the end of input block). Try using gets instead of cin
Good Luck!!

[bugzpodder]

i tried like 10 different styles of outputs and got PE on every one of them :S

[dapumptu]

Need some hint with 10068 - The Treasure Hunt

I have no idea to solve this problem , any hints would be thankful !!!

[Dmytro Chernysh]

Take a look at http://online-judge.uva.es/board/viewtopic.php?t=3572

[dapumptu]

How to find shortest path to each nodes (start, treasures, end) ???
How to walk in maze and ignore the blocked block and finally find a way
to a node ???

Any hints would be thankful !!!!!

[angga888]

How to find shortest path to each nodes (start, treasures, end) ???
How to walk in maze and ignore the blocked block and finally find a way
to a node ???

You can use BFS.

Good Luck!
angga888

[SilentStrike]

I am doing a breadth first search in the original ascii map, and then making a 12x12 graph, and then doing a O(2^n*n^2) dp in the derived graph. I think the algorithm is fine. I get the correct answer (except for a different, but still seemingly valid path) for the sample input. Are there any special cases?

What is the correct answer for this input?

Code: Select all

2 2
ST
..
1
2 2
S#
#T
1
5 8
#......T
..#*..#.
..######
...*...#
####S.#*
5
10 50 50 100 30 80
10 10
#........*
..#*..#...
..######..
.......#..
####S..##.
.*.#...#..
.......#..
.##.#....#
.*.....#.#
....*..#.T
10
100 400 20 50 150 250 30 70 4 5
5 8
#......T
..#*..#.
..######
...**..#
####S.##
5
10 50 50 100 30 80
20 20
....................
.*..................
..........*.........
....................
....................
............*.......
....................
....................
..............*.....
.........S..........
....................
..............*.....
....................
....................
..*..........*......
....................
..........T.........
..*.................
....................
.....*..............
5
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
20 20
....................
.*..................
..........*.........
....................
....................
............*.......
....................
....................
..............*.....
.........S..........
....................
..............*.....
....................
....................
..*..........*......
....................
..........T.........
..*.................
....................
.....*......*.......
5
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0 0

My program produces the output

Code: Select all

Hunt #1
Minimum energy required = 1 cal
E

Hunt #2
The hunt is impossible.

Hunt #3
The hunt is impossible.

Hunt #4
Minimum energy required = 17539 cal
NWWWNNNEESPNWWSSSEEEESSSSSWSPNWWWPWNNNEPESEEEESEENNENNNNNPSSSSSWSSSSE

Hunt #5
Minimum energy required = 3915 cal
NPWPWWNNNEESPNEEEE

Hunt #6
Minimum energy required = 2453 cal
NNNNNNNNWWWWWWWWPEEEEEEEEESPEESSSPEESSSPSSSPWSSSPWWWWWWWWWWWPSSSPEEESSPNNNEEEEE

Hunt #7
Minimum energy required = 2952 cal
NNNNNNNNWWWWWWWWPEEEEEEEEESPEESSSPEESSSPSSSPWSSSPWWWWWWWWWWWPSSSPEEESSPEEEEEEEPNNNWW

[artem]

This is the output, which gives my AC program:

Code: Select all

Hunt #1
Minimum energy required = 1 cal
E

Hunt #2
The hunt is impossible.

Hunt #3
The hunt is impossible.

Hunt #4
Minimum energy required = 17539 cal
NWWWNNNEESPNWWSSSEEEESSSSSSWPNWWWPWNNENPESEEEESEENENNNNNNPSSSSSSWSSSE

Hunt #5
Minimum energy required = 2835 cal
NPWPWWNNNEESPNEEEE

Hunt #6
Minimum energy required = 2453 cal
NNNNNNNNWWWWWWWWPEEEEEEEEESPEESSSPEESSSPSSSPSSSWPWWWWWWWWWWWPSSSPEEESSPNNNEEEEE

Hunt #7
Minimum energy required = 2952 cal
NNNNNNNNWWWWWWWWPEEEEEEEEESPEESSSPEESSSPSSSPSSSWPWWWWWWWWWWWPSSSPEEESSPEEEEEEEPNNNWW

[/list]