ista2000's blog

Invitation to ICO Preparatory Contest 6
By ista2000, history, 7 years ago, In English

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(AsleepAdhyyan), Soham Mukherjee(antipr000) and me(ista2000). 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

  • Vote: I like it
  • +13
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ista2000 (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ista2000 (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it +12 Vote: I do not like it

is the last one using convex hull trick to solve dp at each level??

Any other approaches welcome

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will the problems be moved to practice ?

→ Reply
»
7 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Is ICO Contest based on partitions? :P

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Hi, so to me seems like a notorious coincidence.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply