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

Post Reply
..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

When I first solve the problem, I also get confused by the previous post.

What the problem require is, when you are at the center square(without knowing which direction you are facing), you have to decide the whole path. Say the path is, forward, right, left, forward, left, forward........

Once you decided the path, you have to use this path to walk.
You can't change the path once you start, so don't consider something like
"oh! I have stepped on a rose, I should be at position (x,y)"
You can assume that you will not know if you step on rose, though this assumption is not realistic.
Last edited by .. on Sun Dec 26, 2004 9:31 am, edited 1 time in total.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.
Top
shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 »

Well, so consider the given input in the problem:

.RRR.
R.R.R
R.P.R
R.R.R
.RRR.

here he can go north, east, south,south,west,south. in this case he needed to break 3. so why the answer is 2?
Self judging is the best judging!
Top
sidky
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:
Contact sidky

Post by sidky »

The man doesn't know which way he is facing. But, no matter the orientation is, he will move in the same directions. For this case, the man can move right, forward,forward,forward.
Check in 4 possible starting direction (North, South, East, West) and you can see, he would tremple at most 2 roses in these 4 directions. So, the answer is 2.
Top
Lamas
New poster
Posts: 13
Joined: Sun May 25, 2003 12:36 pm
Location: Hong Kong
Contact:
Contact Lamas

Post by Lamas »

Per wrote: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)
so if the map is like that

Code: Select all

9
####.#.##
####.#.##
#.##.#.##
####.#.##
####P####
##.######
##.##....
##.######
##.######
is the answer 3?

Thanks very much for Guru. I think I got it~~ :D
good algorithm is important~
Top
Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »

Yes the answer is 3.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Top
Lamas
New poster
Posts: 13
Joined: Sun May 25, 2003 12:36 pm
Location: Hong Kong
Contact:
Contact Lamas

Post by Lamas »

I got 3 WA~~~ :cry:

does anyone have good test case?
good algorithm is important~
Top
stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:
Contact stubbscroll

Post by stubbscroll »

I think I'm close to solving this problem (my program outputs the correct answer to all test cases posted here), but my program hangs on this input, you could try it:

Code: Select all

21
RRRRRRRRRRRRRRRRRRRRR
R...................R
R...................R
R...................R
R...................R
R...................R
R...................R
R...................R
R...................R
R...................R
R.........P.........R
R...................R
R...................R
R...................R
R...................R
R...................R
R...................R
R...................R
R...................R
R...................R
RRRRRRRRRRRRRRRRRRRRR
0
The answer should of course be 1 rose(s) trampled.
Last edited by stubbscroll on Sun Dec 26, 2004 5:00 pm, edited 2 times in total.
Top
Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »

How about this case:

Code: Select all

9
RRRR.RRRR
RRRR..RRR
RRRRR.RRR
R.....RRR
..R.P.R..
RRR.....R
RRR.RRRRR
RRR..RRRR
RRRR.RRRR
0
Output is:

Code: Select all

At most 0 rose(s) trampled.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Top
Lamas
New poster
Posts: 13
Joined: Sun May 25, 2003 12:36 pm
Location: Hong Kong
Contact:
Contact Lamas

Post by Lamas »

Both correct for the above case~~~
Sigh~~~ :cry:

Any other special case?

I have try:

Code: Select all

1
P
At most 0 rose(s) trampled.
13
RRR.RRRRRRRRR
RR....R..RRRR
RRRRRRRR..R.R
RR.R.RRRRRR.R
...R.R....R..
R.RR.RRRRRR.R
RRRR.RPR.RR.R
R.RRRRRR.RR.R
R.R....R.R..R
R.RRRRRR.R.RR
R.R..RRRRRRRR
RRRR....R..RR
RRRRRRR.RRRRR
At most 3 rose(s) trampled.
13
RRRRRR.RRRR.R
....R.R...R.R
RRRRR..RRRRRR
R.RRRRRR.RR.R
R.R..RR...RRR
R.RR....RR.RR
.R.R.RP.RRR..
R.RRR.R.RRRRR
..RR.R.R..R.R
R.RR.R.R.RR.R
R.RRRR.RRRRRR
R.R...R......
R.RRRRRR.RRRR
At most 3 rose(s) trampled.
good algorithm is important~
Top
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho »

Best that I can do, hope they help:

Code: Select all

