10068 - The Treasure Hunt
Moderator: Board moderators
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.
-
- 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?
However, is it possible to solve it in O(2^n), because all the numbers are integers?
-
- Experienced poster
- Posts: 169
- Joined: Wed Oct 31, 2001 2:00 am
- Location: Singapore
-
- 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.
-
- 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]
[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]
-
- 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:
while the correct one:
See the difference? the blank line in the last line!!
Good Luck!!
Your output:
Code: Select all
output
<blank line>
output
<blank line>
output
<blank line>
output
<blank line>
Code: Select all
output
<blank line>
output
<blank line>
output
<blank line>
output
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.
-
- 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:
while the correct one:
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!!
Your output:
Code: Select all
output
<blank line>
output
<blank line>
output
<blank line>
output
<blank line>
Code: Select all
output
<blank line>
output
<blank line>
output
<blank line>
output
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.
-
- Experienced poster
- Posts: 147
- Joined: Fri Jun 13, 2003 10:46 pm
-
- Experienced poster
- Posts: 146
- Joined: Sat Apr 26, 2003 2:51 am
Take a look at http://online-judge.uva.es/board/viewtopic.php?t=3572
-
- 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?
My program produces the output
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
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
This is the output, which gives my AC program:
[/list]
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