codeforces-scrape

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

232.md (13208B)


      1 Source: https://codeforces.com/blog/entry/5514
      2 
      3 It will be finised in few hours. If you don't understand something, ask your questions, please.
      4 
      5 [233A - Perfect Permutation](/contest/233/problem/A "Codeforces Round 144 (Div. 2)")
      6 
      7 Idea: [Gerald](/profile/Gerald "Master Gerald") Implementation: [tunyash](/profile/tunyash "Candidate Master tunyash") Editorial: [fdoer](/profile/fdoer "Expert fdoer")
      8 
      9 Consider permutation *p* such that *p**i* = *i*. Actually *p* is a sequence of numbers from 1 to *n*. Obviously *p**p**i* = *i*. Now the only trick is to change the permutation to satisfy the second equation: *p**i* ≠ *i*. Let's swap every two consequtive elements. More formally, for each *k*: 2*k* ≤ *n* let's swap *p*2*k* - 1 and *p*2*k*. It's easy to see that the obtained permutation satisfies both equations for every *n* with the only exception: when *n* is odd, there is no answer and we should print  - 1.
     10 
     11 [233B - Non-square Equation](/contest/233/problem/B "Codeforces Round 144 (Div. 2)")
     12 
     13 Idea: [tunyash](/profile/tunyash "Candidate Master tunyash") Implementation: [tunyash](/profile/tunyash "Candidate Master tunyash"), [Gerald](/profile/Gerald "Master Gerald") Editorial: [fdoer](/profile/fdoer "Expert fdoer")
     14 
     15 Firstly let's find the interval of possible values of *s*(*x*). Hence *x*2 ≤ *n* and *n* ≤ 1018, *x* ≤ 109. In other words, for every considerable solution *x* the decimal length of *x* does not extend 10 digits. So *s**max* ≤ *s*(9999999999) = 10·9 = 90.
     16 
     17 Let's bruteforce the value of *s*(*x*) (0 ≤ *s*(*x*) ≤ 90). Now we have an ordinary square equation. The deal is to solve it and to check that the current bruteforced value of *s*(*x*) is equal to sum of digits of the solution. If the solution exists and the equality holds, we should relax the answer.
     18 
     19 It seems that the most error-generating part of this problem is solving the equation.
     20 
     21 Knowing arrays is not neccessary to solve these two problems.
     22 
     23 [232A - Cycles](/contest/232/problem/A "Codeforces Round 144 (Div. 1)")
     24 
     25 Idea: [tunyash](/profile/tunyash "Candidate Master tunyash"), [fdoer](/profile/fdoer "Expert fdoer") Implementation: [tunyash](/profile/tunyash "Candidate Master tunyash") Editorial: [tunyash](/profile/tunyash "Candidate Master tunyash")
     26 
     27 Let's add edge in order of increasing *a* and for equal *b* in order of increasing *b* (here *a* and *b* — the least and the greatest vertices of the edge). If the new edge adds too much 3-cycles, we won't add it. We can count the number of new 3-cycles in *O*(*n*) complexity (they all contain the new edge, so it's enough to check all variants of the third vertex). Obviously we will obtain some proper graph, because we can always add a vertex and two edges to make a new triangle. So, there is always an answer. The complexity of this solution is *O*(*n*3).
     28 
     29 Let's proof that 100 vertices are always enough for the given restrictions on *n*.
     30 
     31 * For some *p* after first *p* iterations we will have a complete graph of *p* vertices.
     32 * Now we have exactly *C*(*p*, 3) triangles. Consider *p* such that *C*(*p*, 3) ≤ *k* and *C*(*p*, 3) is maximal.
     33 * For the given restrictions *p* ≤ 85.
     34 * From this moment, if we add *u* from some vertex, we increase the total number of 3-cycles on *C*(*u*, 2).
     35 * So we have to present a small number that is less than *C*(85, 3) as sum of *C*(*i*, 2).
     36 * The first number we subtruct will differ *C*(85, 1) on some value not greater than *C*(85, 1) = 85, because *C*(*n*, *k*) - *C*(*n* - 1, *k*) = *C*(*n* - 1, *k* - 1).
     37 * The second number we subtruct will differ the number we have on some value not greater than *C*(14, 1) = 14.
     38 * and so on.
     39 * For every *k* it's enough to use not more that 90 vertices.
     40 
     41 [232B - Table](/contest/232/problem/B "Codeforces Round 144 (Div. 1)")
     42 
     43 Idea: [tunyash](/profile/tunyash "Candidate Master tunyash"), [Skird](/profile/Skird "Expert Skird") Implementation: [tunyash](/profile/tunyash "Candidate Master tunyash") Editorial: [tunyash](/profile/tunyash "Candidate Master tunyash")
     44 
     45 * Let *s**i* number of points in the column *i*.
     46 
     47 ![ ](/predownloaded/49/13/491389abfb8310e879d9d35f22f5a596c857ea0c)
     48 
     49 * Two neighboring squares are drawn at this picture, *A* is the number of point it the left area (it is one column), *B* is the number of points in the middle area and *C* is the number of points in the right area (it is one column too). That's why by definition we have:
     50 
     51 ![](https://espresso.codeforces.com/b0321b85475278e5d01d9842d4b4ccaf93f57b62.png)
     52 
     53 * Therefore *A* = *C*.
     54 * That's why ![](https://espresso.codeforces.com/40f3ad76407858803063e08e57341084c89718a9.png)
     55 * Divide all columns by equivalence classes on the basis of ![](https://espresso.codeforces.com/d311f94c8a7f00a8291ca41115329f7534281187.png). For all *a* and *b* from one class *s**a* = *s**b*.
     56 * *cnt**a* is number of columns in class with ![](https://espresso.codeforces.com/1c90badf244fce4850e3f4cb668690a0c2bf0836.png).
     57 * There are (*C**n**k*)*cnt**a* ways to draw *k* points in the each of columns in the class *a* independendently of the other classes.
     58 * *dp*[*i*][*j*] is number of ways to fill all columns in classes 1, ... *i* in such way that ![](https://espresso.codeforces.com/80779f5ff84eb1e37a11192bc0695fe1dd2fdaf4.png). ![](https://espresso.codeforces.com/eecfc60f69501aebc2f3edb9fff08520f964c17d.png)
     59 * *cnt**i* take only two values ![](https://espresso.codeforces.com/26e04dcbfa0f72d60706ede50f38de5900f959b8.png) and ![](https://espresso.codeforces.com/920eb9fe66eae0f5b85efd32d9207767a1009ea6.png). Let's calc (*C**n**a*)*cnt**i* for all *a* and *cnt**i* and use it to calc our dp. We have *O*(*n*2·*k*) complexity.
     60 
     61 [232C - Doe Graphs](/contest/232/problem/C "Codeforces Round 144 (Div. 1)")
     62 
     63 Idea: [Gerald](/profile/Gerald "Master Gerald"),[tunyash](/profile/tunyash "Candidate Master tunyash") Implementation: [tunyash](/profile/tunyash "Candidate Master tunyash"), [Gerald](/profile/Gerald "Master Gerald") Editorial: [tunyash](/profile/tunyash "Candidate Master tunyash")
     64 
     65 Let's reduce the problem to the same problem for graphs with less orders. Vertex |*D*(*n* - 1)| + 1 is cutpoint (except cases *n* ≤ 2 but equations below is true for these cases).
     66 
     67 Without loss of generality *a* < *b*.
     68 
     69 Let *dist*(*a*, *b*, *n*) — length of the shortest path in graph of order *n*.
     70 
     71 The first case is *a* ≤ |*D*(*n* - 1)| and |*D*(*n* - 1)| + 1 ≤ *b*
     72 
     73 *dist*(*a*, *b*, *n*) = *min*(*dist*(*a*, |*D*(*n* - 1)|, *n* - 1), *dist*(*a*, 1, *n* - 1)) + *dist*(*b* - |*D*(*n* - 1)|, 1, *n* - 2) + 1
     74 
     75 ![ ](/predownloaded/ef/19/ef19ccad9305cc37d2947d197ea71e179711c355.jpg)
     76 
     77 Edges is marked in red, paths is marked in blue. This formula means that we can go from the vertex *a* by the path 1 to the vertex 1. Then we can go to the |*D*(*n* - 1)| + 1 by the edge and go to the vertex *b* by the path 3. Or we can go to the vertex |*D*(*n* - 1)| by the path 2 and then go to the vertex |*D*(*n* - 1)| + 1 by the path 2 and then go to the vertex *b* by the path 3.
     78 
     79 The second case is |*D*(*n* - 1)| + 1 ≤ *a*, *b*.
     80 
     81 *dist*(*a*, *b*, *n*) = *dist*(*a* - |*D*(*n* - 1)|, *b* - |*D*(*n* - 1)|, *n* - 2)
     82 
     83 That's easy case.
     84 
     85 The third case is *a*, *b* ≤ |*D*(*n* - 1)|
     86 
     87 *dist*(*a*, *b*, *n*) = *min*(*dist*(*a*, *b*, *n* - 1), *min*(*dist*(1, *a*, *n* - 1), *dist*(|*D*(*n* - 1)|, *a*, *n* - 1)) + *min*(*dist*(1, *b*, *n* - 1), *dist*(|*D*(*n* - 1)|, *b*, *n* - 1) + 2)
     88 
     89 ![ ](/predownloaded/f3/12/f3125845b66fdeff7573d4f757a6147f84925806.jpg)
     90 
     91 If shortest path contains cutpoint (|*D*(*n* - 1)| + 1) we can go to the vertex 1 or |*D*(*n* - 1)+1$ form the both of *a* and *b*. After that we can go to the cutpoint. Else we should consider path from *a* to *b* in *D*(*n* - 1).
     92 
     93 Let's notice that for all of *n* will be no more than 4 distinct runnings of *dist*(*i*, *j*, *n*).
     94 
     95 It can be prooved by the considering many cases of our actions.
     96 
     97 In authors colution we cashed all *dist*(1, *i*, *n*) and *dist*(*i*, |*D*(*n*)|, *n*) for all achieveable *i* and *n*.
     98 
     99 We have complexity ![](https://espresso.codeforces.com/6498004f69c3e1effecb9f918482548d804f54fa.png) for one query. (it's log because |*D*(*n*)| grows like φ*n*).
    100 
    101 [232D - Fence](/contest/232/problem/D "Codeforces Round 144 (Div. 1)")
    102 
    103 Idea: [Gerald](/profile/Gerald "Master Gerald"), [tunyash](/profile/tunyash "Candidate Master tunyash") Implementation: [fdoer](/profile/fdoer "Expert fdoer") Editorial: [fdoer](/profile/fdoer "Expert fdoer")
    104 
    105 Let *d* and *d*' be arrays such that *d**i* = *h**i* - *h**i* + 1, *d*'*i* =  - *d**i* for every 1 ≤ *i* ≤ (*n* - 1). With that notation the conditions of matching look somehow like these:
    106 
    107 * the pieces do not intersect, that is, there isn't a single plank, such that it occurs in both pieces of the fence;
    108 * the pieces are of the same width;
    109 * for all i *i* (0 ≤ *i* ≤ *r*1 - *l*1 - 1) the following condition holds: *d**l*1 + *i* = *d*'*l*2 + *i* (that is true in case when *l* = *r*).
    110 
    111 The main idea of our solution is stated in the next sentence. For each query *l*...*r* the answer is number of pairs (*a*, *b*) such that (*a* > *r* or *b* < *l*), 1 ≤ *a* ≤ *b* ≤ *n* - 1, *b* - *a* = *r* - *l* and *d**l*...*r* - 1 exactly matches *d*'*a*...*b* - 1. Let's build a suffix array *sa* from the concatenation of arrays *d* and *d*' with a fictive number between them for separation. Let position of suffix *i* in *sa* be *pos**i*. For each query all pieces of the fence that satisfy both second and third conditions of matching will be placed in *sa* on some segment *bound**left*...*bound**right* such that *bound**left* ≤ *pos**l* ≤ *bound**right* and *lcp*(*bound**left*...*bound**right*) ≥ (*r* - *l*). So, it's possible to use binary search to find *bound*'s. Depending on complexity of *lcp* finding algorithm, we could get them in *O*(*logn*) or *O*(*log*2*n*) complexity.
    112 
    113 But there is still a problem to count the number of suffixes from *sa**bound**left*...*bound**right* that satisfy the first condition too. Actually it is equal to count the number of *i* (*bound**left* ≤ *i* ≤ *bound**right*) such that (*n* + 1 ≤ *sa**i* ≤ *n* + *l* - (*r* - *l*) - 1 or *sa**i* ≥ *n* + *r*) (in the concatenation *d*' starts from *n* + 1). It is a classic problem to count numbers from the given interval in the given subarray. For each query it could be solved in *O*(*logn*) complexity.
    114 
    115 For instance, we could solve it offline using sweep line method and any data structure that support queries of sum on an interval and increment of an element. Or we could use some 2D/persistent structure.
    116 
    117 So, the summary of the algorithm looks like this:
    118 
    119 * build *d* and *d*'. Build a suffix array on their concatenation.
    120 
    121 For each query:
    122 
    123 * find the interval (*bound**left*...*bound**right*) with two consecutive binary searches using lcp function.
    124 * query the count of suffixes from that interval that do not intersect with the given piece of the fence.
    125 
    126 The best author's solution complexity is *O*(*nlogn* + *qlogn*), but careful written solutions in *O*(*nlog*2*n*) comply with the lime limit too.
    127 
    128 [232E - Quick Tortoise](/contest/232/problem/E "Codeforces Round 144 (Div. 1)")
    129 
    130 Idea: [tunyash](/profile/tunyash "Candidate Master tunyash") Implementation: [tunyash](/profile/tunyash "Candidate Master tunyash"), [KAN](/profile/KAN "Candidate Master KAN") Editorial: [tunyash](/profile/tunyash "Candidate Master tunyash")
    131 
    132 Let's choose central column of the area and for all cells to the left from column calc masks of achieveable cells in the central column and for all cells to the right from column calc masks of cells of which this is achievable. It's easy dp with bitsets. ![](https://espresso.codeforces.com/5d858dbb732809a6013ca8ce6a360e52254af517.png) for the right part of board. ![](https://espresso.codeforces.com/08b44f1d960a1698a148ab80ecc3731171f6006a.png) (![](https://espresso.codeforces.com/b31aaa1e8148d0354d5ce22960459dfdb6039f49.png) — logical or, here it's bitwise or for masks) for the left part. dp calcs mask of achieveable points in the central column.
    133 
    134 ![ ](/predownloaded/92/95/929568e55fe72b22fbc89b77b06ec2462b1aa86a.jpg)
    135 
    136 For query *x*1, *y*1, *x*2, *y*2 (if *y*1 ≤ *mid* ≤ *y*2, where *mid* is chosen central column) answer is yes if ![](https://espresso.codeforces.com/e1ee58f17a55401a863bd273b8c85e798944d106.png) (![](https://espresso.codeforces.com/160ebdcb5e0c9bad1d16d2cca9574c16155a30ea.png) is bitwise and) is not empty.
    137 
    138 Run this algo for left and right part of board we will get answers for all queries. Complexity is ![](https://espresso.codeforces.com/76af1aaa044c42643d467ec157fa49fbe0fe8857.png).