unofficial English tutorial of KDOI round 10

T1 bargain

Operation 1 denotes "Choose a digit and delete it", and operation 2 denotes deleteing all the remaining digits in one go.

Hint 1: When operation 2 is better than operation 1?

Hint 2: Enumerate from right to left.

It's easy to notice that we won't leave too much digits for operation 2. Furthermore, the number of left digits, k, won't exceed 5, since 10^k > k\cdot 10^5 for all k>5.

Consider dynamic programming. Let f_{i,j} be the minimum cost to delete all the last i digits, while j digits are deleted using operation 2.

Let c_i be the i-th digit of n, counting from the least significant digit. Now we have the following transition:

Thus, we can solve this problem in O(k\log n) time, where k=5 in this case.

T2 water

The hardest problem in this round!

Operation 1 denotes subtraction, and operation 2 denotes addition.

Hint 1: Adjust the order of the operations.

Hint 2: Can you determine whether a sequence of operation 1 is valid?

Hint 3: Use binary search.

We need some observations to make this problem easier.

Observation 1

One can always use all operation 1 before any operation 2.

It's straightforward, so I omit the proof.

However, it leads to the first key observation:

Observation 2

Let a'_i be the temperature of vertex i after we use up operation 1.

The answer is yes (i.e. Huoyu) if and only if \forall j \in \text{son}_i, a'_j \le a'_i, and a'_1 \le 0.

To proof it, consider the root. Since we can only increase the temperature using operation 2, a'_{root} \le 0 should hold. Then we add -a_{root} to the root, and for every son j, there should be a'_j \le a'_{root}, or a'_j will remain positive.

Now the temperature of root is 0, so we can simply remove it and check the remain forest. The above observation can then be proved by induction. \square

Let x_i be the number of operation 1 done on vertex i. (If i isn't a leaf, we can simply let x_i = \sum\limits_{j\in \text{son}_i} x_j.)

We need to check whether we can managed to satisfy the following inequalities:

\forall j \in \text{son}_j, a_i - x_i \ge a_j - x_j \\ x_1 \ge a_1

However, it seems impossible to maintain the information, since a_i and x_i can be extremely large. So we need observation 3:

Observation 3

for all vertex i, there exists an interval [l_i, r_i] (possibly empty), such that x_i = p is valid (with all the constraints inside subtree i) \iff p \in [l_i,r_i].

The proof also needs induction.

Firstly, l_i is easy to compute: l_i = \max\{\sum\limits_{j \in \text{son}_i}l_j, a_i\}. Suppose we know r_i, and every subtree satisfy the above lemma.

It's obvious that we only need to consider the case where there aren't any empty intervals.

Suppose x_i=p\ (p>l_i) is valid. Now we need to proof x_i=p-1 is also valid.

There must exist a j \in \text{son}_i whose x_j > l_i, or p > l_i is violated. Then we decrease x_j by 1.

For j, a_i - x_i \ge a_j - x_j still holds, since we decrease 1 at both sides of the inequality; and for k other than j, the left hand side increases by 1 while the right hand side remains the same.

Thus, x_i=p-1 is still valid. \square

One corner case is that |\text{son}_i|=1, then we simply need to inherit [l,r] from its son.

Given observation 3, a fan of Um_nik should immediately come up with binary search.

In detail, we can first compute l_i, then use binary search to compute r_i. We only need to check whether x_i = p is valid.

Enumerate j through every son vertex of i. Since a_i - x_i \ge a_j - x_j we have x_j \le a_i-a_j+x_j. So x_j \in [l_i, \min\{r_i,a_i-a_j+x_j\}]. If this interval is empty then p is obviously invalid.

Otherwise, we can compute bound of x_i by summing up all these intervals, and p is valid iff it falls into such bound.

Thus, we can solve the problem in O(n \log V) time.

Please take care of the bound while binary searching, and maybe __int128 is neccessary in some cases.

T3 anti

Hint 1: solve the 2/5 scored problem, i.e. come up with a solution without maximizing k.

Hint 2: solve Special Property B, i.e. \Sigma=2.

This is a deterministic approach, which needs some case work.

Consider when the answer is no (i.e. Shuiniao).

• If s only contains one kind of character; Or
• If s only contains two kinds of character, and the second kind only occurs at the middle of string (i.e n is odd and only s_{(n+1)/2} is different from the rest).

It's obvious that such condition is sufficient.

We can also show that such condition are necessary, by giving a construction of the answer sequence.

After we exclude the situation with no solution, one should consider how to maximize k. After examining anti2.ans one should notice almost every subsequence has length 2. It is because 2 different characters can form a valid subsequence, which seems optimal.

stage 0

So, if we only need to calculate k, one can easily come up with a greedy solution: Every time, we pick 2 diffrent characters with the maximum and the second maximum times of occurrence. Then we pack the first occurrence of both characters into a subsequence, and remove such 2 occurrence.

It's not hard to proof that k is maximized. If s becomes empty then we can directly output the answer. Otherwise we need to merge the remaining letters into existed subsequences.

Obviously, only 1 kind of character will remain in s. WLOG let a be such character.

stage 1

We enumerate from 1 to n. If s_i \neq \mathtt a we merge every remaining a before i into the subsequence which i belongs to.

It can be shown that, after this stage, only a trailing sequence of a(possibly empty) will remain. Every a before any character other than a will be removed.

stage 2

Let l_i be the number of as in the subsequence which i belongs to, on the left of i. Specially, if i is not matched with an a in stage 0, let l_i=0.

Let d be the length of the remaining a sequence.

If there exists an i where s_i \neq \mathtt{a} \land l_i \neq d we can simply append all the remaining a after i.

Otherwise, if there exists more than 1 i satisfying s_i \neq \mathtt a:

Let p,q be the first two such i.

• If d>1 we can append the first remaining a after p, and the rest after q.
• Otherwise we can move the first a with p to the belonging subsequence of q. Now q will have two as before it, and nothing behind it, and p will be alone. Then, we can directly append the remaining a(only 1) after p.

Otherwise, there will be no solution, as the string must satisfy one of the condition given above.

Thus, we solved this problem in O(n \log n) time. Note that we need to sort the subsequence. Maybe careful implementation can reach linear complexity.

T4 show

Hint 1: solve Special Property D.

Hint 2: consider sqrt balancing.

It is not hard for one to notice, given r, troupe in room p exits if and only if l \le q_p, where q_p is a constant which only depends on r and p. (Specially, let q_1=r.)

Consider maintaining q_p as we move r from 1 to k.

Suppose we move to i from i-1. Only q_{a_i} is affected, which becomes \max\limits_{v \in \text{out}_{a_i}}\{q_v\}.

So the problem is translated into a form of 2D counting, because we only need to count \sum_{i} [q_i \ge l], which can be done in O((n+q) \log n) time by storing all the queries in advance and using fenwick tree.

However maintaining q_p is of wrong complexity, since the out degree of a vertex can be large.

Use the balancing trick. For all vertices x with out degree greater than B, we can maintain q_x when updating q_{a_i}; for other vertices, we can simply enumerate through the edges. Choose B=\sqrt n, and we can complete this in O(n \sqrt n) time.