10944 - Nuts for nuts..

[rushel]

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.

[Larry]

What do you do after you do the BFS? Do you know it's a TSP problem?

[rushel]

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

[Larry]

Well, you can solve it by using DP, since the number of items isn't too high..

[txandi]

This could help:

http://irl.eecs.umich.edu/jamin/courses ... ture22.pdf

[rushel]

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

[Dominik Michniewski]

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

[Larry]

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]

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]

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

[danielrocha]

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

[CodeMaker]

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

[Dominik Michniewski]

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

[CodeMaker]

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

[mf]

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