10944 - Nuts for nuts..

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10944 - Nuts for nuts..

Post by rushel » Sun Oct 23, 2005 11:20 am

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sun Oct 23, 2005 12:20 pm

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

Post by rushel » Sun Oct 23, 2005 12:55 pm

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:

Post by Larry » Sun Oct 23, 2005 8:55 pm

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

Post by txandi » Sun Oct 23, 2005 9:18 pm


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

Thanks

Post by rushel » Mon Oct 24, 2005 3:14 pm

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: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Tue Oct 25, 2005 11:47 am

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:

Post by Larry » Tue Oct 25, 2005 1:59 pm

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

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Tue Oct 25, 2005 6:09 pm

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: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Tue Oct 25, 2005 9:32 pm

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 :D

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)

User avatar
danielrocha
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:

Post by danielrocha » Tue Oct 25, 2005 9:34 pm

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

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Wed Oct 26, 2005 2:26 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: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Wed Oct 26, 2005 2:53 pm

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)

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Wed Oct 26, 2005 3:09 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 :cry:
Jalal : AIUB SPARKS

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Wed Oct 26, 2005 3:26 pm

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

Post Reply

Return to “Volume 109 (10900-10999)”