SRM 301

Division 2

250 Pts - InsertionSortCount  

Idea Flow

Input_Constraint ~ We cannot use more than two loops.

Question Hints ~ "Must know insertion sort :p".

Conclusion ~ Straight forward check ll run within in runtime.

Learnt lesson ~ take index j and check number of number from [0..j-1] is > j. So those corresponds to the result. 

500 Pts - IndicatorMotionReverse 

Idea Flow

Input_Constraint ~ 1 sec is the time-limit so string-length can be the number of operation.

Question Hints ~ "Understand that it is a direct implementation program.

Conclusion ~ Finding shorter way to code is more important.

Learnt lesson ~ Sometimes it's is better to expand the input and then get answer from the expanded string.

1000 Pts - CorrectingParenthesization 

Idea Flow

Input_Constraint ~ Problem allows maximum of 50^4 operation that is 4 for loop for the give problem.

Question Hints ~ Gives idea that we need use dynamic programming approach.

Conclusion ~ Fixing two brackets and solving for other sub-problem.

Learnt lesson ~ Must learn how to convert this to bottom-up approach or the iterative method.

int run(int i,int j)
{
   if(i>j)
     return 0;
   int &res=dp[i][j];
   if(res!=-1)
     return res;
   res=run(i+1,j-1)+enc(ans[i],ans[j]);
   for(int k=i+1;k<j;k+=2)
    res=min(res,run(i,k)+run(k+1,j));
   return res;
 
}