codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

573.md (14270B)


      1 Source: https://codeforces.com/blog/entry/20040
      2 
      3 [Div2B — Bear and Three Musketeers](//codeforces.com/contest/574/problem/B)
      4 
      5 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).
      6 
      7 Brute force is *O*(*n*3). 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.
      8 
      9 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*(*n*2 + *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.
     10 
     11 It's also possible to write it by adding "if" in right place in brute forces to get *O*(*n*2 + *nm*). Check it out in [code](//codeforces.com/contest/574/submission/12767226).
     12 
     13 [Div1A — Bear and Poker](//codeforces.com/contest/574/problem/C)
     14 
     15 Any positive integer number can be factorized and written as 2*a*·3*b*·5*c*·7*d*·....
     16 
     17 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](//codeforces.com/contest/574/submission/12767378)
     18 
     19 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](//codeforces.com/contest/574/submission/12767388)
     20 
     21 [Div1B — Bear and Blocks](//codeforces.com/contest/574/problem/D)
     22 
     23 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 *h**i* = *min*(*h**i* - 1, *h**i* - 1, *h**i* + 1) where *h*0 = *h**n* + 1 = 0. By using this formula two times we get height after two operations: *h**i* = *max*(0, *min*(*h**i* - 2, *h**i* - 1 - 1, *h**i* - 2, *h**i* + 1 - 1, *h**i* + 2)) and so on. From now I will omit *max*(0, ...) part to make it easier to read.
     24 
     25 After *k* operations we get *h**i* = *min*(*Left*, *Right*) where *Left* = *min*(*h**i* - *j* - (*k* - *j*)) = *min*(*h**i* - *j* + *j* - *k*) for ![](https://espresso.codeforces.com/c803343864c7aaa9119a50419eceaf4de5c3e104.png) and *Right* is defined similarly. *h**i* becomes zero when *Left* or *Right* becomes zero. And *Left* becomes zero when *k* = *min*(*h**i* - *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.
     26 
     27 For each *i* we are looking for *min*(*h**i* - *j* + *j*). We can iterate over *i* from left to right keeping some variable *best*:
     28 
     29 ```
     30 best = min(best, h[i]);
     31 best is answer for i;
     32 best++;
     33 ```
     34 
     35 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](//codeforces.com/contest/574/submission/12767308)
     36 
     37 [Div1C — Bear and Drawing](//codeforces.com/contest/574)
     38 
     39 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.
     40 
     41 ![ ](/predownloaded/82/6f/826fe1b8eeef9cf74c126dc2efde035a289f5c69.png)
     42 
     43 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:
     44 
     45 ![ ](/predownloaded/7f/62/7f62d19d4fc65a7556fa8a3b2fcb67ac7b6f4d07.png)
     46 
     47 Note that Y-letter can have long legs but its central part can have only one edge.
     48 
     49 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](//codeforces.com/contest/574/submission/12767236)
     50 
     51 [Div1D — Bear and Cavalry](//codeforces.com/contest/573/problem/D)
     52 
     53 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*.
     54 
     55 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.
     56 
     57 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):
     58 
     59 ![ ](/predownloaded/f3/df/f3dfa3aa136abc055d77562bd76f97f8598dfc0d.png)
     60 
     61 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:
     62 
     63 ![ ](/predownloaded/f3/29/f329a1266d6ddf509c5c7cdb1cf2a38f5c110af4.png)
     64 
     65 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.
     66 
     67 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.
     68 
     69 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.
     70 
     71 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 ![](https://espresso.codeforces.com/e534f2da678188382079d5eae762e91981566186.png) times multiplying matrices
     72 
     73 Complexity is ![](https://espresso.codeforces.com/315d8457a6aaa7ca93c12c3b17a9aef1a933544f.png).
     74 
     75 [Div1E — Bear and Bowling](//codeforces.com/contest/573/problem/E)
     76 
     77 **FIRST PART — greedy works**
     78 
     79 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*.
     80 
     81 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.
     82 
     83 **(lemma)** If *a**i* > *a**j* and *i* < *j*, we won't take *a**j* first.
     84 
     85 Proof. Let's consider a moment when we don't fulfill the lemma for the first time. If there are no taken numbers between *a**i* and *a**j*, we have *Q**i* = *k*·*a**i* + *suf* > *k*·*a**j* + *suf* = *Q**j* so *a**i* is a better choice. For taken numbers between *a**i* and *a**j* — each number *x* changes *Q**i* by *x* and *Q**j* by *a**j*. We'll see that *x* > *a**j* so *Q**i* will remain greater than *Q**j*. If *a**i* > *x*, the lemma (fulfilled till now) says that *x* wasn't taken before *a**i* — it can't be true because *x* is taken and *a**i* is not. So indeed *x* ≥ *a**i* > *a**j*.
     86 
     87 **Let's assume that our greedy strategy is not correct.** Let's consider first moment when we take some element *a**j* 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* + *a**j* and achieve optimal score with size *s*. But it was possible just before taking *a**j* 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.
     88 
     89 **(case 1 — *B* contains at least one element on the left from *a**j*)** Let *a**i* denote last element from *B* that *i* < *j* (here "last" means "with the biggest *i*"). Our strategy wanted *a**j* before elements from *B* so we know from lemma that *a**i* ≤ *a**j*. It will turn out that replacing *a**i* with *a**j* (in set *A* + *B*) doesn't decrease the score so taking *a**j* is acceptable. Note that replacing an element with another one doesn't change size of a set/subsequence.
     90 
     91 In moment of choosing *a**j* it had the biggest quality so then *Q**j* ≥ *Q**i*. Now in *A* + *B* there are new elements, those in *B*. Let's imagine adding them to *A* (without *a**i* and *a**j*). Each new element *x* on the right change both *Q**i* and *Q**j* by *x*. Elements on the left change *Q**i* by *a**i* and *Q**j* by *a**j* (note that *a**i* ≤ *a**j*). And there are no elements between *a**i* and *a**j*. Now, taking *a**i* would give us set *A* + *B* but *Q**j* remains not less than *Q**i* so we can take *a**j* instead.
     92 
     93 **(case 2 — *B* contains only elements on the right from *a**j*)** Similarly, we can replace *a**i* with closest *a**j* from set *B*. As before, elements on the right change *Q**i* and *Q**j* by the same value.
     94 
     95 **SECOND PART — how to implement it**
     96 
     97 First, let's understand ![](https://espresso.codeforces.com/4ad4f71250c8ed21eb27d44087319c0d74cfd450.png) solution. We divide a sequence into ![](https://espresso.codeforces.com/909ec83af66a546b3f5db58ea951d4a6289ac97d.png) 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 ![](https://espresso.codeforces.com/909ec83af66a546b3f5db58ea951d4a6289ac97d.png) linear functions of form *a**i*·*x* + *b*. With binary search we can find the best element in ![](https://espresso.codeforces.com/068f8d741ecfcc36056356e886f009263674cd5b.png) and then construct new hull for this Part in ![](https://espresso.codeforces.com/068f8d741ecfcc36056356e886f009263674cd5b.png).
     98 
     99 We can remove ![](https://espresso.codeforces.com/451185951e528f7848bcd6d81f0288763caf3998.png) 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 ![](https://espresso.codeforces.com/9ca62661ea21b1ce54195f1d67b5981f402316e3.png). And we can sort linear functions *a**i*·*x* + *b* by angle only once because value *a**i* doesn't change — then constructing a hull is only ![](https://espresso.codeforces.com/4e74f6500d421e32d4a682202d52c0430daf5340.png). Note that when rebuilding a hull, we must set pointer to the beginning of Part.
    100 
    101 So we have ![](https://espresso.codeforces.com/c120044181b4566c32bcd52ecbca96ca298efcef.png). [Code](//codeforces.com/contest/573/submission/12767462).
    102 
    103 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.