I apologise, the alg obviously stops when *Fan minutes* <= *Peppurr's minutes*
On Monday, 4 May 2020 10:06:56 UTC+8, Alexander Iskhakov wrote: > > 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 google-code+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/85fe62d5-884a-43c5-920b-3a654154b0c3%40googlegroups.com.
