codeforces-scrape

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

169.md (7966B)


      1 Source: https://codeforces.com/blog/entry/4187
      2 
      3 ** UPD: Formulas are already fixed. **
      4 
      5 **[163A - Substring and Subsequence](/contest/163/problem/A "VK Cup 2012 Round 2")**
      6 
      7 Solution summary: dynamic programming.
      8 
      9 Sample jury solution: [1415300](/contest/163/submission/1415300 "Submission 1415300 by Burunduk1") (author = [levlam](/profile/levlam "Master levlam"))
     10 
     11 The problem could be solved with the following dynamic programming. Let *f*[*i*, *j*] be the number of distinct pairs ("substring starting at position *i*" and "subsequence of the substring *t*[*j*... |*t*|]")
     12 
     13 Then:
     14 
     15 ```
     16 f[i, j] = f[i, j + 1];
     17 if (s[i] == t[j])
     18   add(f[i, j], f[i + 1, j + 1] + 1)
     19 ```
     20 
     21 Answer = ![](https://espresso.codeforces.com/782cb89fbe7443d4734af5f2bb9f8d15ac2ace56.png) f[i,0]
     22 
     23 **[163B - Lemmings](/contest/163/problem/B "VK Cup 2012 Round 2")**
     24 
     25 Solution summary: sorting + binary search.
     26 
     27 Sample jury solution: [1415306](/contest/163/submission/1415306 "Submission 1415306 by Burunduk1") (author: [Burunduk1](/profile/Burunduk1 "Grandmaster Burunduk1"))
     28 
     29 We need to find the minimal time *T*. Let us find it using binary search.
     30 
     31 Once the time is fixed, one can arrange lemmings using greedy approach starting either from the top or from the bottom. In this solution we consider the way to start from the bottom. Among all lemmings, that can get on the first ledge, let's choose the lemming with the minimal weight (and among all such lemmings the one with the minimal speed). Why is it correct? Assume that we used some heavier lemming, then we can't use any lighter lemming anywhere, so we could replace it. Among all lemmings with the minimal weight we choose the slowest, as the faster ones can climb higher.
     32 
     33 To arrange lemmings fast, we can sort them beforehand, comparing first the weight and then the speed. After if, we consider all the lemmings in that order and either choose the current one, if it can get in time, or leave it. It is useless to consider one lemming twice, as we won't be able to use it anyway.
     34 
     35 So, the solution consists of sorting and a binary search with a linear search inside. The time is ![](https://espresso.codeforces.com/3cb2cf5a5621bbe333948ffd524f6738de343b23.png).
     36 
     37 However, that was not enough. One also had to deal with precision problems. Let us evaluate the number of binary search iterations.
     38 
     39 0 ≤ *T* ≤ *H* * *K* (the maximal time does not exceed 109). We need to understand how the times can differ. In the case of "N = K = 105, H = 104, V about 109" the times needed for two lemmings to get on some ledges, can differ by 10- 18, as the times are fractions like ![](https://espresso.codeforces.com/66a57ac9d3721304b05b9a7d0a1a219d0ed5dedf.png), where *X* and *Y* are about 109.
     40 
     41 So we need to make *log*21027 = 90 iterations. In fact, jury solution made 75 and that was enough, however 70 was not. The idea above shows that 90 will be definitely enough.
     42 
     43 **[163C - Conveyor](/contest/163/problem/C "VK Cup 2012 Round 2")**
     44 
     45 Solution summary: events along the circle or binary search.
     46 
     47 Sample solution: [1415310](/contest/163/submission/1415310 "Submission 1415310 by Burunduk1") (author: [Burunduk1](/profile/Burunduk1 "Grandmaster Burunduk1"))
     48 
     49 Sample solution: [1415316](/contest/163/submission/1415316 "Submission 1415316 by Burunduk1") (author: [arseny30](/profile/arseny30 "Master arseny30"))
     50 
     51 Wherever Anton starts, he will run along the conveyor a segment of length ![](https://espresso.codeforces.com/2cde43f8df1e2f10ba44a26cd7968f9306fe2ff3.png). Consider one candy. To eat it, he needs to get on the conveyor in any moment of the segment [*a**i* - *D*..*a**i*]. Consider all points like *a**i* - *D* and *a**i* (add 2*l* if that is negative). Also add points 0 and 2*l*.
     52 
     53 Sort these points. Consider two neighboring points: x[i] и x[i+1]. If Anton starts at any moment between them, he will eat the same amount of candies.
     54 
     55 From now on, we can create one of the solving solutions:
     56 
     57 1. Start from every middle of the segment M = (x[i]+x[i+1]) / 2 and use binary search to find the number of candies on the segment [*M*..*M* + *D*].
     58 2. Consider events along a circle like (a[i] — D, +1) and (a[i], -1). One needs to move twice along the circle and use the second run to add the current length to the answer for the current number of candies.
     59 
     60 The both solutions require ![](https://espresso.codeforces.com/36f470bf769107e6d8d30da09625de1ca4144c7b.png) time.
     61 
     62 **[163D - Large Refrigerator](/contest/163/problem/D "VK Cup 2012 Round 2")**
     63 
     64 Solution summary: backtracking + boundaries evalutaion.
     65 
     66 Sample solution: [1415320](/contest/163/submission/1415320 "Submission 1415320 by Burunduk1") (author: [Burunduk1](/profile/Burunduk1 "Grandmaster Burunduk1"))
     67 
     68 The solution consists of three main ideas:
     69 
     70 1. *V* = *ABC*, *A* ≤ *B* ≤ *C* тогда *A* ≤ *N*1 / 3, *B* ≤ (*N* / *A*)1 / 2.
     71 2. *A* and *B* are divisors of *V*, as we are already given the factorization of *V*, we can run only through the divisors
     72 3. Given fixed *A*, the optimal real *B* and *C* are (*N* / *A*)1 / 2 (denote this values as *X*). I.e. the square will always be greater than  ≥ 2(2*AX* + *X*2). So we can use this value as a boundary for the answer.
     73 
     74 If that still was not enough, one could optimize using the following ideas:
     75 
     76 1. Border evaluation will be more useful while running through possible values of *A* in descending order
     77 2. *A* and *B* are 32-bit integers.
     78 3. Once we have calculated the answer for *V*, memoize it (this one makes possible maximal test a bit smaller).
     79 
     80 If anyone needs any theoretical base, here's some statistical information:
     81 
     82 1. The maximal number of divisors of numbers from 1 through 1018 is 103860 (the number 897612484786617600 = 2834527211 ...)
     83 2. Using only first two optimizations, the number of numbers *A*, found by our solution, is 10 471 (in the case of the number with maximal number of divisors)
     84 3. Using only first two optimizations, the number of pairs of *A* and *B*, found by our solution, is 128 264 (in the case of the number with maximal number of divisors)
     85 
     86 **[163E - e-Government](/contest/163/problem/E "VK Cup 2012 Round 2")**
     87 
     88 Solution summary: Aho-Corasick and finding the sum along a way in a tree of suffix links
     89 
     90 Sample solution: [1415345](/contest/163/submission/1415345 "Submission 1415345 by Burunduk1") (author: [arseny30](/profile/arseny30 "Master arseny30"))
     91 
     92 We assume that the reader is familiar with the Aho-Corasick algorithm ([http://en.wikipedia.org/wiki/Aho-Corasick](https://en.wikipedia.org/wiki/Aho-Corasick))
     93 
     94 Consider a trie of names and suffix links over it. For every vertex *v* one can calculate the number of names, ending in that vertex (*end*[*v*]).
     95 
     96 Then, the "add name *i*" operation is *end*[*v*[*i*]] += 1, where *v*[*i*] is ending vertex of *i*-th name.
     97 
     98 Similarly, "remove name *i*": *end*[*v*[*i*]] -= 1.
     99 
    100 To answer a request "calculate how politicized the text is", one needs to know, that the suffix links form a tree. Once we move though the text and simultaneously through the trie with suffix links, we add the sum of all *end*[*v*[*i*]] along the path to the root of the tree of suffix links the politicization of the text.
    101 
    102 Now, there's another problem: we need to calculate the sum of weights along a way to the root, the weights may change.
    103 
    104 One can do it in the following way:
    105 
    106 1. Move the weights from vertices to corresponding edges to vertices' parents
    107 2. Build the Eulerian traversal of the tree, where the down-move will store positive weight of the edge and up-move will store its negation.
    108 3. The sum along a path to the root if the sum on a segment of the Eulerian traversal (the endpoints are any entries of the vertices in the traversal).
    109 
    110 A fast and short way to calculate the sum on a segment is Fenwick's tree.
    111 
    112 Here's a solution running in O(|SumLen| * log) time and 26 * |SumLen| memory (the trie will not be compressed).