Page 1 of 3
10068 - The Treasure Hunt
Posted: Wed Dec 25, 2002 4:10 am
by 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.
10068 - O(n!) or O(2^n)
Posted: Sun Jul 27, 2003 3:19 am
by 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?
Posted: Sun Jul 27, 2003 8:01 am
by 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...
Please...
Posted: Sun Jul 27, 2003 8:16 pm
by 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.
Posted: Sun Aug 03, 2003 3:41 pm
by 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.
10068 Tell me the Frequencies PE
Posted: Tue Sep 16, 2003 11:24 pm
by 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]
Posted: Wed Sep 17, 2003 3:52 pm
by 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!!
Posted: Wed Sep 17, 2003 3:58 pm
by 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!!
Posted: Wed Sep 17, 2003 11:37 pm
by bugzpodder
i tried like 10 different styles of outputs and got PE on every one of them :S
10068
Posted: Tue Feb 03, 2004 4:52 am
by dapumptu
Need some hint with 10068 - The Treasure Hunt
I have no idea to solve this problem , any hints would be thankful !!!
Posted: Tue Feb 03, 2004 4:54 am
by Dmytro Chernysh
Posted: Wed Feb 04, 2004 7:25 am
by 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 !!!!!
Posted: Thu Feb 12, 2004 10:04 am
by 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
10068 WA
Posted: Wed Jan 26, 2005 8:45 am
by 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
Posted: Sun Aug 07, 2005 1:19 pm
by 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]