Educational Codeforces Round 150 Editorial

I'm going to share some of my solutions since they are not mentioned in the editorial.

For 1841C - Ranom Numbers, I basically did some sort of brute force, checking every possible replacement for a character and taking the maximum.

The trick is that when you decrease a character, some of the characters that are directly affected by you may not be affected anymore (or may be affected by some other letter on the right of the current letter), and when you increase a character, some of the characters are before you and not affected by anybody may be affected by you.

To check this, I made a vector called where where where[i] are the indices where character i occurs, so that when checking whether there is a greater or smaller character after some index it becomes easy with a std::lower_bound (or binary search). Moreover, I maintain a frequency of all non-affected characters before me and all characters that are directly affected by me, and then do some calculations. (I admit it, the solution is hairy) Code here

For 1841D - Pairs of Segments, I sorted according to the left boundary (and so let [l[i], r[i]] denote the intervals after sorting).

Now, use Dynamic Programming where dp[i] is the minimum number of removed intervals starting at i, and the transitions are either dp[i] = dp[i + 1] + 1 where we just remove the current interval or we try to see if we can merge it, so we loop over all segments with index j > i to find the segment that intersects with i with minimum right boundary, let this interval be x (if not found, just don't proceed with this transition), and let R = max(r[x], r[i]) (basically the right boundary after merging)

and then we basically try to minimize with dp[j] + removed where j is such that j > i and l[j] > R and removed denotes all segments k where i < k < j and k is not x, which are all the removed segments. Code here

For 1841E - Fill the Matrix, I used the same general idea: we just collect all contiguous segments in the same row in the matrix by considering from the bottom row to the top row and noting that some of the black towers split some segments in two.

However, I feel my implementation was a bit simpler, it was using an idea called deltaing that I learned from Algorithms Live's amazing episode 9: "Solution Bags".

The idea is to maintain

• A vector called where where where[i] are the indices where the number i in the array.

• A set (called st cause I didn't think what to call it) containing all the indices of the black cells in the current row. It initially contains -1 and n (since indices are zero-based)

• A vector segments where segments[i] denotes the frequency of all segments of size i, initially all zeros except for segments[n] = n, this is to denote that for all we know, all segments didn't occur, and a segment of size n occurs n times (as if the table is empty), and we will update this as we go (this is the "deltaing" part)

Now, we loop on row j from n down to 1, and we note that there are black cells in where[j] that split the segments. How do we know which segments are being split? Using the set st: -

Suppose that a black cell appears at index i, we can find the previous black cell as L = *prev(st.lower_bound(i)) and the next black cell as simply R = *st.lower_bound(i), and we know they both exist since we started with -1 and n in the set. The update goes as follows:

• The segment with length R - L - 1 will be removed, meaning that it will not exist for j rows from now on, so we decrement segments[R - L - 1] -= j, meaning that for all we know, we assumed it exists for all segments[R - L - 1] rows but now we know that it will not exist for j rows (from now on).

• A segment with length R - i - 1 will exist now, so we increment segments[R - i - 1] += j, meaning that for all we know, unless we update it, a segment of length R - i - 1 will exist for j more rows.

• A segment with length i - L - 1 will similarly exist now, so segments[i - L - 1] += j, for the same exact reason.

• We insert i in the set st.

After we're done we basically have the frequency of each size of a segment, and we can just loop greedily from the largest segment to the smallest segment and fill as much as we can with our m integers. Code here.