Education Codeforces Round 82 Reflection

February 13, 2020

A: Erasing Zeroes (00:02)

Pop all the zeroes in the front and the end of the string. Then count the number of 00s in the array.

B: National Project (00:10, +1)

Very annoying to read and understand question. The code is not very long.

The required time is max(n,tgood)max(n, t_{good}) where tgoodt_{good} is the time to have t2\lceil \frac{t}{2} \rceil high-quality pavement.

tgood=ng(g+b)+(nmodg)t_{good} = \lceil \frac{n}{g} \rceil \cdot (g + b) + (n\bmod g) for nmodg0n\bmod g \not= 0, and tgood=ng(g+b)bt_{good} = \frac{n}{g} \cdot (g + b) - b for nmodg=0n\bmod g = 0.

C: Perfect Keyboard (00:18)

Build an edge between two adjacent letters. If they form a chain, output the chain then the remaining characters. Otherwise, it is impossible.

D: Fill The Bag (00:43, +1)

I have a few guesses to this question. Some of them were correct and some of them weren't, which contributed to the 1 WA.

Guess 1 (Wrong): you should greedily consume the box from the largest to the smallest that can be used without breaking first.

Countercase: n=72,m=2,a=32,128n = 72, m = 2, a = {32, 128}

Guess 2 (Correct): you should handle from the lowest bit of nn to the highest bit of nn.

So it is just greedily finding a box that is larger than the current bit, breaking it down until there is a box of the same size, then adding this cost to the total cost.

Drafting some cases on paper, by marking down nn and aa in binary forms, does help me think of the solution much more quickly.

E: Erase Subsequences (01:00, +1)

The problem can be transformed to the problem: is it possible to find two increasing, distinct sequences such that the characters they are referring to are exactly tt?

Tips (not actually tips): read the constraints carefully.

I missed the last line of the constraints: the total length of strings ss doesn't exceed 400. So I tried to guess that the sequence in step 1 must be maximum, but that was not the case (WA on test 4).

F: Number of Components

Did not attempt. Noted the unusual limit of ci1000c_i \leq 1000.

G: Sum of Prefix Sums

Thought that this is probably centroid decomposition, tried coding after finishing A to E. After coding most of the helper functions, suddenly realized that I have no idea how to maximize the required function.