21
RRRRRRRR.RRRRRRRRRRRR
RRRRRRRR..RRRR...RRRR
RRRRR...R..RR..R.RRRR
RRRRR.R..R....R..RRRR
R...R..R..RRRR..RRRRR
R.R..R..R..RR..R...RR
R..R..R..R....R..R.RR
RR..R..R..RRRR..R..RR
RRR.RR.RR..RR..R..R..
RRR.RR.RRR.R..R..R..R
RR..R..R..P..R..R..RR
R..R..R..R.RRR.RR.RRR
..R..R..RR..RR.RR.RRR
RR..R..RRRR..R..R..RR
RR.R..R....R..R..R..R
RR...R..RR..R..R..R.R
RRRRR..RRRR..R..R...R
RRRR..R....R..R.RRRRR
RRRR.R..RR..R...RRRRR
RRRR...RRRR..RRRRRRRR
RRRRRRRRRRRR.RRRRRRRR
21
RRRRRRRR.RRRRRRRRRRRR
RRRRRRRR..RRRR...RRRR
RRRRR...R..RR..R.RRRR
RRRRR.R..RR...R..RRRR
R...R..R..RRRR..RRRRR
R.R..R..R..RR..R...RR
R..R..R..R....R..R.RR
RR..R..R..RRRR..R..RR
RRR.RR.RR..RR..R..R..
RRR.RR.RRR.R..R..R..R
RR..R..R..PR.R..R..RR
R..R..R..R.RRR.RR.RRR
..R..R..RR..RR.RR.RRR
RR..R..RRRR..R..R..RR
RR.R..R....R..R..R..R
RR...R..RR..R..R..R.R
RRRRR..RRRR..R..R...R
RRRR..R....R..R.RRRRR
RRRR.R..RR..R...RRRRR
RRRR...RRRR..RRRRRRRR
RRRRRRRRRRRRRRRRRRRRR
21
RRRRRRRR.RRRRRRRRRRRR
.RRRRRRR..RRRR...RRRR
..RRR...R..RR.RR.RRRR
...RR.RRRR....RRRRRRR
....R..RR.RRRR..RRRRR
.....R..R..RR..R...RR
......R..R....RR.RRRR
.......R..RRRR..R..RR
........R..RR.RR..R..
.........R.R..R..R..R
..........P..R..R..RR
.........R.RRR.RR.RRR
........RR.RR..RR.RRR
.......RRRR..R..R..RR
......RRR..R..R..R..R
.....R.RRR..R..RR.RRR
....R..RRRR..R..R...R
...R..RR...RR.R.RRRRR
..RR.R..RR..R...RRRRR
.RRR.R.RRRR..RRRRRRRR
RRRRRRRRRRRR.RRRRRRRR
21
.................R.R.
RRRRRRRRRRRRRRRRRR.R.
.................R.R.
RRRRRRRRRRRRRRRR.R.R.
.R.............R.R.R.
.R.RRRRRRRRRRR.R.R.R.
.R.R.........R.R.R.R.
.R.R.RRRRRRR.R.R.R.R.
.R.R.R.....R.R.R.R.R.
.R.R.R.RRR.R.R.R.R.R.
.R.R.R.R..P..R.R.R.R.
.R.R.R.R.R.RRR.R.R.R.
.R.R.R.R.R.....R.R.R.
.R.R.R.R.RRRRRRR.R.R.
.R.R.R.R.........R.R.
.R.R.R.RRRRRRRRRRR.R.
.R.R.R.............R.
.R.R.RRRRRRRRRRRRRRRR
.R.R.................
.R.RRRRRRRRRRRRRRRRRR
.R.R.................
21
.................R.R.
RRRRRRRRRRRRRRRRRR.R.
.................R.R.
RRRRRRRRRRRRRRRR.R.R.
...............R.R.R.
...RRRRRRRRRRR.R.R.R.
.............R.R.R.R.
.....RRRRRRR.RRRRRRR.
.....R.....R.R.R.R.R.
.......RRR.R.R.R.R.R.
..........P..R.R.R.R.
.........R.RRR.R.R.R.
.........R.....R.R.R.
.......R.RRRRRRR.R.R.
.......R..R......R.R.
.......RRRRRRRRRRR.R.
.....R....R........R.
.....RRRRRRRRRRRRRRRR
.....................
...RRRRRRRRRRRRRRRRRR
.R.R.................
21
.................R.R.
RRRRRRRRRRRRRRRRRR.R.
................RR.R.
RRRRRRRRRRRRRRRRRR.R.
...............RRRRR.
...RRRRRRRRRRR.RRRRR.
.............R.RRR.R.
.....RRRRRRR.RRRRRRR.
.....R.....R.R.R.R.R.
.......RRR.R.R.R.R.R.
..........P..R.R.R.R.
.........R.RRR.R.R.R.
.RR......R.....R.R.R.
.RR....R.RRRRRRR.R.R.
.RR....R..R......R.R.
.RR....RRRRRRRRRRR.R.
.RR..R....R........R.
.....RRRRRRRRRRRRRRRR
.....RR..............
...RRRRRRRRRRRRRRRRRR
.R.R.................
21
RRRRRRRRRR.RRRRRRRRRR
RRRRRRRRRR..RRRRRRRRR
RRRRRRRRRR.RRRRRRRRRR
RRRRRRRRRR..RRRRRRRRR
RRRRRRRRRR.RRRRRRRRRR
RRRRRRRRR.RRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRR
RRRRRRRRR.RRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRR
R.R.RRRRR...R.R.RRRRR
RRRR......P......RRRR
RRRRR.R.R...RRRRR.R.R
RRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRR.RRRRRRRRR
RRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRR.RRRRRRRRR
RRRRRRRRRR.RRRRRRRRRR
RRRRRRRRR..RRRRRRRRRR
RRRRRRRRRR.RRRRRRRRRR
RRRRRRRRR..RRRRRRRRRR
RRRRRRRRRR.RRRRRRRRRR
0
Output:

