Ra16bit's blog

By Ra16bit, history, 6 months ago, 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 Heltion 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. tco, Comments (7)
 » 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?
• »
»
»
2 months ago, # ^ |
Rev. 2

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$).

k segments
xx | xx | xx | xx | xxxxx
^   <--->
|    M_k
|
index i - M_k

k - 1 segments
xx | xxx | xxxx | xxxx
^   <-->
|   M_{k-1}
|
index i - M_{k-1}

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!