### upobir's blog

By upobir, history, 4 years ago,

Hello, Codeforces community.

It is my pleasure to invite you all to the replay contest of National High School Programming Contest 2020 (National Round), which took place some weeks back with the young contestants of Bangladesh as participants. The contest is loosely based on IOI rules and syllabus, with problems having subtask-based scoring system.

The contest will begin at 13:00 UTC on 15 July, 2020 and will run for 5 hours. There will be 12 problems in total.

The contest platform is toph.co, you can register for the contest here.

The problems of the contest were authored and reviewed by curly_braces, fsshakkhor, gola, rebornplusplus, Hasinur_, Hasnaine_, Moshiur_, I_love_ProParThinkNot, ishtupeed, ovis96, SiamH, Shefin_, solaimanope, tanus_era, upobir.

You can use C++11 GCC 7.4, C++14 GCC 8.3, C++17 GCC 9.2, C11 GCC 9.2, PyPy 7.1 (2.7), PyPy 7.1 (3.6), Python 2.7 and Python 3.7 in this contest.

We look forward to your participation and hope that you enjoy the problemset, best of luck in the contest.

• +64

 » 4 years ago, # |   0 How to solve I ?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 That was my problem, Here's an incomplete solution: the idea is dynamic programming, first of all, to all important partitions we can greedily assign a lexicographically minimum nondecreasing subsequence. We'll use this assigned subsequence to count the partitions. Let $dp[pos][num]$=count of partition of prefix $1\cdots pos$ where $num$ will be greedily chosen from last subarray. Using this definition you should be able to come up with a $O(n^3)$ idea using some cumulative sum. The idea can be made more efficient by actually observing that the $dp[pos'][num']$ who contribute to $dp[pos][num]$ can be calculated using 2d cumulative sum and subtracting some parts. I'd advice that you compute the dp table by your hand for some samples and will realize what to subtract.
•  » » » 4 years ago, # ^ |   0 I had a similar idea but could not figure out the details. If you can post your code,that would be helpful.
•  » » » » 4 years ago, # ^ |   0 Formally if you define $last[num]$ as the latest index on which there was $num$, then intially $dp[pos][num]=$sum of all $dp[pos'][num']$ with $pos' \leq last[num], num' \leq num$. Now the $dp[pos'][num']$ who are deleted are those for which there exists \$num'\leq num_2
•  » » » 4 years ago, # ^ |   +5 is there any editorial available? i am not able to solve I.
•  » » » » 4 years ago, # ^ |   0 Yeah! But in Bengali I think. :(
•  » » » » » 4 years ago, # ^ |   0 sorry but i can't understand Bengali. if problem creator can write logic part and give code than it would be very easy to understand solution.
•  » » » » » » 4 years ago, # ^ |   0 Ok. Then wait for him.
 » 4 years ago, # |   0 I got just 265 points. :(
 » 4 years ago, # |   0 Is there any editorial of the contest?