10944  Nuts for nuts..
Moderator: Board moderators
10944  Nuts for nuts..
I use bfs to solve this problem can anyone please give me some test data
It will be very helpful for me. Please help if possible.
It will be very helpful for me. Please help if possible.

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
What do you do after you do the BFS? Do you know it's a TSP problem?
Check out http://www.algorithmist.com !

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
Well, you can solve it by using DP, since the number of items isn't too high..
Check out http://www.algorithmist.com !

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
When I try to use DP on this problem I got MLE every time. I'm stucked.
Could anyone help me? Is this possible to use only O(N^2) memory for this problem ? I think, that we must check every permutation and store partially results for future use ... But this approach give us MLE of course. How can I shrink memory usage??
Best regards
DM
Could anyone help me? Is this possible to use only O(N^2) memory for this problem ? I think, that we must check every permutation and store partially results for future use ... But this approach give us MLE of course. How can I shrink memory usage??
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
hey Dominik, there's only 16 crucial points, so you can memoize O(N*2^N), which is 16*2^16... and should be better than enough..
Check out http://www.algorithmist.com !
My solution tries all possible visiting orders of the nuts by a DFS with 2 hueristics to cut off. The first one is to cut off if the current cost plus the underestimated future cost is not less than minimum cost. The second one is not to visit the kth nut from the ith nut if there is a jth nut such that the jth nut is not visited yet and cost(i>j)+cost(j>k)<=cost(i>k).

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
Thanks Larry for help  I found my mistake: I generated in queue some states more than once.
But now I have other problem  I got WA I try to fight with this tomorrow
Best regards
DM
But now I have other problem  I got WA I try to fight with this tomorrow
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)
 danielrocha
 New poster
 Posts: 44
 Joined: Sun Apr 27, 2003 3:17 am
 Location: Rio Grande do Norte  Brazil
 Contact:
On the contest day we used a memoization technique like the one described above  O(N^2*2^N), and it got AC with 0.5s. This is a very interesting algorithm, and it should be able to solve problems up to 20 nodes, like this one:
3153  Long Night of Museums
http://acmicpclivearchive.uva.es/nuev ... php?p=3153
3153  Long Night of Museums
http://acmicpclivearchive.uva.es/nuev ... php?p=3153
Daniel
UFRN HDD1
Brasil
UFRN HDD1
Brasil
 CodeMaker
 Experienced poster
 Posts: 183
 Joined: Thu Nov 11, 2004 12:35 pm
 Location: AIUB, Bangladesh
Hi, I need some help.
1st of all, does x=column and y=row
or is it opposite?
next if anyone can give me some test data, that will help.....
i m getting wa for some reason. i cant find the problem.
thanks.
1st of all, does x=column and y=row
or is it opposite?
next if anyone can give me some test data, that will help.....
i m getting wa for some reason. i cant find the problem.
thanks.
Code: Select all
input:
20 20
#..................#
....................
....................
....................
....................
....................
....................
....................
....................
....................
.........L..........
....................
....................
....................
....................
....................
....................
....................
....................
#..................#
11 7
.....L.....
...........
...........
...........
#....#....#
...........
...........
10 10
..........
.....#....
....#.#...
...#...#..
..#.....#.
..........
.....L....
..........
..........
..........
10 10
..........
..#....#..
..#....#..
..#....#..
..##L###..
..#....#..
..#....#..
..#....#..
..........
..........
5 5
L....
.....
..#.#
.....
#....
Code: Select all
my output:
76
20
29
69
12
Last edited by CodeMaker on Wed Oct 26, 2005 2:58 pm, edited 1 time in total.
Jalal : AIUB SPARKS

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
Your case with H shape is incorrect  contains more items that maximum.
I'm got WA on this problem too ...
And I think, that first two numbers should be 7 11, not 11 7 (because input gives it to you as rows and columns).
Best regards
DM
I'm got WA on this problem too ...
And I think, that first two numbers should be 7 11, not 11 7 (because input gives it to you as rows and columns).
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)
 CodeMaker
 Experienced poster
 Posts: 183
 Joined: Thu Nov 11, 2004 12:35 pm
 Location: AIUB, Bangladesh
ya, sorry for that, i know there will be 15 items at max. actually i am trying to find out is my solution gives optimal cost or not. so i was trying big dataset.
it is very hard all the time to test the output by hand. every thing i try gives correct cost[ how can i be sure, i tried my best to count it by hand]
it will be helpful if anyone can give some critical dataset. u know... i m trying to figure the error
it is very hard all the time to test the output by hand. every thing i try gives correct cost[ how can i be sure, i tried my best to count it by hand]
it will be helpful if anyone can give some critical dataset. u know... i m trying to figure the error
Jalal : AIUB SPARKS
The first integer is the height of the map (no. of rows), the second one is the width (no of columns.)CodeMaker wrote:1st of all, does x=column and y=row
or is it opposite?
For your input, my program prints:
Code: Select all
76
19
12
26
12