ICE - Editorial

Editorial - Ice-Cream Party



Author: Divesh Thakker
Tester: Nishit Patel
Editorialist: Divesh Thakker




Dynammic Programming

Problem statement

There are n numbers and you have to choose some numbers such that their sum is minimum under the condition: for each i - atleast either i-1, i, or i+1 is chosen.

Quick Explanation

There are 3 options to begin with - taking the 1st one , taking the 2nd one , and taking the 3rd one. Subsequently apply dp on the rest of the array.


If you choose an element i then u have to choose either i+1, i+2, i+3. Hence we have 3 choices at the start -

  1. To take the first element . Then it is not complusary to take the last element as its ajacent element ie. the first element is taken .

  2. To take the 2nd element . Then it will be normal dp as it not compulsary to take the last element as 1st element has its ajacent element ie. the 2nd element taken.

  3. To take the 3rd element . Then it is compulsary to take the last element as 1st element has no ajacent element taken. Hence we have to compulserly choose the last element . (One tecnique is to add INT_MAX after the last element which will make it nesserary to take the last element)

Subsequently continue on to the dp solution and get the best of these 3 conditions and print that answer.


Setter’s solution

Tester’s solution

Time complexity - O(n)