10605 - Mines For Diamonds

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

Moderator: Board moderators

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa »

Hmm... Either test data is weak or there's indeed a polynom on number of diamonds and number of possible entrances.
To be the best you must become the best!

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

I guess test data is weak (but I don't have the test data on my computer here, so I can't check). With how I understood the problem first, greedy strategies seemed likely to fail on random inputs. After I realised I understood the problem wrong, I didn't change the input.
I would be interested what your program would print in following case:

Code: Select all

10 10
##########
#........#
#........#
#........#
#...*....#
#........#
#...*.*..#
#...#....#
#...#....#
##########
Output should be 6.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

I just checked with a few submissions, that the test data is indeed weak. I will try to generate better inputs.

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa »

Adrian,

It outputs 6.

Check your private inbox in several minutes (writing my algo right now).
To be the best you must become the best!

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

For all who get WA after rejudge and think their program is right:
The new data set contains one invalid test case where 24 grid squares are needed. Sorry for my mistake, I already mailed the new data set to Carlos, I hope it is fixed soon.

Edit: fixed

rage_true
New poster
Posts: 8
Joined: Mon Sep 13, 2004 5:25 pm

10605 TLE

Post by rage_true »

I always get TLE on this problem.
Using brute forse on each step I try go from one diamante to another or go to exit(when i go to exit i find another unused diamonde and use recursion again).
How can i prune it?
Give me some hints.Plz.

ziliang
New poster
Posts: 19
Joined: Sat Sep 30, 2006 2:50 pm

10605

Post by ziliang »

i just got ac.

i noticed that each diamond must connect to another diamond or the wall.

so i enumerate the father of a diamond node. and then calculate the total langth.


i got acc but i don't know how to prove my method right.


i wonder how you guys solved this problem,and whether my algo was right? :roll:
不鸣则已,一鸣惊人.

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm
Location: bangladesh

Re: 10605

Post by mak(cse_DU) »

ziliang wrote:i just got ac.

i noticed that each diamond must connect to another diamond or the wall.

i wonder how you guys solved this problem,and whether my algo was right? :roll:
You are right "Ziliang".
I solved is using DP(TSP).
It will help some one:

Code: Select all

1
5 11
###########
#.........#
#..**.....#
#.........#
###########
Output:

Code: Select all

3
Mak
Help me PLZ!!

Post Reply

Return to “Volume 106 (10600-10699)”