10798 - Be wary of Roses

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

Moderator: Board moderators

Michael Goldshteyn
New poster
Posts: 14
Joined: Tue Oct 19, 2004 2:01 am

10798 - Be wary of Roses

Post by Michael Goldshteyn »

I thought the solution to this problem involved finding the worst of the least weight (fewest roses stepped on) paths starting from the four squares around the plinth ('P') square. Apparently this is not the case. My attempt at solution went something like this:

1) Find least destructive path from square above plinth to any edge square.
2) Find least destructive path from square right of plinth to any edge square.
3) Find least destructive path from square below plinth to any edge square.
4) Find least destructive path from square left of plinth to any edge square.

Take the worst of the above and that is the most roses that will get trampled. However, I get wrong answer with that approach, so clearly there is more to the problem than this. Can someone who got an accepted status or the problem author comment, please.

Mike

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

I have not tried this problem yet, but it seems like an A* search problem..

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

Post by Adrian Kuegel »

I haven't solved the problem yet, but I am sure I understood it.
The problem asks you to find a path such that the number of trampled roses is minimum, where you take the maximum of the 4 possible "rotations" of that path. Your approach does not solve this (although I can't give you a counterexample right now).
So, naive solution would be:
- Loop over all possible paths
- evaluate number of trampled roses for each direction
- let cost of that path be maximum of trampled roses for a direction
- select path with minimum cost.

IgorOstrovsky
New poster
Posts: 2
Joined: Tue Dec 14, 2004 5:14 am

Post by IgorOstrovsky »

Mike, here is a counter-example to your solution:

Code: Select all

@@.@@
@@.@@
..P..
@@..@
@@@.@
Your approach would return that no roses will be trampled because there is a path from all four neighbours of the center to the edge so that no roses are trampled. However, the four paths are not all rotations of each other. So, the gardener will not have a strategy such that no roses are trampled regardless of which direction s/he is facing.

Igor

Michael Goldshteyn
New poster
Posts: 14
Joined: Tue Oct 19, 2004 2:01 am

Post by Michael Goldshteyn »

So, if I understand this correctly. You have to try all minimal exit paths, on all four rotations of the field and print the worst case scenario?

Mike

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

Post by Cho »

I don't quite understand the problem...
What's the purpose of 'P' in the input?
And why I have to tramples 2 roses to escape for the sample?

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim »

I haven't solved the problem, but I can tell you that your hands are tied and eyes covered. so there must be a generic strategy that will reduce the number of flowers trampled.
Last edited by shamim on Wed Dec 15, 2004 2:44 pm, edited 2 times in total.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per »

Cho wrote:I don't quite understand the problem...
What's the purpose of 'P' in the input?
And why I have to tramples 2 roses to escape for the sample?
P has no significance. It is always in the middle square of the map.

Since you don't know your direction, you can never be certain that your first step is neither north nor south, and it should be obvious that any path starting with north or south needs to cross at least two roses. Hence there is no way to guarantee that fewer than 2 roses are trampled.

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

Post by Cho »

Then I think I really misunderstand the problem. The problem states that "You must come up with an escape path that tramples the fewest possible roses". I thought the gardener (me) can make decision when I am escaping. So for the following input:

Code: Select all

11
...........
...........
...........
...........
....RRRRRR.
....RPRRRR.
....RRRRRR.
....RRRRRR.
....RRRRRR.
....RRRRRR.
...........
Originally, I think the answer is 2 because if I'm unlucky and walking towards south, I will immediately know that there will be three more roses in front of me. So I should turn back and escape in opposite direction. Two roses are trampled as result.

But after reading the posts, it seems that the answer should be 4. Can someone confirm that?

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per »

Cho wrote:Then I think I really misunderstand the problem. The problem states that "You must come up with an escape path that tramples the fewest possible roses". I thought the gardener (me) can make decision when I am escaping. So for the following input:

Code: Select all

<snip>
Originally, I think the answer is 2 because if I'm unlucky and walking towards south, I will immediately know that there will be three more roses in front of me. So I should turn back and escape in opposite direction. Two roses are trampled as result.
Yes, you can make choices, but you never learn which direction you're facing, even after taking a few steps. So in your example if you take a step south you won't know that there are three more roses in front of you, since you have no way of knowing that you happened to take a step south (it might as well have been east, west or north for all you know).

I guess a slightly more realistic version of the problem would be that the gardener can sense when he tramples a rose, and hence conclude that some directions are impossible.
But after reading the posts, it seems that the answer should be 4. Can someone confirm that?
Yup, that's correct.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

Hmm. Cho brings up an interesting point and for his example an escape with trampling 3 roses is possible and consistent with the problem description:

Start by taking two steps forward, in the yet unknown direction.
If you step on a rose with your second step, then you know (since you memorised the map) that you are either walking south or east, in which case you turn around and keep walking in the opposite direction, thereby trampling one more rose, for a total of three.
If you didn't step on a rose with your second step, you know you are either walking north or west, in which case you can escape by continueing walking in the same direction without stepping on an other rose.

To get the intended answer (4) in this case, you either should not be aware that you step on a rose (unlikely) or be forced to determine your path before you start walking. The latter could be meant by the phrase "You must come up with an escape path...".

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

Actually, I think BFS is fine, since the number of states isn't that big..

Michael Goldshteyn
New poster
Posts: 14
Joined: Tue Oct 19, 2004 2:01 am

So repeating the method of solution once more

Post by Michael Goldshteyn »

Is it true then that the solution to the problem is:

1) Take all possible minimum weight (least roses trampled) exit paths, since we don't know the choice of optimal route that the farmer will make and he can choose any optimal route, since they all have equal weight.
2) Apply them to all four possible rotations of the board, adjusting the maximum number of roses trampled, accordingly, since the farmer can attempt any optimal route, without caring which direction he is actually facing. The final maximum number of roses trampled is the answer.

Mike

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per »

No.

Consider, for example, the test case

Code: Select all

9
####.#.##
####.#.##
#..#.#.##
####.#.##
####P####
##.######
##.##....
##.######
##.######
There is only one minimum weight exit path, but applying your second step to that path would give you the answer "4", whereas the real answer is "2" (take two steps forward, then walk left)

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 »

I am confused with the test case you gave here per.

Here I am giving what happens in the four direction:

North: No obstacle. 0
South: steps and break 1. if he continues in this path he will break more. So he gets back. And go to north. So in this case 1.
Same for east and west.

So answer must be 1. why two?

Well here is a case:
00R00
R00RR
R0P0R
00000
00000

I know the man does not know which direction he is. So consider walking to north. He steps in safe place. Then if he again goes to north he will break 1. but if he follows left then north he will be able to go out without breaking. Right? But how will he select whether he will go to left or straight? At least he does not know the direction.

I guess the total answer is 0 for this case. But actually what the problem said? AT MOST right? So here for my case if he continues to north he have to break one to go out. Again if he steps north then two right then he breaks two. That means at most he breaks 2 to go out from the field? Hoof, I am puzzled! Can anybody explain what actually happens for my and per
Self judging is the best judging!

Post Reply

Return to “Volume 107 (10700-10799)”