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

Post by incin » Wed Dec 25, 2002 4:10 am

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)

Post by Dmytro Chernysh » Sun Jul 27, 2003 3:19 am

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

Post by junjieliang » Sun Jul 27, 2003 8:01 am

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... :wink:

Maybe I should try it...

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

Please...

Post by Dmytro Chernysh » Sun Jul 27, 2003 8:16 pm

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:

Post by Whinii F. » Sun Aug 03, 2003 3:41 pm

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

Post by bugzpodder » Tue Sep 16, 2003 11:24 pm

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

Post by Joseph Kurniawan » Wed Sep 17, 2003 3:52 pm

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

Post by Joseph Kurniawan » Wed Sep 17, 2003 3:58 pm

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

Post by bugzpodder » Wed Sep 17, 2003 11:37 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

Post by dapumptu » Tue Feb 03, 2004 4:52 am

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

Post by Dmytro Chernysh » Tue Feb 03, 2004 4:54 am


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

Post by dapumptu » Wed Feb 04, 2004 7:25 am

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

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Thu Feb 12, 2004 10:04 am

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

Post by SilentStrike » Wed Jan 26, 2005 8:45 am

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

Post by artem » Sun Aug 07, 2005 1:19 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]

Post Reply

Return to “Volume 100 (10000-10099)”