10798 - Be wary of Roses

[Larry]

You should look at the constraints very carefully..

[stubbscroll]

Thanks for the small hints given in this thread and the "Help with NCPC" thread. I realise that dynamic programming might be the way to go. I'll get back to this problem later when I'm more skilled in DP. Formulating recurrence relations is one of my weakest areas, and that's the main reason why I have trouble with DP and why I also often choose backtracking instead . Does anyone know about a good internet tutorial on recurrences, that even I might understand?

[stubbscroll]

Nevermind my last post. I actually got accepted on this problem after improving my existing solution. "Later" turned out to be under one hour.

[Lamas]

I got AC la..... XD

Thanks Cho~ Thanks everyone~~~

[Cho]

I thought I can hold the record for a while.
But yours requires 64KB memory and takes 0.066s only

[Lamas]

hehe~~

[..]

I thought I can hold the record for a while.
But yours requires 64KB memory and takes 0.066s only

On the online judge, when a program finishes fast enough, the judge can't measure its memory usage and will consider the memory usage as 64KB.
Maybe Lamas is really intelligent to write a program that uses small memory, I don't know

[sohel]

Can anyone tell me why my approach doesn't work.

- I run one dfs and I assume that I am initially facing north.
- For each move I consider 3 other shadow moves that goes in the other three directions along with the original one. And I consider the cost as the maximum of the four positions.

I am basically optimizing A[21][21][4]...
.. that is for each point there could be four orientation.

Suppose the garden looks like this.

...
RP.
...

So when I take a step to north the cost is 1 and not 0, since the shadow walker along the west directions steps on a rose.

and thus after the first move A[1][2][0] becomes 1. From each state I consider 3 moves, ie go forward, turn left or turn right.

I get all the samples right of this board.

my node looks like this..

struct node {
point p1, p2, p3, p4; // the location of me and my three shadows.
int d1, d2, d3, d4; // the direction that four of us are facing
int m1, m2, m3, m4; // numbers of roses that the four of us have stepped on to come to the respective point.
}

[Destination Goa]

Do you consider that edges have different length in your DFS? (some 0, some 1). You should apply sorta Dijkstra algorithm. Though, it is solvable within O(N) using BFS with two queues. One queue is used to step via zero edges, another queue stores nodes one unit away from those in the zero-queue. Only when zero-distance queue is empty, one can move from non-zero-distance queue nodes. You'll get it when you try to write it. It's like Dijkstra where minimum is either 'current' or 'current+1'.

The approach seems correct to me (and I was going to impement it myself). Since everything is symmetric, current position is all we need to spot damaged roses for 4 other cases of a path. I don't know why do you need direction in this problem. Coordinates should be enough.

There was another problem of this kind (AFAIR, "Maze Traversal"). There you had to find shortest path which gets you out of the maze with invalid steps skipped. That was much worse because the path was actually important to detect skipped moves (final coordinates wouldn't be the same for different origins). This is not the case with this problem. All paths reach the border simultaneously and there are no obstacles on the map.

[Destination Goa]

All that confusion I saw in the begining comes because of "North", "South", etc... in the problem statement. It would be nicer to write "forward", "backward", "left", "right". Perhaps I wasn't trapped because I remembered of "Maze Traversal" problem I stated above. It is located somewhere in volumes 6-8 as far as I remember.

[Destination Goa]

Yeah, applying Per's test I see there is a need for direction or something else. Coordinates are fine, but number of roses isn't.

You do right that you store quadruples (m1, m2, m3, m4) for each node. But direction on itself isn't enough. You have to keep all possible quadruples for each node. You can eliminate only quadruples dominated by some other quadruple stored in the node. By "dominated" I mean that all m1..m4 are greater-equal then those ones of dominator quadruple. Anyway, I think this makes it non-polynomial.

Consider two quadruples:
1 10 0 0
1 2 3 3

You will keep the 2nd one. But if all further steps will add to 3rd and 4th shadow walker, you'll end up with something like that:

1 10 9 9
1 2 12 12

But "1 10 0 0" was eliminated, so you will not produce "1 10 9 9" which is obviously better.

[Destination Goa]

Since the obvious upper limit is (N-1)/2 roses (always go forward), there is at most 11^4 quadruples for each node. And there are 21x21 nodes. This leads to 6'500'000 states, many of which will be unreachable. So I think BFS over good hashing will solve the problem.

[Destination Goa]

Finally AC. The method described above works. However, at first it gave TL. Basic optimizations led to 7.5 sec. Hard optimizations got it under 0.035 sec.

[Destination Goa]

So, actually it's polynomial for O(N^6).

[little joey]

Destination Goa,

So now we're going to see some five postings for every problem you solve or try to solve? What are you trying to achieve by that? Exposing the thought process of a superior mind? Increasing your number of posts?

I like to discuss problems and the way to solve them, but I'm not interested what you're doing right now. It serves no purpose. But that, of course, is only my opinion.

-litlle joey.