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

Contest link: Click here

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

Auto comment: topic has been updated by MagicPotato (previous revision, new revision, compare).Auto comment: topic has been updated by MagicPotato (previous revision, new revision, compare).is the last one using convex hull trick to solve dp at each level??

Any other approaches welcome

Yes, https://ideone.com/61Va4F

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

Will the problems be moved to practice ?

They have been moved. :)

Is ICO Contest based on partitions? :P

Hi, so to me seems like a notorious coincidence.

How to solve partition count? I can only come up with dp solution for 40pts.

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.

Just figured it out! Thanks for your help anyway.