## 10068 - The Treasure Hunt

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

Moderator: Board moderators

incin
New poster
Posts: 3
Joined: Tue Dec 24, 2002 5:52 pm

### 10068 - The Treasure Hunt

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
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

### 10068 - O(n!) or O(2^n)

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
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore
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
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

### Please...

It's a special case of TSP - traveling salesman problem, which is very close to the Hamiltonian path, which is definitely NP-complete.
Last edited by Dmytro Chernysh on Tue Feb 03, 2004 4:55 am, edited 1 time in total.

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
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.
JongMan @ Yonsei

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

### 10068 Tell me the Frequencies PE

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
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia
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!!
There are 3 things one need to be successful : motivation, ability and chance. And if you're a believer, make it four : God's will.

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia
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!!
There are 3 things one need to be successful : motivation, ability and chance. And if you're a believer, make it four : God's will.

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm
i tried like 10 different styles of outputs and got PE on every one of them :S

dapumptu
New poster
Posts: 5
Joined: Tue Nov 25, 2003 3:30 pm

### 10068

Need some hint with 10068 - The Treasure Hunt

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

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

dapumptu
New poster
Posts: 5
Joined: Tue Nov 25, 2003 3:30 pm
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
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia
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
New poster
Posts: 22
Joined: Fri Jan 04, 2002 2:00 am

### 10068 WA

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
New poster
Posts: 17
Joined: Thu Jun 09, 2005 5:01 pm
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]