SRM: 477 - DIV: II - 500 Problem - Islands

Trivial problem with normal iteration, you can view the problem here

the main idea is to count the no of beaches that each cell has - if it is a land piece-.

We define a beach as a land that has a side neighbouring a water cell.

we iterate through all cells, if the current cell is a land peice we call the function countBeaches(i , j)

that counts the no of peace surrounding the indexed cell [ i ] [ j ].

we can define the function countBeaches(i, j) with two ways ;

the first one is two construct nested if statements that checks for every condition that exist for the 8 possible directions ( North, North West, North East, South , South East, South West)

regarding of course the difference between the odd lines and the even lines.

see the following picture to notice the difference

but another way to do this is to construct an array with the delta positions and add them to the original indexes to make the affect of translation.

that of course saves lots of coding time.

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.