- Problem Statement.
- A
**main()**with the examples compiled in. - A skeleton that compiles with
**main.cpp**. -
**Problem Given in Topcoder**: September, 2016 -
**Competitors who opened the problem**: 466 -
**Competitors who submitted a solution**: 379 -
**Number of correct solutions**: 308 -
**Accuracy (percentage correct vs those who opened)**: 66.1% -
**Average Correct Time**: 19 minutes, 37 seconds.

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

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.

/* 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; } |