### ista2000's blog

By ista2000, history, 3 years ago,

Hello wonderful Codeforces Community!

I would like to invite you to the 6th and the last contest of the Preparatory Series for the Indian Computing Olympiad hosted by us. The contest will start on 4th Januray, 2018 7:30 PM IST.

The problems are set by Adhyyan Sekhsaria(Adhyyan1252), Soham Mukherjee(soham_1234) and me(MagicPotato). I would also like to thank Taranpreet Singh(taran_1407) to help us with the testing and editorials. :D

There will be 4 problems and 3 hours to solve them. The difficulty will be around the INOI level although anyone can participate for the joy of solving the problems. :D

I hope you like the problems and this serves as a great start to the year. :)

All the best, see you on the leaderboards. :D

• +13

 » 3 years ago, # |   0 Auto comment: topic has been updated by MagicPotato (previous revision, new revision, compare).
 » 3 years ago, # |   0 Auto comment: topic has been updated by MagicPotato (previous revision, new revision, compare).
 » 3 years ago, # |   +12 is the last one using convex hull trick to solve dp at each level??Any other approaches welcome
•  » » 3 years ago, # ^ | ← Rev. 2 →   0
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Yes, that's the intended solution. Also instead of using a dynamic convex hull for reversing the max/min, its easier to process the DP backwards, interchanging what represents m and c in y = mx + c. Dynamic CHT is kinda an unnecessary thing to do here.As for other approaches. I have found someone using divide and conquer optimization too. Here is the solution.EDIT: The intended solution: https://ideone.com/pWkx7f
 » 3 years ago, # |   0 Will the problems be moved to practice ?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 They have been moved. :)
 » 3 years ago, # |   +13 Is ICO Contest based on partitions? :P
•  » » 3 years ago, # ^ |   +4 Hi, so to me seems like a notorious coincidence.
 » 3 years ago, # |   0 How to solve partition count? I can only come up with dp solution for 40pts.
•  » » 3 years ago, # ^ |   +8 First of all, let's calculate for each i the rightmost index j such that in subarray [i....j] there are atmost k distinct values. Let's call it maxi[i]. I did this by maintaining count of elements in current range (use unordered map) and deque.Now let dp[i] denote the answer if the original string was s[i...n]. Clearly answer is dp[1]. While updating dp[i], you can make partition of current substring at i, i + 1.....maxi[i]. Let's say you make partition at j then you have to add dp[j + 1] to dp[i]. So, we have to add the summation dp[j], j ranging from i + 1 to maxi[i] + 1. This can be done using fennwick/ segment tree.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Just figured it out! Thanks for your help anyway.