Div2B — Bear and Three Musketeers
Warriors are vertices and "knowing each other" is an edge. We want to find connected triple of vertices with the lowest sum of degrees (and print sum - 6 because we don't want to count edges from one chosen vertex to another).
Brute force is O(n3). We iterate over all triples a, b, c and consider them as musketeers. They must be connected by edges (they must know each other). If they are, then we consider sum of their degrees.
We must notice that there is low limit for number of edges. So instead of iterating over triples of vertices we can iterate over edges and then iterate over third vertex. It gives us O(n2 + nm) and it's intended solution. To check if third vertex is connected with other two, you should additionally store edges in 2D adjacency matrix.
It's also possible to write it by adding "if" in right place in brute forces to get O(n2 + nm). Check it out in code.
Div1A — Bear and Poker
Any positive integer number can be factorized and written as 2a·3b·5c·7d·....
We can multiply given numbers by 2 and 3 so we can increase a and b for them. So we can make all a and b equal by increasing them to the same big value (e.g. 100). But we can't change powers of other prime numbers so they must be equal from the beginning. We can check it by diving all numbers from input by two and by three as many times as possible. Then all of them must be equal. Code
Alternative solution is to calculate GCD of given numbers. Answer is "YES" iff we can get each number by multiplying GCD by 2 and 3. Otherwise, some number had different power of prime number other than 2 and 3. Code
Div1B — Bear and Blocks
In one operation the highest block in each tower disappears. So do all blocks above heights of neighbour towers. And all other blocks remain. It means that in one operation all heights change according to formula hi = min(hi - 1, hi - 1, hi + 1) where h0 = hn + 1 = 0. By using this formula two times we get height after two operations: hi = max(0, min(hi - 2, hi - 1 - 1, hi - 2, hi + 1 - 1, hi + 2)) and so on. From now I will omit max(0, ...) part to make it easier to read.
After k operations we get hi = min(Left, Right) where Left = min(hi - j - (k - j)) = min(hi - j + j - k) for and Right is defined similarly. hi becomes zero when Left or Right becomes zero. And Left becomes zero when k = min(hi - j + j) — we will find this value for all i. If you are now lost in this editorial, try to draw some test and analyze my formulas with it.
For each i we are looking for min(hi - j + j). We can iterate over i from left to right keeping some variable best:
best = min(best, h[i]);
best is answer for i;
best++;
We should to the same for Right and take min(Left, Right) for each i. Then final answer is maximum over answers for i. Code
Div1C — Bear and Drawing
Let's consider a tree already drawn on a strip of paper. Let's take first vertex on the left and last vertex on the right (in case of two vertices with the same x, we choose any of them). There is a path between them. Let's forget about vertices not on this path. A path divides a strip into 1D regions.
What can be added to the main path? Only simple paths attached to it with one edge. So it can be one of the following structures — Y-letter or Line:
Note that Y-letter can have long legs but its central part can have only one edge.
How to check if given tree is a path + Y-letters + Lines? First, let's move from each leaf till we have vertex with degree at least 3, marking vertices as deleted. We don't mark last vertex (that with degree at least 3) as deleted but we increase his number of legs. Finally, for each not-deleted vertex we count his not-deleted neighbours for which degree - min(legs, 2) > 1 — otherwise this neighbour is start of Line or Y-letter. Each vertex on the main path can have at most two neighbours that also belong to the main path. There can be more neighbours but they must be in Lines or Y-letters — that's why we didn't count them. So answer is "No" iff for some vertex we counted more than two neighbours. Code
Div1D — Bear and Cavalry
Let's sort warriors and horses separately (by strength). For a moment we forget about forbidden assignments. Inversion is a pair of warriors that stronger one is assigned to weaker horse. We don't like inversions because it's not worse to assign strong warriors to strong horses: A·B + a·b ≥ A·b + B·a for A ≥ a and B ≥ b. Note that repairing an inversion (by swapping assigned horses) decreases number of inversions — prove it by yourself (drawing a matching with intersections could be helpful). Without any restrictions the optimal matching is when we assign i-th warrior to i-th horse (indexed after sorting) — to get no inversions.
Let's go back to version with forbidden connections. We have n disjoint pairs which we can't use. We will prove that there exists an optimal assignment where (for all i) i-th warrior is assigned to j-th horse where |i - j| ≤ 2.
Let's take an optimal assignment. In case of ties we take the one with the lowest number of inversions. Let's assume that i is assigned to i + 3. There are at least 3 warriors j > i assigned to horses with indices lower than i + 3. So we have at least 3 inversions with edge from i to i + 3 (warriors on the left, horses on the right):
Above, connection warrior-horse is an edge. Then inversions are intersections. Swapping horses for warriors i and j (where j belongs so some red edge) would decrease number of inversions and it wouldn't decrease a score. We took an optimal assignment so it means that it's impossible to swap horses for them. Hence, for each red edge we can't change pair (black, read) into the following blue edges:
So one of these blue edges is forbidden. Three red edges generate three pairs of blue edges and in each pair at least one blue edge must be forbidden. Note that all six blue edges are different. All blue edges are incident to warrior i or to horse i + 3 but only one forbidden edge can be incident to warrior i and only one forbidden edge can be incident to horse i + 3. We have at most two forbidden edges incident to them so it can't be true that three blue edges are forbidden.
By cases analysis we can prove something more — that there can be only three possible types of connecting in an optimal assignment. First type: i can be connected to i. Second: warrior i with horse i + 1 and warrior i + 1 with horse i. Third: warriors i, i + 1 and i + 2 are connected with horses i, i + 1, i + 2.
It gives us O(nq) solution with calculating queries independently with dp[i] defined as "what result can we get for assigning everything with indices lower than i?". To calculate dp[i] we must know dp[i - 3], dp[i - 2] and dp[i - 1]. It wasn't intended solution because we can get better complexity.
We can create a segment tree and for intervals we should keep info "result we can get for this interval with 0/1/2 first and 0/1/2 last elements removed". For an interval we keep matrix 3x3 and actualizing forbidden edge for single i consists of: 1. calculating values of 3x3 matrix for a small interval with i 2. actualizing a tree with times multiplying matrices
Complexity is .
Div1E — Bear and Bowling
FIRST PART — greedy works
We will add (take) elements to a subsequence one by one. Adding number x, when we have k - 1 taken numbers on the left, increases result by k·x + suf where suf is sum of taken numbers on the right. Let's call this added value as the Quality of element x.
We will prove correctness of the following greedy algorithm. We take element with the biggest Quality till there are no elements left. For every size of a subsequence (number of taken elements) we will get optimal score.
(lemma) If ai > aj and i < j, we won't take aj first.
Proof. Let's consider a moment when we don't fulfill the lemma for the first time. If there are no taken numbers between ai and aj, we have Qi = k·ai + suf > k·aj + suf = Qj so ai is a better choice. For taken numbers between ai and aj — each number x changes Qi by x and Qj by aj. We'll see that x > aj so Qi will remain greater than Qj. If ai > x, the lemma (fulfilled till now) says that x wasn't taken before ai — it can't be true because x is taken and ai is not. So indeed x ≥ ai > aj.
Let's assume that our greedy strategy is not correct. Let's consider first moment when we take some element aj and for some s we can't get optimal subsequence with size s by taking more elements (using any strategy). Let A denote a set of elements taken before. So there is no way to add some more elements to set A + aj and achieve optimal score with size s. But it was possible just before taking aj so there is a subset of remaining elements B that |A + B| = s and set A + B is the best among sets with size s. Note that B can't be empty.
(case 1 — B contains at least one element on the left from aj) Let ai denote last element from B that i < j (here "last" means "with the biggest i"). Our strategy wanted aj before elements from B so we know from lemma that ai ≤ aj. It will turn out that replacing ai with aj (in set A + B) doesn't decrease the score so taking aj is acceptable. Note that replacing an element with another one doesn't change size of a set/subsequence.
In moment of choosing aj it had the biggest quality so then Qj ≥ Qi. Now in A + B there are new elements, those in B. Let's imagine adding them to A (without ai and aj). Each new element x on the right change both Qi and Qj by x. Elements on the left change Qi by ai and Qj by aj (note that ai ≤ aj). And there are no elements between ai and aj. Now, taking ai would give us set A + B but Qj remains not less than Qi so we can take aj instead.
(case 2 — B contains only elements on the right from aj) Similarly, we can replace ai with closest aj from set B. As before, elements on the right change Qi and Qj by the same value.
SECOND PART — how to implement it
First, let's understand solution. We divide a sequence into Parts. When choosing the best candidate in a Part, we want to forget about other Parts. It's enough to remember only x and suf — number of taken elements on the left (in previous Parts) and sum of elements on the right (in next Parts). x affects choosing the best element in a Part, suf doesn't (but we need this constant to add it to result for best candidate). For a Part we want to have hull with linear functions of form ai·x + b. With binary search we can find the best element in and then construct new hull for this Part in .
We can remove from complexity. First, binary search can be replaced with pointers — for each Part initially we set a pointer at the beginning of Part. To find best candidate in Part, we slowly move pointer to the right (by one). Complexity is amortized . And we can sort linear functions ai·x + b by angle only once because value ai doesn't change — then constructing a hull is only . Note that when rebuilding a hull, we must set pointer to the beginning of Part.
So we have . Code.
There are other two correct lemmas to speed your solution up. We can take all positive numbers first (it's not so easy to prove). And we can stop when taken number doesn't increase score — next taken numbers won't increase score neither.