Unofficial editorial of first 3 questions of DEC2016 long contest

Hello guys,

I have created a page Facebook where I have posted the explanation of the first 3 problems of the DEC2016 contest. I didn’t manage to do the others. If I succeed I’ll post their explanation too :slight_smile:

Feel free to like my page, to receive updates on it :slight_smile:

Thanks

Regards,
Rohit

I felt that your example for the editorial of KIRLAB was wrong or I may have misunderstood it. Let’s try your method with the given test case.
13 2 8 6 3 1 9
here dp[13]=1, dp[2]=3 and dp[3]=3. If the answer is max(dp[i]) then the answer should have been 3 whereas the answer is 5.Please comment on this @codedecode0111. Forgive me if I may have misunderstood it. :slight_smile:

Why my solution is giving TLE for second subtask?
Link-CodeChef: Practical coding for everyone

@vm666 Because you created a map which will take O(log n), you should make an array of size 10^7(you won’t get memory error) which takes O(1).

Here’s my solution - CodeChef: Practical coding for everyone

Hello @tej_17: We check the elements sequentially, so first element we check is 13, then 2, 8 and so on…
So, initially, dp[i] = 0 for all i.

Case 13: 
dp[13] = 0, so we update dp[13] = 1

Case 2:
dp[2] = 0, so we update dp[2] = 1

Case 8:
dp[2] = 1, so we update dp[2] = 2

Case 6:
dp[2] = 2, dp[3] =1, max = 2, so we update dp[2] = dp[3] =2 +1  = 3

Case 3:
dp[3] = 3, so we update dp[3] = 4

Case 1 :
We skip.

Case 9:
dp[3] = 4, so we update dp[3] = 5.

Max(dp[i] for all i) is 5 which is the required answer.

Thanks for clearing the confusion :slight_smile: @codedecode0111

No problem :slight_smile:

@admin waiting for official editorials of december long