Topcoder SRM 813 is scheduled to start at 11:00 UTC-4 on Sept 17, 2021.
Registration is now open for the SRM in the Arena or Applet and closes at 10:55 UTC-4. The coding phase will start at 11:05 UTC-4, so make sure that you are all ready to go. Click here to what time it starts in your area.
Please take a look at our How to Compete guide to understand Topcoder Algorithm rounds better.
Some Important Links:: Match Results (match results, rating changes, challenges, individual test case results), Problem Archive, Problem Writing, Algorithm Rankings, Editorials and Older Editorials(SRM 710 and before),
Best of luck!
- The Topcoder Team
How to solve the 600 point (div 1) problem ?
$$$dp[S][C]$$$ with transitions in $$$O(n^2)$$$ — the number of ways to cover $$$S$$$ points with $$$C$$$ segments.
For each $$$dp[i][j]$$$ count the number of bad ways to choose segments (the ones where there's at least one uncovered point), then subtract it from all ways to get the actual value.
To count that, iterate over the position of the first uncovered point and the number of segments to the left of it. Use already calculated dp to cover everything on the left, then some easy combinatorics to place the remaining segments on the right, then cnk to choose the segments to place on the left from all segments.
Thanks
That is 100^4 right? Is there a 100^3 solution?
Yeah, it's $$$O(n^4)$$$ but the constant is $$$\frac 1 4$$$, so it passes freely (in C++ Kappa).