通过

Hackerrank - Chief Hopper problem

  • 项目

In This post I would like to discuss a nice problem that I solved recently in Hackerrank.

For those of you who don't know Hackerrank, then it is time to get acquainted with it.

Its a great site containing many coding challenges with an online judge.

The Challenges are divided into categories (graphs, dynamic programming, greedy, etc...) and subdivided based on their difficulty level.

I try to solve every couple of days a problem in Hackerrank mostly to keep the brain working and fresh.

Today I would like to discuss a nice problem that I recently solved and show the solution for it.

 

Cheif Hopper:

Chief's bot is playing an old DOS-based game. There are N+1 buildings in the game - indexed from 0 to N and are placed left-to-right. It is guaranteed that building with index 0will be of height 0 unit. For buildings with index i (i∈[1,N]) height will be hi units.  

At beginning Chief's bot is at building with index 0. At each step, bot jumps to next (right) building. Suppose bot is at kth building and his current energy is botEnergy, then in next step he will jump to (k+1)th building. He will gain/lose energy equal in amount to difference between hk+1 and botEnergy

  • If hk+1>botEnergy, then he will lose hk+1−botEnergy units of energy.
  • Otherwise, he will gain botEnergy−hk+1 units of energy.

Goal is to reach Nth building, and during the course bot should never have negative energy units. What should be the minimum units of energy with which bot should start to successfully complete the game?

Input Format

The first line contains integer N. Next line contains N space separated integers h1,h2, ?,hN representing the heights of the buildings.

Output Format

Print a single number representing minimum units of energy required to complete the game.

Constraints 
1≤N≤105 
1≤hi≤105,i∈[1,N]

This problem is actually trickier than what it seems and I will use my usual induction paradigm to come up with an algorithm to this problem.

We will device an algorithm using an induction on the number of buildings N:

1. P(1) - there is only one building. Unlike other problems that I usually elegantly skip this step by saying that it is trivial, it is worth while to spend time thinking through this step as it will give us insights to the rest of the problem.

 For one building what is the minimal energy that we need ? We can start out by having h1 initial energy, leaving us with h1 + (h1 - h1) energy once we finish with the building. But is it actually required to have h1? the requirement is that we don't end up with negative energy, However 0 or more energy are fine.So we need to find an initial energy level E such that E + (E - h1) = E - (h1 - E) >= 0. Hence we need E to be equal to ceiling(h1/2).This will now hint us to the solution of the entire problem.

2. P(n < N) - Lets assume that we know how to solve the problem and find the minimal required starting energy for n < N buildings.

3. P(N) = ? How do we reduce the problem from N buildings to n < N buildings. Since we need to find the initial minimal energy, it only makes sense that we ignore the first building (e.g. h1) and apply our induction hypothesis to (h2... hN) buildings. We get from the induction hypothesis a minimal initial value E2N (for buildings h2 ... hN). What do we do with building h1 ? this is very similar to P(1). Our equation will be: E1N + (E1N - h1) >= E2N.

E1N = ceiling((E2N + h1)/2).

To describe now the algorithm in words: We start with an initial energy level of 0. We traverse the buildings from last to first applying the equation above to each building and updating the energy level accordingly. 

Lets see the code:

Comments

  • Anonymous
    April 22, 2015
    thanks..its awesom
  • Anonymous
    June 01, 2015
    Why do you have the "+1" term in "MinE = (MinE + Buildings[i] + 1)/2" ?
    Is it for rounding?
  • Anonymous
    August 17, 2015
    thnx ....was really helpful. keep it up...
  • Anonymous
    February 07, 2016
    Can you clarify on the first part of the induction.you mentioned that "E to be equal to ceiling(h1/2)" for only one building,Let's say its height is 3 then as you mentioned min initial energy would be floor(3/2) = 2.But 2 is not correct as we get -ve energy(2-3).
  • Anonymous
    June 14, 2017
    Nice solution. Being more simple-minded than you, I solved this problem simply by brute-force bisection method. It's fast enough to pass Hackerrank tests (even with Python).