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.
How to solve I ?
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.
I had a similar idea but could not figure out the details. If you can post your code,that would be helpful.
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<num, pos'\leq last[num_2] < last[num]$$$, Now while fixing $$$pos$$$, if you iterate on $$$num$$$ then you can keep track of a stack of $$$num_2$$$ sorted (increasing by $$$num_2$$$ and decreasing by $$$last[num_2]$$$). The entries of these stack give you the information of which 2d ranges to subtract. Since this stack can be maintained in amortized $$$O(n)$$$, the whole algorithm becomes $$$O(n^2)$$$
is there any editorial available? i am not able to solve I.
Yeah! But in Bengali I think. :(
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.
Ok. Then wait for him.
I got just 265 points. :(
Is there any editorial of the contest?