HILLS - Editorial

PROBLEM LINK:

Practice
Contest

Author: Hasan Jaddouh
Tester: Misha Chorniy
Editorialist: Suchan Park

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

There are N hills in a row. The height of the i-th hill is H[i]. Chef is initially on the 1st hill.

When Chef is at hill i, Chef can jump to the adjacent hill j if and only if H[i] - D \le H[j] \le H[j] + U without a parachute, and H[j] < H[i] with a parachute. Chef is allowed to use the parachute at most once.

Find the rightmost hill that the Chef can reach.

QUICK EXPLANATION:

Simulate the whole process. Use the parachute as late as possible.

EXPLANATION:

Since the Chef can only jump to the adjacent hill, we can make a for-loop that iterates the current position of Chef.

Using the parachute when the Chef can jump without the parachute is obviously a waste. Therefore the Chef should continuously jump without a parachute as long as he can.

So, we can simulate the whole process using a for loop, like this:

for i = 1 to N: // i denotes the position of the Chef
  if (i == N) {
    // If the Chef is on the rightmost hill,
    // there is nothing to do.
  }
  else if (H[i] - D <= H[i+1] <= H[i] + U) {
    // if the Chef is able to jump on his own, 
    // just jump without a parachute
  }
  else if (H[i+1] < H[i]) {
    // Chef can jump if the parachute is left

    if(parachute isn't used) {
      Use the parachute.
    }else {
      Break the loop. (since the Chef cannot jump)
    }
  }
  else {
    // Chef cannot jump when the next hill is too high
    
    Break the loop. (since the Chef cannot jump)
  }

One can check whether the parachute is used or not by setting a boolean-type variable. (true if used, false otherwise)

The answer will be the maximum i visited during the loop.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

here is the link to the easiest solution to this problem :

https://github.com/executable16/CodeChef/blob/master/JumpingInTheHill.cpp