SRM 302

Division 2

250 Pts -

Idea Flow

Input_Constraint ~ One for loop is sufficent.

Question Hints ~ Direct Implementation Problem.

Conclusion ~ Was in right direction.

Learnt lesson ~ Stl makes things faster discussed in previous blog

500 Pts -

Idea Flow

Input_Constraint ~ Question is direction any implementation ll pass the time limit.

Question Hints ~ Each position is of character 2

Conclusion ~ Using Set operation safe lot of time I was sorting each time.

Learnt lesson ~ Learnt to use Set operation.

1000 Pts -

Idea Flow

Input_Constraint ~ Question is clear and bruteforce ll timelimit

Question Hints ~ Since we need to take oly the factor. Running till sqrt(N) ll pass the time limit.

Conclusion ~ I used queue and solved the problem didn come up with the dp solution.

Learnt lesson ~ Using dp would have fasten things up, But why dp works thing about it .

Things to ponder

Does first computed current state from any previous state is the final solution or we need to find minimum from all previous state.

.i.e

if(j+i<=M )
  dp[j+i]=min(dp[j+i],dp[i]+1);
if(i+l<=M )
  dp[i+l]=min(dp[i+l],dp[i]+1);

is't equivalent to

if(j+i<=M and dp[j+i] not visited )
  dp[j+i]=dp[i]+1;
if(i+l<=M and dp[j+l] not visited )
  dp[i+l]=dp[i]+1;