The Wildcard Round of TopCoder Open 2021 Algorithm is over, so the list of Semifinals advancers is finalized now. I've put some stats about them into the table below. Here we have two former champions, and four people who had 2nd place before!
Good luck to all the semifinalists in November!
Qualified from | TC Handle | TC Rating | CF Handle | CF Rating | Country | Onsites before | Best place before |
---|---|---|---|---|---|---|---|
Stage 1 | lyrically | 3253 | hos.lyric | 3204 | Japan | 3 | 2nd @ TCO 2019 |
Stage 2 | Petr | 3608 | Petr | 3414 | Switzerland | 13 | Four times TCO Algo Champion (2006, 2013, 2015, 2018) |
Stage 3 | tourist | 3841 | tourist | 3819 | Belarus | 8 | Three times TCO Algo Champion (2014, 2019, 2020) |
Stage 4 | bqi343 | 3560 | Benq | 3745 | United States | 1 | Semifinalist @ TCO 2020 |
Round 4 | ACRush | 3522 | ACRush | 3047 | China | 8 | 2nd @ TCO 2010 |
Round 4 | scott_wu | 3437 | scott_wu | 3169 | United States | 5 | 3rd @ TCO 2017 |
Round 4 | SpyCheese | 3179 | SpyCheese | 2643 | Russia | 0 | Qualified to Semifinals @ TCO 2019 |
Round 4 | gs14004 | 3039 | ko_osaga | 3103 | South Korea | 0 | |
Round 4 | ecnerwal | 3488 | ecnerwala | 3336 | United States | 3 | 2nd @ TCO 2020 |
Round 4 | Um_nik | 3334 | Um_nik | 3489 | Russia | 5 | 4th @ TCO 2018 |
Round 4 | neal_wu | 3294 | neal | 3147 | United States | 1 | 9th @ TCO 2020 |
Round 4 | Heltion | 2642 | Sugar_fan | 2951 | China | 0 | |
Round 4 | kuniavski | 2826 | PavelKunyavskiy | 2845 | Russia | 2 | 2nd @ TCO 2015 |
Round 4 | maroon_kuri | 3063 | maroonrk | 3400 | Japan | 1 | Semifinalist @ TCO 2019 |
Wildcard | grumpy_gordon | 2645 | never_giveup | 2762 | Russia | 0 | |
Wildcard | krijgertje | 2786 | krijgertje | 2937 | Netherlands | 5 | 5th @ TCO 2016 |
By "Onsites before" above I mean TCO Algorithm Onsites, of course. If you find some mistakes in the table, feel free to tell me via direct message.
How to solve the problem B from regionals qualifier round 2: Given n <= 1e5 positive numbers, each up to 2^25. In one move you can replace any 2 adjacent numbers with their sum. Find minimum number of moves to make the sequence non decreasing.
Each move decreases the length of the sequence by 1, so an equivalent task is to maximize the length of the final sequence. And yet another way to look at it is that you are dividing the input sequence into pieces in such a way that the sums of those pieces are non-decreasing and their number is maximized.
Given a non-decreasing sequence, let its "width" be the size of the last (biggest) element.
If you have two options how to make a non-decreasing sequence out of a prefix of input and the options have equal length, the one with the smaller width is better. This is because anything you can append to a wider sequence, you can also append to a narrower one.
The most important observation of the task is the following one: out of all non-decreasing sequences that can be produced from a given sequence, the minimum possible width is always obtained for some sequence that also has the maximum possible length. (Comment if you can't prove this.)
Thus, we can do DP on prefixes and for each prefix we just need to remember the length and width of the most narrow out of longest solutions.
When processing a new sequence, you are looking for the smallest width it can have -- i.e., the smallest number of pieces in the last element sufficient that the most narrow sequence built from the rest can go before the last piece. There are some ways how to do this in O(n log n), but it's also possible to do it in O(n) by maintaining the feasible candidates in a deque.
Will be video-editorials that you've made live on Hopin be published anywhere, or they were not saved?
Thank you
How to prove this "most important observation"? I tried for an hour but couldn't quite get it right. It relies also on the fact that all numbers are >= 0, right?
I think I finally came up with a proof that works after trying for many hours :) misof Is this the proof you had in mind?
Definitions
Valid segmentation of length $$$i :=$$$ a way to cut up the array into $$$i$$$ contiguous segments (using $$$i - 1$$$ cuts) such that the sum of values in each segment is $$$<=$$$ sum of values in next segment.
$$$M_l :=$$$ minimum width among any valid segmentation of length $$$l$$$
$$$[i:j] :=$$$ contiguous subarray starting at index $$$i$$$ and ending at index $$$j$$$
Theorem
f there exists a valid segmentation of length $$$k$$$ in an array where all values $$$>= 0$$$, then $$$M_k <= M_{k - 1}$$$, for any $$$k >= 2$$$.
In words: When cutting the array up into more segments the minimum possible width only goes down.
Proof (by induction)
Inductive hypothesis
If there exists a valid segmentation of length $$$k$$$ ($$$k >= 2$$$) in an array with values $$$>= 0$$$, then $$$M_k <= M_{k - 1}$$$.
Base case
It holds for $$$k = 2$$$ since the only valid segmentation of length 1 has width $$$N$$$ (where $$$N$$$ is the length of the array), and any valid segmentation of length 2 has width $$$< N$$$.
Inductive step
Assume it holds for $$$k - 1$$$. Now we must prove that it holds for length $$$k$$$. If there does not exist a valid segmentation of length $$$k$$$, then the conditional statement in the theorem does not hold and the proof holds. Therefore we can assume for the remainder of the proof that a valid segmentation of length $$$k$$$ exists.
Let's assume by contradiction that the inductive step does not hold and that instead $$$M_{k - 1} < M_k$$$. This scenario is depicted in the drawing below (array ends at index $$$i$$$).
From the definition of $$$M_{k}$$$, we know that it is possible to split prefix $$$[0:i-M_k]$$$ (see drawing) into $$$k - 1$$$ segments. From the contradiction hypothesis we also have that $$$i - M_{k - 1} > i - M_k$$$, and therefore it is possible to split $$$[0:i-M_{k - 1}]$$$ into $$$k - 2$$$ segments.
From the inductive hypothesis we know that $$$M_{k - 1} <= M_{k - 2}$$$. Therefore instead of cutting $$$[0:i-M_{k - 1}]$$$ into $$$k - 2$$$ segments, we can cut it into $$$k - 1$$$ segments and achieve a width that is not greater than it. Then we add on top of it segment $$$[i-M_{k-1}+1:i]$$$ which is guaranteed to make a valid segmentation since the width of the $$$k-1$$$'th segment is not greater than before. Note: this argument only holds because all values in array are $$$>= 0$$$.
We have now achieved a valid segmentation of $$$k$$$ segments with a width of $$$M_{k - 1} < M_{k}$$$. This is a contradiction (since we defined $$$M_{k}$$$ to be the minimum width among any valid segmentation of length $$$k$$$), and therefore our hypothesis was wrong. Therefore we must have $$$M_{k - 1} >= M_{k}$$$ which proves the inductive step.
Corollary
Let's choose in the theorem above $$$k$$$ to be equal to be the maximum valid segmentation. Then we have that $$$M_k <= M_{k - 1} <= ... <= M_{2}$$$. Therefore there exists a maximum segmentation whose width is equal to the minimum width among any valid segmentation.
Congrats tourist!