PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Alei Reyes
Tester: Aleksa Plavsic
Editorialist: Taranpreet Singh
DIFFICULTY:
Cakewalk
PREREQUISITES:
Basic Math.
PROBLEM:
Given heights H of N steps of a staircase, you have to reach the last step. Your current height is 0. You cannot climb next step, if H[i+1]-H[i] > K. In order to reach the top, you can make steps. Find the minimum number of steps you have to make, to reach the last step. Also, H[i] < H[i+1] for all valid i.
SUPER QUICK EXPLANATION
- Number of steps to be built between ith step and next step is dependent only upon differenct of heights of current step and the next step.
- Final answer is given as sum of (H[i]-H[i-1]-1)/K for all valid i, 1 \leq i \leq N, considering H[0] = 0.
EXPLANATION
The first thing to notice is that Number of steps to be built between the ith step and next step is dependent only upon difference of heights of the current step and the next step. Because the height of steps are in strictly increasing order of height, which means, If we cannot reach step x from the previous step, we cannot reach any other step after x without building step just before step x.
Since we want to make the least number of steps, we will try to make the next step as high as possible, while keeping it reachable from the current step. Give a try to calculate this Maximum distance.
Initially, from a step of height x, we can reach any step of height in the range [x, x+K] directly, [x,x+2*K] height by building one step, [x,x+y*K] height by building y-1 steps. between two consecutive given steps.
To find this value y, we can take the difference in heights of consecutive steps less the height we can jump directly. Call it D. This difference we need to cover by using steps of height K. Since y is minimum steps we build, D-K \leq y*K. We can rewrite it as D \leq (y+1)*K.
Again rewrite it as y = \lceil D/K \rceil -1.
This is it, we can take the sum of all y for every consecutive steps pair and print as the answer. For simplicity, add a step of height 0 before the first step, Since our initial height is 0.
Time Complexity
Time complexity is O(N) since we iterate over array H once only.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 