You can also find video editorials for problems B-D on ak2006's Youtube channel!
1632A — ABC
Only a few strings have the answer "YES".
For n≥3, the answer is "NO".
Let n≥3 and the resulting string be a. For there to be no palindromes of length greater than 1, at least all of these inequalities must be true: a1≠a2, a2≠a3, and a1≠a3. Since our string is binary, this is impossible, so the answer is "NO".
For n≤2, there are 4 strings that have the answer "YES": 0, 1, 01, and 10; as well as 2 strings that have the answer "NO": 00 and 11.
Time complexity: O(n)
1632B — Roof Construction
The cost of construction is a power of two.
The cost of construction is 2k, where k is the highest set bit in n−1.
Let k be the highest set bit in n−1. There will always be a pair of adjacent elements where one of them has the k-th bit set and the other one doesn't, so the cost is at least 2k. A simple construction that reaches it is 2k−1, 2k−2, …, 0, 2k, 2k+1, …, n−1.
Time complexity: O(n)
Bonus: count the number of permutations with the minimum cost.
1632C — Strange Test
It is optimal to apply the third operation at most once.
It is optimal to apply the third operation at most once, because is does not decrease a and always makes b≤a. This means that after we use it, we can only apply the second operation.
If we don't apply the third operation, the answer is b−a.
Suppose we do apply it. Before that, we used the first and second operations some number of times, let the resulting values of a and b be a′ and b′ respectively (a≤a′,b≤b′). The answer in this case will be (a′−a)+(b′−b)+((a′ | b′)−b′)+1 = a′+(a′ | b′)+(1−a−b). This is equivalent to minimizing a′+(a′ | b′), since (1−a−b) is constant.
To do that, we can iterate a′ from a to b. For a fixed a′, we have to minimize a′ | b′, the optimal b′ can be constructed like this:
Set b′ to zero and iterate over bits from highest to lowest. There are 4 cases:
- If current bit of a′ is 0 and b is 1, set the current bit of b′ to 1.
- If current bit of a′ is 0 and b is 0, set the current bit of b′ to 0.
- If current bit of a′ is 1 and b is 1, set the current bit of b′ to 1.
- If current bit of a′ is 1 and b is 0, set the current bit of b′ to 1 and stop.
This works in O(logb) and can also be sped up to O(1) using bit manipulation.
Time complexity: O(b) or O(blogb)
Bonus 1: solve the problem in O(logb) or faster.
Bonus 2: prove that is optimal to have either a′=a or b′=b.
1632D — New Year Concert
Let's call a segment [l,r] bad if gcd. There at most n bad segments.
For a fixed l, as r increases, \gcd(a_l \ldots a_r) does not increase.
Suppose you change a_i into a big prime. How does this affect the bad segments?
Read the hints above.
Let's find all of the bad segments. For a fixed l, let's find the largest r that has \gcd(a_l \ldots a_r) \ge r - l + 1. This can be done with binary search and a sparse table / segment tree. If \gcd(a_l \ldots a_r) = r - l + 1, then the segment [l, r] is bad.
If we change a_i into a big prime, no new bad segments will appear. And all bad segments that have i inside of them will disappear. So we have to find the minimum number of points to cover all of them. This is a standard problem, which can be solved greedily: choose the segment with the smallest r, delete all segments that have r in them, and repeat. In our case, this is easy to do because our segments are not nested.
Time complexity: O(n \log n \log A) with a sparse table, where A is the maximum value of a_i.
Notes:
There are many different modifications to the previous solution, some of them use two pointers (since segments are not nested) and some of them update the answer on the fly while searching for the bad segments. Using a segment tree and two pointers you can get the complexity O(n (\log n + \log A)).
You can also use the fact that for a prefix, there at most O(\log A) different suffix \gcd values. This leads to another way to find the bad segments.
1632E2 — Distance Tree (hard version)
It is optimal to add edges of type (1, v).
Try to check if for a fixed x the answer is at most ans.
For a fixed x and answer ans, find the distance between nodes that have depth_v > ans.
For each node, find two children with the deepest subtrees.
Read the hints above.
Let f_{ans} be the maximum distance between two nodes that have depth_v > ans. If for some x the answer is at most ans, then either ans \ge depth or \lceil \frac{f_{ans}}{2} \rceil + x \le ans, since we can add an edge (1, u) where u is in the middle of the path connecting the two farthest apart nodes with depth_v > ans. Since f_{ans} decreases as ans increases, we can use binary search. Also note that we can use two pointers and increase ans as we increase x.
How to calculate f_{ans}? Let's find for each node its two children with the deepest subtrees. Let a_v and b_v be the depths of their subtrees (a_v \ge b_v). If there are not enough children, set this values to depth_v. If b_v > 0, do f_{b_v-1} := \max(f_{b_v - 1}, a_v + b_v - 2 \cdot depth_v). After this, iterate i from n - 2 to 0 and do f_i = \max(f_i, f_{i + 1}).
Time complexity: O(n) or O(n \log n) with binary search.
Note: To solve E1, it is enough to calculate f_{ans} in O(n) or O(n \log n) for each ans. One way to do that is to find the diameter of the resulting tree after repeatedly deleting any leaf that has depth_v \le ans (1 is also considered a leaf).