SRM 699, D2, 250-Pointer (UpDownHiking)

James S. Plank

Wed Nov 23 14:59:12 EST 2016
Try this on your own, and I'll give you a hint. For each day, calculate where you would be if you simply ascended every day, or where you would be if you magically started at height N*B, and descended every day. Your answer will be one of these.

I will give you more explanation and an answer below.

A hit rate of 66 percent is pretty low for a problem that seems very simple. As with many of topcoder's problems, one of the keys to success is to try not to be too smart. I think one tendency that people have is to use algebra to figure out on what day you need to switch from going up to going down. That's fine, but since N is constrained to be 50, you can simply simulate each day.

As I hinted above, suppose you simply ascend every day. Then, your altitude, at the beginning of each day, will be 0, A, 2A, ..., (N-1)A. At the end of day N, your altitude will be NA.

And suppose that you magically started at altitude NB, and instead, you descend every day. Then, your altitude, at the beginning of each day, will be NB, (N-1)B, (N-2)B, ..., B. At the end of day N, your altitude will be 0.

Let's look at the first four examples:

Example 0: 
Day 1:  0 or 30
Day 2:  7 or 20
Day 3: 14 or 10
Example 1: 
Day 1:   0 or 150
Day 2:  40 or 120
Day 3:  80 or  90
Day 4: 120 or  60
Day 5: 160 or  30
Example 2: 
Day 1:  0 or  2
Day 2: 50 or  1
Example 3: 
Day 1:  0 or 126
Day 2: 42 or  84
Day 3: 84 or  42

As you can see, on each day, you have a choice of values -- one where you're always going up, and one where you're always going down. If the first of these is higher than the second, then it's impossible to achieve, because you'll be too high to get back down to altitude zero.

If the second of these is higher than the first, then that altitude will be impossible to achieve, because you can't get there from the beginning, by going up every day.

What this means is that for each day, the smaller of the two values is the one that can be achieved. It will start out being the value that you get by going up, but at some point, it will switch to be the value that you get by going down. Regardless, you can keep track of this value for each day, and return the maximum. For Example 0, that will be 10, which is the largest minimum value on any day. In example 1, it is 80.

This is the easy program to write. Yes, you can use algebra to calculate on what day this will occur, but it's much easier to simply write the for loop and keep track of the best value.

That code is below.

Solution.cpp: 

/* Topcoder SRM 699, D2, 250-Pointer: UpDownHiking.
 * James S. Plank
 * Wed Nov 23 15:22:45 EST 2016
 */

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

class UpDownHiking {
  public:
    int maxHeight(int N, int A, int B);
};

int UpDownHiking::maxHeight(int N, int A, int B)
{
  int Day;         /* We'll run through each day, from day 1 to day N */
  int Up;          /* This is our altitude at the beginning of each day, if we only went up. */
  int Down;        /* This is our altitude if we started at N*B and only went down each day. */
  int Min;         /* For each day, we record the minimum of Up and Down here. */
  int Best;        /* This is the maximum value of Min */
 
  Up = 0;
  Down = N*B;
  Best = 0;

  /* This loop is simple enough that it doesn't really need any comments.  We're going
     to maintain the values of Up and Down for each day, from 1 to N, calculate the
     minimum value, and then keep track of the best of these. */

  for (Day = 1; Day <= N; Day++) {
    printf("Day %d: %4d or %4d\n", Day, Up, Down);
    Up += A;
    Down -= B;
    Min = (Up < Down) ? Up : Down;
    Best = (Min > Best) ? Min : Best;
  }

  return Best;
}