codeforces-scrape

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

406.md (11427B)


      1 Source: https://codeforces.com/blog/entry/11186
      2 
      3 #### [405A - Gravity Flip](/contest/405/problem/A "Codeforces Round 238 (Div. 2)")
      4 
      5 Observe that in the final configuration the heights of the columns are in non-decreasing order. Also, the number of columns of each height remains the same. This means that the answer to the problem is the sorted sequence of the given column heights.
      6 
      7 Solution complexity: *O*(*n*), since we can sort by counting.
      8 
      9 #### [405B - Domino Effect](/contest/405/problem/B "Codeforces Round 238 (Div. 2)")
     10 
     11 If the first pushed domino from the left was pushed to the left at position *l*, all dominoes at prefix [1;*l*] fall down, otherwise let *l* be 0. Similarly, if the first pushed domino from the right was pushed to the right at position *r*, all dominoes at suffix [*r*;*n*] also fall down, otherwise let *r* be *n* + 1. Now, in the segment (*l*;*r*) there will remain vertical dominoes and blocks of dominoes supported by the equal forces from both sides.
     12 
     13 When does a domino at position *p* in segment (*l*, *r*) remains standing vertically? One way is that it is not pushed by any other domino. This could be easily checked by looking at the pushed dominoes closest to *p* (from both sides). It is pushed by dominoes, only if the closest from the left was pushed to the right, and the closest from the right was pushed to the left. Suppose these dominoes are at positions *x* and *y*, *x* < *p* < *y*. Then, the only way that the domino is still standing is if it is positioned at the center of the block [*x*;*y*], which could be checked by ![](https://espresso.codeforces.com/a251f72eccac3fbfd7804fb35a9fb3cca19549d2.png).
     14 
     15 Solution complexity: *O*(*n*) / *O*(*n*2), depends on implementation.
     16 
     17 #### [406A - Unusual Product](/contest/406/problem/A "Codeforces Round 238 (Div. 1)")
     18 
     19 Written as a formula, the problem asks to find the value of
     20 
     21 ![](https://espresso.codeforces.com/2addb1b89b672471f0c178ffe6d0f57ce9932b5f.png)
     22 
     23 Suppose that *i* ≠ *j*. Then the sum contains summands *A**ij**A**ji* and *A**ji**A**ij*. Since the sum is taken modulo 2, these summands together give 0 to the sum. It follows that the expression is always equal to the sum of the diagonal bits:
     24 
     25 ![](https://espresso.codeforces.com/ac441729f785f7fc55aa974b1e6c4de1f683a62e.png)
     26 
     27 Now, each query of type 1 and 2 flips the value of exactly one bit on the diagonal. Thus we can calculate the unusual product of the original matrix, and flip its value after each query of type 1 and 2.
     28 
     29 Solution complexity: *O*(*n* + *q*), if we don't take the reading of the input into account... :)
     30 
     31 #### [406B - Toy Sum](/contest/406/problem/B "Codeforces Round 238 (Div. 1)")
     32 
     33 Let's define the symmetric number of *k* to be *s* + 1 - *k*. Since in this case *s* is an even number, *k* ≠ *s* - *k*.
     34 
     35 Note that (*k* - 1) + (*s* + 1 - *k*) = *s*, i.e., the sum of a number and its symmetric is always *s*. Let's process the given members *x* of *X*. There can be two cases:
     36 
     37 1. If the symmetric of *x* does not belong to *X*, we add it to *Y*. Both give equal values to the respective sums: *x* - 1 = *s* - (*s* + 1 - *x*).
     38 2. The symmetric of *x* belongs to *X*. Then we pick any *y* that neither *y* and symmetric of *y* belong to *X*, and add them to *Y*. Both pairs give equal values to the respective sums, namely *s*.
     39 
     40 How to prove that in the second step we can always find such *y*? Let the number of symmetric pairs that were processed in the step 1 be *a*, then there remain ![](https://espresso.codeforces.com/303e07f3f5cf874f06407060b757ca3420ef35c7.png) other pairs. Among them, for ![](https://espresso.codeforces.com/fea1f6464e8108fab48dc2b0e7206a715125c5e4.png) pairs both members belong to *X*, and for other ![](https://espresso.codeforces.com/2b13584fa2edcb582d323f3609ff89e5da16ccda.png) pairs none of the members belong to *X*. To be able to pick the same number of pairs for *Y*, as there are in *X*, we should have
     41 
     42 ![](https://espresso.codeforces.com/31c7717c79291e69b647eb96e2fbd05fdc3f2285.png)
     43 
     44 which is equivalent to ![](https://espresso.codeforces.com/61329b112c3af9315885cd0e936dd963955d45eb.png), as given in the statement.
     45 
     46 Solution complexity: *O*(*s*) / *O*(*n*).
     47 
     48 #### [406C - Graph Cutting](/contest/406/problem/C "Codeforces Round 238 (Div. 1)")
     49 
     50 It can be proved that only graphs with an odd number of edges cannot be partitioned into path of length 2. We will construct a recursive function that solves the problem and also serves as a proof for this statement.
     51 
     52 The function `partition(v)` will operate on non-blocked edges. It will partition the component of vertex *v* connected by the non-blocked edges into paths of length 2. If this component has an odd number of edges, the function will partition all the edges of the component, except one edge (*u*, *v*); the function then will return vertex *u*, expecting that the parent function call will assign it to some path.
     53 
     54 The function works as follows: find all vertices that are adjacent to *v* by the non-blocked edges, call this set `adjacent`. Then block all the edges from this set vertices to *v*. For each *u* in `adjacent`, call `partition(u)`. Suppose `partition(u)` returned a vertex *w*. That means we can pair it into the path (*v*, *u*, *w*). Otherwise, if `partition(u)` does not return anything, we add *u* to `unpaired`, since the edge (*v*, *u*) is not yet in any path. We can pair any two vertices of this set *u*, *w* into a single path (*u*, *v*, *w*). We pair as much of them as possible in any order. If from this set a single vertex, *u*, is left unpaired, the function will return *u*. Otherwise the function will not return anything.
     55 
     56 The function could be implemented as a single DFS:
     57 
     58 ```
     59 partition(v) :
     60     adjacent = { u | not blocked[(u,v)] }
     61     for(u : adjacent)
     62         blocked[(u,v)] = true
     63 
     64     unpaired = {}
     65     for(u : adjacent)
     66         int w = partition(u)
     67         if(w = 0)
     68             add(unpaired, u)
     69         else
     70             print(v,u,w)
     71 
     72     while(size(unpaired) >= 2)
     73         int u = pop(unpaired)
     74         int w = pop(unpaired)
     75         print(u,v,w)
     76 
     77     if(not empty(unpaired))
     78         return pop(unpaired)
     79     else
     80         return 0
     81 ```
     82 
     83 Solution complexity: *O*(*n* + *m*).
     84 
     85 #### [406D - Hill Climbing](/contest/406/problem/D "Codeforces Round 238 (Div. 1)")
     86 
     87 Note that the path of each hill climber is strictly convex in any case. Let's draw the paths from all hills to the rightmost hill. Then these paths form a tree with the "root" at the top of the rightmost hill. We can apply the Graham scan from the right to the left to find the edges of this tree. Each pop and insert in the stack corresponds to a single edge in the tree.
     88 
     89 ![ ](/predownloaded/6a/de/6ade35e1dd914a785e5b430023b6a4cb0c103727.jpg)
     90 
     91 Now it is easy to see that for each team of climbers, we should calculate the number of the lowest common ancestor for the corresponding two vertices in the tree. The size if the tree is *n*, so each query works in ![](https://espresso.codeforces.com/9040a33098f83986b0de64475c66584fbfdf0e22.png).
     92 
     93 Solution complexity: ![](https://espresso.codeforces.com/06b2dfff448a3a9e0e9b5c879f5cda0ce1cecba5.png).
     94 
     95 #### [406E - Hamming Triples](/contest/406/problem/E "Codeforces Round 238 (Div. 1)")
     96 
     97 Let's look at the Hamming graph of all possible distinct 2*n* strings, where each two strings are connected by an edge with length equal to the Hamming distance between these strings. We can observe that this graph has a nice property: if we arrange the vertices cyclically as a regular 2*n*-gon with a side length of 1, then the Hamming distance between two strings is the length of the shortest route between these vertices on the perimeter of the polygon.
     98 
     99 For example, the figure shows the graph for *n* = 3. The gray edges have length 1, the orange edges have length 2 and the blue edges have length 3. That is the corresponding Hamming distance.
    100 
    101 ![ ](/predownloaded/58/b9/58b93f14889c0658ce54109772d5e2d72df8ad8a.jpg)
    102 
    103 Now, we can convert each string coded by a pair (*s*, *f*) to an integer (*f* + 1)·*n* - *s*. The new numbers will be 0, 1, ..., 2*n* - 1 and correspond to the same cyclical order on the perimeter of the polygon. The given strings are mapped to some subset of the vertices. Now we have to find the number of triangles (possibly degenerate) with maximal perimeter in this subgraph. It will be useful to keep the new converted numbers sorted.
    104 
    105 First, we can figure out what this perimeter could be. If there exists a diameter in the full graph, so that all of the points are on one side of the diameter, the perimeter is 2*d*, where *d* is the length of the longest edge:
    106 
    107 ![ ](/predownloaded/33/86/33860ab2026273377797841e9033b28457e4a0fb.jpg)
    108 
    109 Then any triangle with two vertices at the longest edge points and the third one being any point has the maximal perimeter. Since the numbers are sorted, the longest edge in this case will be produced by two cyclically adjacent elements, which is not hard to find.
    110 
    111 If for any diameter this does not hold, then the maximal perimeter is 2*n*. This can be proved by taking two different points *a*, *b* and drawing two diameters with them as endpoints; since it is not the previous case, there shoud be a third point *c* in area where the perimeter of triangle *a*, *b*, *c* is 2*n*.
    112 
    113 The tricky part is to count the triples in this case. We do this by working with the diameter (0, *n*). There can be several cases:
    114 
    115 1. A maximum triangle has vertices 0 and *n*. This a simple case: with any other vertex as the third the triangle has perimeter 2*n*.
    116 2. A maximum triangle has vertex 0, but not *n*. Then the second vertex should be in interval [0, *n*), and the third in interval (*n* + 1, 2*n* - 1], and the clockwise distance between the second and the third should not exceed *n* (since then the perimeter of the triangle would be less than 2*n*). We count the number of such triples iterating two pointers (one in each of these intervals). For each pointer in the first interval, all points from *n* + 1 till the second pointer will make a maximal perimeter triangle. We similarly solve the case where the maximal triangle has vertex *n*, but not 0.
    117 3. The maximal triangle does not have 0 or *n* as its vertices. Then one vertex of the triangle should be on one side of diameter (0, *n*), and two should be on the opposite side. To count them, we iterate a vertex pointer on the first side, say, (0, *n*); let the diametrally opposite vertex on the opposite side be *x*. Then the second vertex can be any in [*n* + 1, *s*], and the third can be any of the [*s*, 2*n* - 1]. It is easy to calculate these numbers using partial sums on the circle. Note that *s* can be both the second and the third vertex (since strings can repeat). So we iterate this pointer over all one side vertices and update the answer. Similarly we solve the case where a single vertex is on the other side, and two on this side.
    118 
    119 One only needs to be careful with the formulas in each case.
    120 
    121 Solution complexity: ![](https://espresso.codeforces.com/c534bf46b6ba904301185a92049570781d3b6d85.png), because of the sorting.
    122 
    123 #### Post Scriptum
    124 
    125 What were your solutions? Feel free to share any solutions or thoughts! For example, was there a solution to DivI E simpler than in this tutorial?