11501 - Laurel Creek

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

Moderator: Board moderators

Post Reply
redroof
New poster
Posts: 5
Joined: Sun Sep 28, 2008 12:51 pm

11501 - Laurel Creek

Post by redroof »

A clarification question -- Can we pick up the log (length == 1) in the figure below? (suppose we stand on 'B')

Code: Select all

....
.B.S
.|..
...E
If yes, we have a path to traverse from B to E, otherwise not. thanks.

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Re: 11501 - Laurel Creek

Post by baodog »

Yes, you can.

redroof
New poster
Posts: 5
Joined: Sun Sep 28, 2008 12:51 pm

Re: 11501 - Laurel Creek

Post by redroof »

Got AC. Actually we don't need to consider the above case. My ac code assumes all logs are connected by two stumps.

Vytenis
New poster
Posts: 7
Joined: Mon Aug 04, 2008 8:16 pm

Re: 11501 - Laurel Creek

Post by Vytenis »

Is there some simple solution to this problem? I thought that a kind of BFS is needed, but it seemed that the potential state space is too big for it to run in time.

redroof
New poster
Posts: 5
Joined: Sun Sep 28, 2008 12:51 pm

Re: 11501 - Laurel Creek

Post by redroof »

I use BFS. Considering the available slots where the log can be picked up or put down, the state space is not that big. Because there are at most 15 stumps with limited row and column size(<= 15) and logs only exist between stumps, the following case is the one that comes with the greatest number of logs. right? :roll:

Code: Select all

S-S-S-S
|.|.|.|
S-S-S-S
|.|.|.|
S-S-S-S
|.|.|.|
S-S-S-.
There are less than 24 positions that logs can be put down. Also the current position can be represented with 4 bits (we can only stand on a stump), so the state space can be represented as 4bit + 24bit = 28 bits.

bemscho
New poster
Posts: 1
Joined: Thu Oct 09, 2008 7:57 pm

Re: 11501 - Laurel Creek

Post by bemscho »

I use BFS, too. But I got WA at 0.010
I don't consider length or location of logs, but only stumps. Is this wrong approach?
Could you give me some critical test case?

redroof
New poster
Posts: 5
Joined: Sun Sep 28, 2008 12:51 pm

Re: 11501 - Laurel Creek

Post by redroof »

Code: Select all

....S...S..
........|..
B-----S.|.E
......|.|..
......|.S..
......|....
....S-S....
I don't know how you process with only the information of stumps. But try the above case.

Post Reply

Return to “Volume 115 (11500-11599)”