SRM: 477 - DIV: II - 250 Problem - Vacation Time

The problem main idea was to choose an interval to ensure the minimum re-scheduled days through the whole No. of days given

You can view the whole problem here

The first approach to this problem is brute force algorithm, we may think of it this way;

may be we should try all the possible intervals that start at day no [ i ] and end at day [ j ]

and count the no of re-scheduled days between those days, and keep track of the minimum no of scheduled days.

This algorithm will satisfy the time limit but is still as obvious in O ( n ^ 2 ).

another Dynamic Solution will solve problem in only O( n ).

the hint is we may solve this problem as follows ;

1st - we will have an Array that holds at Position [ i ] ; the sum of all scheduled days from day [1] to day [ i ]. that is by simply looping through the array and accumlating the sum of the previous day to this day we are in.

2nd - we loop again through the same array checking the minimum scheduled days in between day[ i ] and day [ i + K ].

Simply we transformed the too nested loops into two separate loops that each run in O ( n ) (^.^)

No one believe what Dynamic Programming can do to your life :)

Here is the sample code for a more clarification.