codeforces-scrape

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

509.md (9584B)


      1 Source: https://codeforces.com/blog/entry/16119
      2 
      3 [509A - Maximum in Table](/contest/509/problem/A "Codeforces Round 289 (Div. 2, ACM ICPC Rules)")
      4 
      5 In this problem one needed to implement what was written in the statement: create matrix (two-dimensional array) using given rules and find maximal value in the table.
      6 
      7 It is also possible to see that maximal element is always in bottom-right corner.
      8 
      9 Easier solution with recursion also was enough to get AC:
     10 
     11 ```
     12 def elem(row, col):
     13     if row == 1 or col == 1:
     14         return 1
     15     return elem(row - 1, col) + elem(row, col - 1)
     16 ```
     17 
     18 One may see the [Pascal's triangle](https://en.wikipedia.org/wiki/Pascal%27s_triangle) in the given matrix and understand that answer is equal to ![](https://espresso.codeforces.com/3f254186c638d7ed77ade17c7438f3247db6e73f.png)
     19 
     20 Prepared by: [riadwaw](/profile/riadwaw "Master riadwaw")  
     21 Author of editorial: [riadwaw](/profile/riadwaw "Master riadwaw")
     22 
     23 [509B - Painting Pebbles](/contest/509/problem/B "Codeforces Round 289 (Div. 2, ACM ICPC Rules)")
     24 
     25 Suppose there are two piles with number of pebbles differed by more than *k*, then there is no solution:
     26 
     27 ![](https://espresso.codeforces.com/8e65e8b580fdefc24d644e64615dbaf0140af2ed.png)
     28 
     29 Now let *M* = *max* *a**i* ≤ *min* *a**i* + *k* = *m* + *k*.  
     30 There's a way to construct correct coloring:
     31 
     32 * Chose *m* peebles from each pile and assign first color to them.
     33 * In each pile assign different colors to all other pebbles (you may use first color once more) (It's possible bacause there are no more than *k* uncolored pebbles.
     34 
     35 Now there are *m* or *m* + 1 pebbles of first color and 0 or 1 pebbles of any other color in each pile.
     36 
     37 Prepared by: [Kostroma](/profile/Kostroma "Grandmaster Kostroma")  
     38 Author of editorial: [riadwaw](/profile/riadwaw "Master riadwaw")
     39 
     40 [509C - Sums of Digits](/contest/509/problem/C "Codeforces Round 289 (Div. 2, ACM ICPC Rules)")
     41 
     42 The algorithm is greedy: first, take the minimal number with sum of digits *a*1 — call it *b*1. Then, on the *i*-th step take *b**i* as the minimal number with sum of digits *a**i*, which is more than *b**i* - 1.
     43 
     44 It can be easily proven that this algorithm gives an optimal answer. But how to solve the subproblem: given *x* and *y*, find the minimal number with sum of digits *x*, which is more than *y*?
     45 
     46 We use a standard approach: iterate through the digits of *y* from right to left, trying to increase the current digit and somehow change the digits to the right in order to reach the sum of digits equal to *x*. Note that if we are considering the (*k* + 1)-th digit from the right and increase it, we can make the sum of *k* least significant digits to be any number between 0 and 9*k*. When we find such position, that increasing a digit in it and changing the least significant digits gives us a number with sum of digits *x*, we stop the process and obtain the answer. Note that if *k* least significant digits should have sum *m* (where 0 ≤ *m* ≤ 9*k*), we should obtain the answer greedily, going from the right to the left and putting to the position the largest digit we can.
     47 
     48 Let us bound the maximal length of the answer, i.e. of *b**n*. If some *b**i* has at least 40 digits, than we take the minimal *k* such that 10*k* ≥ *b**i*. Than between 10*k* and 10*k* + 1 there exist numbers with any sum of digits between 1 and 9*k*. If *k* ≥ 40, than 9*k* ≥ 300, which is the upper bound of all *b**i*. So, in the constraints of the problem, *b**i* + 1 will be less than 10*k* + 1. Than, similarly, *b**i* + 2 < 10*k* + 2 and so on. So, the length of the answer increases by no more than one after reaching the length of 40. Consequently, the maximal length of the answer can't be more than 340.
     49 
     50 The complexity of solution is *O*(*n*·*maxLen*). Since *n* ≤ 300, *maxLen* ≤ 340, the solution runs much faster the time limit.
     51 
     52 Prepared by: [Endagorion](/profile/Endagorion "Grandmaster Endagorion")  
     53 Author of editorial: [Kostroma](/profile/Kostroma "Grandmaster Kostroma")
     54 
     55 [509D - Restoring Numbers](/contest/509/problem/D "Codeforces Round 289 (Div. 2, ACM ICPC Rules)")
     56 
     57 First we note that if the sequences *a**i* and *b**i* are a valid solution, then so are the sequences *a**i* - *P* and *b**i* + *P* for any integer *P*. This means that we can consider *a*1 to be equal to 0 which allows us to recover the sequence *b**i* by simply taking the first row of the matrix. Knowing *b**i* we can also recover *a**i* (for example by subtracting *b*1 from the first column of the matrix) At this stage we allow *a**i* and *b**i* to contain negative numbers, which can be later fixed by adding *K* a sufficient amount of times. Now we consider the “error” matrix *e*: ![](https://espresso.codeforces.com/83efc57d355358ab75c12c810796509abdf6b06e.png).
     58 
     59 If *e* consists entirely of 0s, then we’ve found our solution by taking a sufficiently large *K*. That is: *K* > *max**i*, *j*(*w**i*, *j*).
     60 
     61 Otherwise, we note that *e**i*, *j* = 0(*modK*) which implies that *K* is a divisor of *g* = *gcd**i*, *j*(*e**i*, *j*). The greatest such number is *g* itself, so all that remains is to check if *g* is strictly greater than all the elements of the matrix *w*. If that is the case, then we’ve found our solution by setting *K* = *g*. Otherwise, there’s no solution.
     62 
     63 Prepared by: [Kostroma](/profile/Kostroma "Grandmaster Kostroma"), [riadwaw](/profile/riadwaw "Master riadwaw")  
     64 Author of editorial: [riadwaw](/profile/riadwaw "Master riadwaw")
     65 
     66 [509E - Pretty Song](/contest/509/problem/E "Codeforces Round 289 (Div. 2, ACM ICPC Rules)")
     67 
     68 We first calculate the prefix sums of *vowel*(*s**i*) which allows to calculate the sum of *vowel*(*s**i*) on any substring in *O*(1) time.
     69 
     70 For all *m* from 1 to ![](https://espresso.codeforces.com/346c6f6cf09da21493e2842022d2c3699bf852d8.png), we will calculate the sum of simple pretinesses of all substrings of that length, let’s call it *SP**m*. For that purpose, let’s calculate the number of times the *i*-th character of the string *s* is included in this sum.
     71 
     72 For *m* = 1 and *m* = |*s*|, every character is included exactly 1 time. For *m* = 2 and *m* = |*s*| - 1, the first and the last character are included 1 time and all other characters are included 2 times. For *m* = 3 and *m* = |*s*| - 2 the first and the last character are included 1 time, the second and the pre-last character are included 2 times and all others are included 3 times, and so on.
     73 
     74 In general, the *i*-th character is included *min*(*m*, |*s*| - *m* + 1, *i*, |*s*| — *i* + 1) times. Note that when moving from substrings of length *m* to substrings of length *m* + 1, there are 2 ways in which the sum *SP* can change:
     75 
     76 1. If *m* > |*s*| - *m* + 1, then *SP* is decreased by the number of vowel occurrences in the substring from |*s*| - *m* + 1 to *m*.
     77 2. Otherwise, *SP* is increased by the number of vowel occurrences in the substring from *m* to |*s*| - *m* + 1.
     78 
     79 This way we can easily recalculate *SP**m* + 1 using *SP**m* by adding (subtracting) the number of vowel occurrences on a substring (which is done in *O*(1) time). The complexity of this solution is *O*(*N*).
     80 
     81 Prepared by: [zemen](/profile/zemen "Grandmaster zemen")  
     82 Author of editorial: [zemen](/profile/zemen "Grandmaster zemen")
     83 
     84 [509F - Progress Monitoring](/contest/509/problem/F "Codeforces Round 289 (Div. 2, ACM ICPC Rules)")
     85 
     86 Consider a tree with *n* vertices rooted at vertex 1 and let *b* be the pseudocode’s (DFS) resulting sequence. Then *b*[*l**v*..*l**v* + *size**v* - 1], represents vertex *v*’s subtree, where *l**v* is the index of *v* in *b* and *size**v* is the size of $v$’s subtree.
     87 
     88 Let’s solve the problem using this fact and Dynamic Programming. Let *e*[*l*, *r*] be the number of trees consisting of vertices *a*[*l*], *a*[*l* + 1], …, *a*[*r*] such that running DFS starting from *a*[*l*] will result in a sequence with vertices in the same order as their order in *a*.
     89 
     90 The base case is when *l* = *r* and *e*[*l*, *r*] = 1. Otherwise, ![](https://espresso.codeforces.com/ef7341d555ccc2eb5832b27a6fcfdc4b89026958.png) where the sum is taken over all partitions of the segment [*l* + 1, *r*], that is, over all *k*;*pos*1, ..., *pos**k* + 1, such that *l* + 1 = *pos*1 < *pos*2 < ... < *pos**k* + 1 = *r*, 1 ≤ *k* ≤ *r* - *l*, *a*[*pos*1] < *a*[*pos*2] < ... < *a*[*pos**k*]. Each such partition represents a different way to distribute the vertices among *a*[*l*]’s children’s subtrees. A solution using this formula for calculating *e*[*l*, *r*] will have an exponential running time.
     91 
     92 The final idea is to introduce *d*[*l*, *r*]:  = *e*[*l* - 1, *r*], 2 ≤ *l* ≤ *r* ≤ *n*. It follows that: *d*[*l*, *r*] = ![](https://espresso.codeforces.com/084cee94b13e49a7862f3dca3a09571effe0070c.png) ([statement] is equal to 1 if the statement is true, 0 otherwise) and *e*[*l*, *r*] = *d*[*l* + 1, *r*]. This way *d*[*l*, *r*] and *e*[*l*, *r*] can be calculated in linear time for any segment [*l*, *r*]. The answer to the problem is *e*[1, *n*]. Overall complexity is *O*(*n*3).
     93 
     94 Prepared by: [DPR-pavlin](/profile/DPR-pavlin "Grandmaster DPR-pavlin")  
     95 Author of editorial: [DPR-pavlin](/profile/DPR-pavlin "Grandmaster DPR-pavlin")