## 10944 - Nuts for nuts..

Moderator: Board moderators

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

### 10944 - Nuts for nuts..

I use bfs to solve this problem can anyone please give me some test data

Larry
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?

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

### TSP

Thanks Larry.
I know its a TSP problem but i was worried about TLE. Can u give me a refrence to TSP algorithm

Larry
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..

txandi
New poster
Posts: 25
Joined: Sun Feb 29, 2004 2:06 am

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

### Thanks

Thanks to Larry and txandi for helping me. I am finding the link very useful thanks once again both of u.

Dominik Michniewski
Guru
Posts: 832
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
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)

Larry
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..

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
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 under-estimated future cost is not less than minimum cost. The second one is not to visit the k-th nut from the i-th nut if there is a j-th nut such that the j-th nut is not visited yet and cost(i->j)+cost(j->k)<=cost(i->k).

Dominik Michniewski
Guru
Posts: 832
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
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)

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://acmicpc-live-archive.uva.es/nuev ... php?p=3153
Daniel
UFRN HDD-1
Brasil

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
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.

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

Dominik Michniewski
Guru
Posts: 832
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
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)

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
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
Jalal : AIUB SPARKS

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
CodeMaker wrote:1st of all, does x=column and y=row
or is it opposite?
The first integer is the height of the map (no. of rows), the second one is the width (no of columns.)

For your input, my program prints:

Code: Select all

``````76
19
12
26
12``````