The second inequality comes directly from the first one.

The main idea of the construction is to fill the columns with [0, 1, 2, ..., r - 1] and [r - 1, r - 2, ..., 1, 0] alternatively.

The tricky part is when the number of columns is odd. In this case, we can construct a special case for three columns and expand to the case of any odd columns.

To make it easier, let's assume a = 0.

There is a naive upper bound for the number of rows: , the left hand side is the sum of all rows, and the right hand side is the minimum sum of all columns. The inequality gives , and in fact we can always construct a solution of .

Proof:

adv(0) is the number of men needed to increase percentage from 0% to at least 0.5%. Hence

, the fractional part of adv^k(p) / n is always between [0.5, 1), let it be B (this is true because for n ≥ 200, each men contributes  ≤ 0.5%. If B is not in this range, you actually need less men, contradiction!)

Then finally we have

The greedy approach works for n ≥ 200 (not sure if it works for n < 200). Here's the idea

Let pct(i) be the rounded percentage for i / n. And adv(i) be the least number such that pct(adv(i)) = pct(i) + 1, i.e. the least number of men required to increase the rounded percentage by 1 (always exists for n ≥ 200)

The sum we have before determining the unknown is . To increase the answer, let's consider the i-th language. We can add adv(C_i) - C_i to increase percentage by 1, another adv²(C_i) - adv(C_i) to increase by 1 more, another adv³(C_i) - adv²(C_i) for 1 more, and so on...

The key to the greedy approach is there can be infinitely many new languages, which means we can always add adv(0) to a new language to increase the answer by 1.

For n ≥ 200, it's easy to prove that (proof is in comment below). Hence, there's no point to increase a language by two percentages. So the greedy approach works here.

PS. I actually think this is what the tutorial is trying to say, though they explained it poorly.

The final standing is here: http://moscode.it-edu.mipt.ru/team2018

You can deduce each element one by one.

For example, to make the sequence 10 4 3 5 7, the two constructed sequence should be 7 2 1 2 7 and 3 2 2 3

It can always be achieved with at most two operations [1, n], [1, n - 1].

So just check if it's possible to achieve in one operation. Otherwise, construct with the two intervals.

We failed test 6 when we missed some initialization.

No idea what the test is, though it should be a fairly simple test, IMO.

For problem D, we do dynamic programming on the state dp[odd][even][p], where odd, even is the number of connected components of odd/even size, p is the parity of the edges inside connected components that hasn't been added.

UPD: turns out to be a silly bug, the above dynamic programming should be correct.

How to solve problem F? How do we use the constraint of ?

So what's the idea of the intended solution? Any hint?

Do you mean it's equivalent to problem J of this contest?

Is there any theoretical proof to the construction instead of verifying with a program?

No letter appears in more than one cell in the input grid.

Yep. It can be done greedily if you regard the value of a card as a+b since the scores that the two players get are a,0 and 0,b in both cases, where the difference would be a and -b respectively. So you can set this value for each card and greedily select the pictures.

Of course you still have to handle some other cases :)

Will there be an online mirror any where available on the Internet?

That'll be Heavy-Light Decomposition.

Do anyone know how to solve Subtask 3 of Factories?

I used Shortest Path to solve Subtask 1 and LCA plus brute-force for Subtask 2.

Can anyone explain how D-large is solved? Tks~

Really appreciate the efforts from you guys.

When will the tutorial for E be available? Really looking forward to it!!

I've got a problem with the site: is it possible to check out my own past submissions for a particular problem?

Please post the editorial for div. 1!!!