HILLS - Editorial

Tester: Misha Chorniy
Editorialist: Suchan Park

Cakewalk

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

1 Like