Here is the solution I came up with.
The idea is based on the following assumption: from starting point of (0,
0) the Fan can reach Peppurr in the fastest within abs(x) + abs(y) minutes,
assuming that Peppurr is on (x, y). This doesn't depend on the way Fan
choose: either it's half a rectangle with sides x and y or it is a stairs
or combined. Geometrically all the FASTESTS ways are equal to the way of
sides of rectangle = |x| + |y|.
Based on that, after we read the initial coordinates and during the reading
of Peppurr path char-by-char we can do 3 things:
1. update Peppurr coordinates
2. add the number of minutes passed since Peppurr started
3. compute the time of Fan will reach the Peppurr's coordinanates.
Example:
3 2 SSSW
step-by-step calculation sequence will look like that:
Peppurr move | Peppurr's coordinates after move | *Peppurr's minutes* | *Fan
minutes* to reach Peppurr's coordinates = |x| + |y|
(3, 2)
0 5
S (3, 1)
1 4
S (3, 0)
2 3
S (3, -1)
3 4
W (2, -1)
4 3
So as soon as *Fan minutes* >= *Peppurr's minutes*, the alg stops. Result =
Max(*Fan minutes*, *Peppurr's minutes*)
Obviously, the solution is IMPOSSIBLE if we reached the end of path and the
previous condition hasn't been met.
The time complexity is O(n), where n is the length of Peppurr's path, which
needs to be read down to end in worst case.
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/7b2e1fb4-f3a3-48b6-b415-4a1bd7dffe50%40googlegroups.com.