Code: Select all

At most 0 rose(s) trampled.
At most 1 rose(s) trampled.
At most 2 rose(s) trampled.
At most 0 rose(s) trampled.
At most 2 rose(s) trampled.
At most 3 rose(s) trampled.
At most 4 rose(s) trampled.
Top
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

Post by abishek »

stubbscroll wrote:I think I'm close to solving this problem (my program outputs the correct answer to all test cases posted here), but my program hangs on this input, you could try it:

Code: Select all

21
RRRRRRRRRRRRRRRRRRRRR
R...................R
R...................R
R...................R
R...................R
R...................R
R...................R
R...................R
R...................R
R...................R
R.........P.........R
R...................R
R...................R
R...................R
R...................R
R...................R
R...................R
R...................R
R...................R
R...................R
RRRRRRRRRRRRRRRRRRRRR
0
The answer should of course be 1 rose(s) trampled.
I think you are trying to do a simple backtracing solution (I too did, and my program got TLE and does have this case as the worst case).
There is a polynomial solution to this question (I think).
backtracking is too costly here.
bye
abi
Top
Lamas
New poster
Posts: 13
Joined: Sun May 25, 2003 12:36 pm
Location: Hong Kong
Contact:
Contact Lamas

Post by Lamas »

Thanks very much for Cho~~~ :D

I do fix some bugs with your test case....... and get all your case correct now.
However, I still get WA... T_T.... :(
good algorithm is important~
Top
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho »

I think random test cases might not be helpful for tracing bug for this problem. Anyway, it's better than nothing to do.
100000 random cases: 10798.zip (3.6MB)
Caution: The unzipped files are 19.5MB and 2.8MB
Top
Lamas
New poster
Posts: 13
Joined: Sun May 25, 2003 12:36 pm
Location: Hong Kong
Contact:
Contact Lamas

Post by Lamas »

Thanks again~~
It really help me a lot..
I know what is the problem now.... :D
But i think it is quite hard to solve it..... :(
good algorithm is important~
Top
stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:
Contact stubbscroll

Post by stubbscroll »

Cho wrote:I think random test cases might not be helpful for tracing bug for this problem. Anyway, it's better than nothing to do.
100000 random cases: 10798.zip (3.6MB)
Caution: The unzipped files are 19.5MB and 2.8MB
Thank you very much. Random cases in huge enough numbers can help. I found 14 test cases where my program gave a wrong answer (1 more rose than correct). It seems my choice of pruning was flawed. I removed that particular pruning and I got correct answer, but also made my program much too slow (I get TLE now). I need to rethink my algorithm...
I think you are trying to do a simple backtracing solution (I too did, and my program got TLE and does have this case as the worst case).
There is a polynomial solution to this question (I think).
backtracking is too costly here.
bye
abi
Polynomial solution? Sounds very interesting. I did not think it was possible to solve wide search problems like this using polynomial solutions. I use DFS or BFS usually (I chose DFS/backtracking for this problem).
Top
Post Reply

Return to “Volume 107 (10700-10799)”