Page 2 of 4
Posted: Sat Dec 25, 2004 12:13 pm
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.
Posted: Sun Dec 26, 2004 3:04 am
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?
Posted: Sun Dec 26, 2004 4:46 am
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.
Posted: Sun Dec 26, 2004 9:18 am
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~~
Posted: Sun Dec 26, 2004 11:01 am
by Observer
Yes the answer is 3.
Posted: Sun Dec 26, 2004 11:55 am
by Lamas
I got 3 WA~~~
does anyone have good test case?
Posted: Sun Dec 26, 2004 4:12 pm
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.
Posted: Sun Dec 26, 2004 4:22 pm
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:
Posted: Sun Dec 26, 2004 7:11 pm
by Lamas
Both correct for the above case~~~
Sigh~~~
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.
Posted: Sun Dec 26, 2004 8:22 pm
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.
Posted: Mon Dec 27, 2004 5:34 am
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
Posted: Mon Dec 27, 2004 11:05 am
by Lamas
Thanks very much for Cho~~~
I do fix some bugs with your test case....... and get all your case correct now.
However, I still get WA... T_T....
Posted: Mon Dec 27, 2004 1:02 pm
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
Posted: Mon Dec 27, 2004 5:51 pm
by Lamas
Thanks again~~
It really help me a lot..
I know what is the problem now....
But i think it is quite hard to solve it.....
Posted: Mon Dec 27, 2004 7:26 pm
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).