TopCoder problem "RainyDay" used in SRM 372 (Division II Level Three)

Problem Statement


As the ruler of Rainban, you are well aware of the fact that your country often has violent rainstorms. Thus, you usually remember to ride the Rainban Official Motorcade to your destination. Today, however, you looked outside and, eschewing common sense, decided to walk to the store. Now, a very bad storm is coming, and your Giant Hole (TM) umbrella has a large hole in it!

You know the path that you need to travel to return to your home. You are currently standing where the 'Y' is and are trying to reach home (the 'H'). The rest of the path consists of either 'C' or '.', corresponding to whether that section of the path is covered (and thus rain-proof) or uncovered, respectively. Both your current location and home are rain-proof. You also know the forecast, in which the i-th character is 'R' if it is currently raining at the i-th section of the path, or '.' if it is not.

During each minute, the following events happen:

  1. You choose whether or not to move. If you choose to move, you immediately move one step to an adjacent section of the path. If you choose not to move, you remain in your current section.
  2. If you are now standing in an uncovered section and it is raining there, you get wet.
  3. The forecast circularly shifts one section to the left. For example, "R..R" would become "..RR" (quotes for clarity).
  4. If you are standing in an uncovered section and it is now raining there, you get wet.

So if the path is "Y..H" and the forecast is "R.RR", then choosing to move right every minute would result in the following:

Forecast: R.RR       R.RR       .RRR       .RRR       RRR.       RRR.
Path:     Y..H  -->  CY.H  -->  CY.H  -->  C.YH  -->  C.YH  -->  C..Y
               You        Rain   Get  You   Get  Rain  Get You    Get
               move       moves  wet  move  wet  moves wet move   home

Thus, in the above case, you would get wet 3 times on your way home.

Return the minimum number of times that you will get wet before returning home, if you time your journey properly. You don't care how long it takes, as long as you eventually get home while as dry as possible.



Parameters:String, String
Method signature:int minimumRainTime(String path, String forecast)
(be sure your method is public)


-path will be between 2 and 50 characters, inclusive.
-Each character in path will be 'Y', 'C', '.', or 'H'.
-There will be exactly one 'Y' and exactly one 'H' in path.
-forecast will contain the same number of characters as path.
-Each character in forecast will be either 'R' or '.'.


Returns: 3
The example from the statement.
Returns: 2
Here, you wait 2 minutes, then move right twice (getting wet once). You can then wait 1 minute and move right twice again, getting wet once more.
Returns: 3
Returns: 2
Returns: 0
No rain at all in the forecast!

Problem url:

Problem stats url:




PabloGilberto , radeye , Olexiy , Andrew_Lazarev

Problem categories: