Блог пользователя ista2000

Автор ista2000, история, 7 лет назад, По-английски

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

  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

Any other approaches welcome

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Will the problems be moved to practice ?

»
7 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Is ICO Contest based on partitions? :P

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +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.