codeforces-scrape

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

520.md (21342B)


      1 Source: https://codeforces.com/blog/entry/16736
      2 
      3 We would like to thank the testers of this round's and Winter Computer Camp olympiad's problems: [alger95](/profile/alger95 "Master alger95"), [thefacetakt](/profile/thefacetakt "Expert thefacetakt"), [adamant](/profile/adamant "Candidate Master adamant"), [-imc-](/profile/-imc- "Candidate Master -imc-"), [riskingh](/profile/riskingh "Candidate Master riskingh"), [ASverdlov](/profile/ASverdlov "Expert ASverdlov").
      4 
      5 Make sure to comment if you find any mistakes.
      6 
      7 **UPD**: I've just remembered to put up the usual challenges for the problems. So, here they go.
      8 
      9 [520A - Pangram](/contest/520/problem/A "Codeforces Round 295 (Div. 2)")
     10 
     11 Idea: [Endagorion](/profile/Endagorion "International Grandmaster Endagorion")
     12 
     13 Preparation: [Endagorion](/profile/Endagorion "International Grandmaster Endagorion")
     14 
     15 To check that every letter is present in the string we can just make a boolean array of size 26 and for every letter set the corresponding variable to TRUE. In the end check that there are 26 TRUEs. That is an *O*(*n*) solution. Also don't forget to change all letters to lowercase (or all to uppercase).
     16 
     17 To make all the letters lowercase, one could use standard functions, like `tolower` in Python. Also, it is known that the letters from `a` to `z` have consecutive ASCII numbers, as well as `A` to `Z`; an ASCII number of symbol is `ord(c)` in most languages. So, to get the number of a lowercase letter in the alphabet one can use `ord(c) - ord('a')` in most languages, or simply `c - 'a'` in C++ or C (because a `char` in C/C++ can be treated as a number); to check if a letter is lowercase, the inequality `ord('a') <= ord(c) && ord(c) <= ord('z')` should be checked.
     18 
     19 **Challenge**: how many pangrams of length *n* are there? Strings that differ only in capitalization of some letters are considered distinct. Can you find the answer modulo some prime *p* in linear time?
     20 
     21 [520B - Two Buttons](/contest/520/problem/B "Codeforces Round 295 (Div. 2)")
     22 
     23 Idea: [Endagorion](/profile/Endagorion "International Grandmaster Endagorion")
     24 
     25 Preparation: [Endagorion](/profile/Endagorion "International Grandmaster Endagorion")
     26 
     27 The simplest solution is simply doing a breadth-first search. Construct a graph with numbers as vertices and edges leading from one number to another if an operation can be made to change one number to the other. We may note that it is never reasonable to make the number larger than 2*m*, so under provided limitations the graph will contain at most 2·104 vertices and 4·104 edges, and the BFS should work real fast.
     28 
     29 There is, however, an even faster solution. The problem can be reversed as follows: we should get the number *n* starting from *m* using the operations "add 1 to the number" and "divide the number by 2 if it is even".
     30 
     31 Suppose that at some point we perform two operations of type 1 and then one operation of type 2; but in this case one operation of type 2 and one operation of type 1 would lead to the same result, and the sequence would contain less operations then before. That reasoning implies that in an optimal answer more than one consecutive operation of type 1 is possible only if no operations of type 2 follow, that is, the only situation where it makes sense is when *n* is smaller than *m* and we just need to make it large enough. Under this constraint, there is the only correct sequence of moves: if *n* is smaller than *m*, we just add 1 until they become equal; else we divide *n* by 2 if it is even, or add 1 and then divide by 2 if it is odd. The length of this sequence can be found in ![](https://espresso.codeforces.com/9040a33098f83986b0de64475c66584fbfdf0e22.png).
     32 
     33 **Challenge**: suppose we have a generalized problem: we want to get *n* starting from *m* using two operations "subtract *a*" and "multiply by *b*". Generalize the solution to find the minimal number of moves to get from *n* to *m* in ![](https://espresso.codeforces.com/9040a33098f83986b0de64475c66584fbfdf0e22.png) time if *a* and *b* are coprime. Can you do it if *a* and *b* may have common divisors greater than 1?
     34 
     35 [520C - DNA Alignment](/contest/520/problem/C "Codeforces Round 295 (Div. 2)")/[521A - DNA Alignment](/contest/521/problem/A "Codeforces Round 295 (Div. 1)")
     36 
     37 Idea: [Endagorion](/profile/Endagorion "International Grandmaster Endagorion")
     38 
     39 Preparation: [Endagorion](/profile/Endagorion "International Grandmaster Endagorion")
     40 
     41 What is ρ(*s*, *t*) equal to? For every character of *s* and every character of *t* there is a unique cyclic shift of *t* that superposes these characters (indeed, after 0, ..., *n* - 1 shifts the character in *t* occupies different positions, and one of them matches the one of the character of *s*); therefore, there exist *n* cyclic shifts of *s* and *t* that superpose these characters (the situation is symmetrical for every position of the character of *s*). It follows that the input in ρ from a single character *t**i* is equal to *n* × (the number of characters in *s* equal to *t**i*). Therefore, ρ(*s*, *t*) is maximal when every character of *t* occurs the maximal possible number of times in *s*. Simply count the number of occurences for every type of characters; the answer is *K**n*, where *K* is the number of character types that occur in *s* most frequently. This is an *O*(*n*) solution.
     42 
     43 **Challenge**: we know that ρ*max*(*s*) = *n*2·*C*(*s*), where *C*(*s*) is the maximal number that any character occurs in *s*. How many strings *s* of length *n* with characters from an alphabet of size *k* have *C*(*s*) = *m*? Can you find an *O*(*kn*2) solution? An ![](https://espresso.codeforces.com/da98302e7034110f8148a8649efa7c74d35f5703.png) solution? An ![](https://espresso.codeforces.com/87f5d930f106abda1a36205b5d3814e3269eb647.png) solution? Maybe even better? (Hint: the modulo should be an *appropriately chosen* prime number for a fast solution =)).
     44 
     45 [520D - Cubes](/contest/520/problem/D "Codeforces Round 295 (Div. 2)")/[521B - Cubes](/contest/521/problem/B "Codeforces Round 295 (Div. 1)")
     46 
     47 Idea: [savinov](/profile/savinov "International Master savinov")
     48 
     49 Preparation: [savinov](/profile/savinov "International Master savinov"), [sokian](/profile/sokian "International Master sokian"), [zemen](/profile/zemen "International Master zemen")
     50 
     51 Basically, the first player should maximize the lexicographical order of numbers, and the second player should minimize it. Thus, at every move the first player should choose the largest available number, and the second should choose the minimal one.
     52 
     53 First of all, how do we check if the cube can be removed? It is impossible only if there is some cube "supported" by it (i.e., it has coordinates (*x* - 1, *y* + 1), (*x*, *y* + 1), (*x* + 1, *y* + 1)) such that our cube is the only one supporting it. This can be checked explicitly. The large coordinates' limitations do not allow us to store a simply array for that, so we should use an associative array, like a `set` in C++.
     54 
     55 Now we should find the maximal/minimal number that can be removed. A simple linear search won't work fast enough, so we store another data structure containing all numbers available to remove; the structure should allow inserting, erasing and finding global minimum/maximum, so the `set` C++ structure fits again.
     56 
     57 When we've made our move, some cubes may have become available or unavailable to remove. However, there is an *O*(1) amount of cubes we have to recheck and possibly insert/erase from our structure: the cubes (*x* ± 1, *y*) and (*x* ± 2, *y*) may have become unavailable because some higher cube has become dangerous (that is, there is a single cube supporting it), and some of the cubes (*x* - 1, *y* - 1), (*x*, *y* - 1) and (*x* + 1, *y* - 1) may have become available because our cube was the only dangerous cube that it has been supporting. Anyway, a simple recheck for these cubes will handle all the cases.
     58 
     59 This solution is ![](https://espresso.codeforces.com/5e7dae7c1838af7ba7570bdf02ff61029b043be6.png) if using the appropriate data structure.
     60 
     61 **Challenge** (inspired by questions from [jk_qq](/profile/jk_qq "Expert jk_qq") and [RetiredAmrMahmoud](/profile/RetiredAmrMahmoud "Expert RetiredAmrMahmoud")): suppose that the players put the numbers from right to left, that is, from the least significant digit to the most significant. The first player still wants to maximize the resulting number, and the second wants to minimize it. If the original rules of taking cubes apply, finding the optimal strategy for the players seems intractable. Try to solve this problem in the case where all the cubes are stacked in several independent towers; that is, a cube may only be taken from the top of any tower.
     62 
     63 [520E - Pluses everywhere](/contest/520/problem/E "Codeforces Round 295 (Div. 2)")/[521C - Pluses everywhere](/contest/521/problem/C "Codeforces Round 295 (Div. 1)")
     64 
     65 Idea: [Endagorion](/profile/Endagorion "International Grandmaster Endagorion")
     66 
     67 Preparation: [gchebanov](/profile/gchebanov "Grandmaster gchebanov"), [DPR-pavlin](/profile/DPR-pavlin "International Master DPR-pavlin")
     68 
     69 Consider some way of placing all the pluses, and a single digit *d**i* (digits in the string are numbered starting from 0 from left to right). This digit gives input of *d**i*·10*l* to the total sum, where *l* is the distance to the nearest plus from the right, or to the end of string if there are no pluses there. If we sum up these quantities for all digits and all ways of placing the pluses, we will obtain the answer.
     70 
     71 For a given digit *d**i* and some fixed *l*, how many ways are there to place the pluses? First of all, consider the case when the part containing the digit *d**i* is not last, that is, *i* + *l* < *n* - 1. There are *n* - 1 gaps to place pluses in total; the constraint about *d**i* and the distance *l* means that after digits *d**i*, ..., *d**i* + *l* - 1 there are no pluses, while after the digit *d**i* + *l* there should be a plus. That is, the string should look as follows:
     72 
     73 ![](https://espresso.codeforces.com/4adc1e0994dce507893e25106998c1825a5014b2.png)
     74 
     75 Here a dot means a gap without a plus, and a question mark means that it's not important whether there is a plus or not. So, out of *n* - 1 possible gaps there are *l* + 1 gaps which states are defined, and there is one plus used in these gaps. That means that the other (*n* - 1) - (*l* + 1) = *n* - *l* - 2 gaps may contain *k* - 1 pluses in any possible way; that is, the number of such placements is ![](https://espresso.codeforces.com/7928746671d4d136b992d11f652fb368daed98d2.png). A similar reasoning implies that if the digit *d**i* is in the last part, that is, *i* + *l* = *n* - 1, the number of placements is ![](https://espresso.codeforces.com/243d5245285f1e30f2d280f28401216fe8168467.png).
     76 
     77 To sum up, the total answer is equal to
     78 
     79 ![](https://espresso.codeforces.com/7e2c3204591bf2dbbbef3f589061a83f773abd16.png)
     80 
     81 Let us transform the sum:
     82 
     83 ![](https://espresso.codeforces.com/a44c37049b131a9d6ca42f3a87c5c0eefc9ca9c0.png)
     84 
     85 To compute these sums, we will need to know all powers of 10 up to *n*-th (modulo 109 + 7), along with the binomial coefficients. To compute the binomials, recall that ![](https://espresso.codeforces.com/e0362e32a4337cab8d529bff99cf3949d97eebe9.png), so it is enough to know all the numbers *k*! for *k* upto *n*, along with their modular inverses. Also we should use the prefix sums of *d**i*, that is, the array ![](https://espresso.codeforces.com/3744416b327cc8626e0abff5fab07872b6ac7ed0.png). The rest is simple evaluation of the above sums.
     86 
     87 The total complexity is ![](https://espresso.codeforces.com/e39671ea46606d79738dd2b1f841c393529fab24.png), because the common algorithms for modular inverses (that is, Ferma's little theorem exponentiation or solving a diophantine equation using the Euclid's algorithm) have theoritcal worst-case complexity of ![](https://espresso.codeforces.com/b6d09dd20427de8253012f269cf91ff6e504742d.png). However, one can utilize a neat trick for finding modular inverses for first *n* consecutive numbers in linear time for a total complexity of *O*(*n*); for the description of the method refer to this [comment](https://codeforces.com/blog/entry/13908#comment-188854) by [Kaban-5](/profile/Kaban-5 "Candidate Master Kaban-5") (not sure why it has a negative rating, I found this quite insightful; maybe anyone can give a proper source for this method?).
     88 
     89 **Challenge**: now we want to find the sum of all expressions that are made by placing *k* pluses with *a* ≤ *k* ≤ *b*; that is, we want to find the sum of the answers for the original problem with *k* = *a*, ..., *b*; here *a* and *b* can be any integers with 0 ≤ *a* ≤ *b* ≤ *n* - 1. There is an obvious *O*(*n*2) solution: just find the answers for all *k* separately. Can you find a linear solution?
     90 
     91 [521D - Shop](/contest/521/problem/D "Codeforces Round 295 (Div. 1)")
     92 
     93 Idea: [Endagorion](/profile/Endagorion "International Grandmaster Endagorion")
     94 
     95 Preparation: [gchebanov](/profile/gchebanov "Grandmaster gchebanov")
     96 
     97 Suppose the only type of upgrades we have is multiplication. It doesn't even matter for the answer which particular skill we are going to multiply, so we just choose several upgrades with greatest values of *b**i*.
     98 
     99 Now we have additions as well; set multiplications aside for a moment. It is clear that for every skill we should choose several largest additions (maybe none). Let us sort the additions for every skill by non-increasing; now we should choose several first upgrades for each type. Now, for some skill the (non-increasing) sorted row of *b*'s is *b*1, ..., *b**l*, and the initial value of the skill is *a*. Now, as we have decided to take some prefix of *b*'s, we know that if we take the upgrade *b**i*, the value changes from *a* + *b*1 + ... + *b**i* - 1 to *a* + *b*1 + ... + *b**i* - 1 + *b**i*. That is, the ratio by which the value (and the whole product of values) is going to be multiplied by is the fraction ![](https://espresso.codeforces.com/6bd2a8b8b301f7b493fafa32334f2355bd12ee2c.png). Now, with that ratio determined unambigiously for each addition upgrade, every addition has actually become a multiplication. =) So we have to compute the ratios for all additions (that is, we sort *b*'s for each skill separately and find the fractions), and then sort the multiplications and additions altogether by the ratio they affect the whole product with. Clearly, all multiplications should be used after all the additions are done; that is, to choose which upgrades we use we should do the ratio sorting, but the order of actual using of upgrades is: first do all the additions, then do all the multiplications.
    100 
    101 Finally, let's deal with the assignment upgrades. Clearly, for each skill at most one assignment upgrade should be used, and if it used, it should the assignment upgrade with the largest *b* among all assignments for this skill. Also, if the assignment is used, it should be used before all the additions and multiplications for this skill. So, for each skill we should simply determine whether we use the largest assignment for this skill or not. However, if we use the assignment, the ratios for the additions of current skill become invalid as the starting value of *a* is altered.
    102 
    103 To deal with this problem, imagine that we have first chosen some addition upgrades, and now we have to choose whether we use the assignment upgrade or not. If we do, the value of the skill changes from *a* + *b*1 + ... + *b**k* to *b* + *b*1 + ... + *b**k*. That is, the assignment here behaves pretty much the same way as the addition of *b* - *a*. The only difference is that once we have chosen to use the assignment, we should put it before all the additions.
    104 
    105 That is, all largest assigments for each skill should be made into additions of *b* - *a* and processed along with all the other additions, which are, as we already know, going to become multiplications in the end. =)
    106 
    107 Finally, the problem is reduced to sorting the ratios for all upgrades. Let us estimate the numbers in the fractions. The ratio for a multiplication is an integer up to 106; the ratio for an addition is a fraction of general form ![](https://espresso.codeforces.com/c8ec5b14e159b23b19c997adc3a2e858641d9975.png). As *k* can be up to 105, and *b**i* is up to 106, the numerator and denominator of such fraction can go up to 1011. To compare fractions ![](https://espresso.codeforces.com/a7487d7e62f90136b78ae3fbf0a008396f146e13.png) and ![](https://espresso.codeforces.com/c443c7703e51f03d0eece0b96b9e84e425878209.png) we should compare the products *ad* and *bc*, which can go up to 1022 by our estimates. That, unfortunately, overflows built-in integer types in most languages. However, this problem can be solved by subtracting 1 from all ratios (which clearly does not change the order of ratios), so that the additions' ratios will look like ![](https://espresso.codeforces.com/048f9e639ab2ca01c2ddca5a04ff4d94a7d407b2.png). Now, the numerator is up to 106, the products in the comparison are up to 1017, which fits in 64-bit integer type in any language.
    108 
    109 **Challenge**: suppose that you have to compare two fractions ![](https://espresso.codeforces.com/a7487d7e62f90136b78ae3fbf0a008396f146e13.png) and ![](https://espresso.codeforces.com/c443c7703e51f03d0eece0b96b9e84e425878209.png), where *a*, *b*, *c*, *d* may be up to 1018. What way would you use to do that? Can you find a simple solution that does not involve long arithmetics, floating-point number or magic built-in integer types tricks (but may perform a non-constant number of operations)?
    110 
    111 [521E - Cycling City](/contest/521/problem/E "Codeforces Round 295 (Div. 1)")
    112 
    113 Idea: [Endagorion](/profile/Endagorion "International Grandmaster Endagorion")
    114 
    115 Preparation: [Endagorion](/profile/Endagorion "International Grandmaster Endagorion")
    116 
    117 We have to find two vertices in an undirected graph such that there exist three vertex- and edge-independent paths between them. This could easily be a flow problem if not for the large constraints.
    118 
    119 First of all, we can notice that all the paths between vertices should lie in the same [biconnected component](https://en.wikipedia.org/wiki/Biconnected_component) of the graph. Indeed, for every simple cycle all of its edges should lie in the same biconnected component, and the three-paths system is a union of cycles. Thus, we can find all the biconnected components of the graph and try to solve the problem for each of them independently. The computing of biconnected components can be done in linear time; a neat algorithm for doing this is described in the Wikipedia article by the link above.
    120 
    121 Now, we have a biconnected component and the same problem as before. First of all, find any cycle in this component (with a simple DFS); the only case of a biconnected component that does not contain a cycle is a single edge, which is of no interest. Suppose that no vertex of this cycle has an adjacent edge that doesn't lie in the cycle; this means the cycle is not connected to anything else in the component, so the component is this cycle itself, in which case there is clearly no solution.
    122 
    123 Otherwise, find a vertex *v* with an adjacent edge *e* that doesn't lie in the cycle (denote it *c*). If we can find a path *p* starting with *e* that arrives at a cycle vertex *u* (different from *v*), then we can find three vertex-distinct paths between *v* and *u*: one path is *p*, and two others are halves of the initial cycle. To find *p*, start a DFS from the edge *e* that halts when it arrives to vertex of *c* (that is different from *v*) and recovers all the paths.
    124 
    125 What if we find that no appropriate path *p* exists? Denote *C* the component traversed by the latter DFS. The DFS did not find any path between vertices of *C*\ {*v*} and *c*\ {*v*}, therefore every such path should pass through *v*. That means that upon deletion of *v*, the component *C*\ {*v*} becomes separated from all vertices of *c*\ {*v*}, which contradicts with the assumption that the component was biconnected. That reasoning proves that the DFS starting from *e* will always find the path *p* and find the answer if only a biconnected component was not a cycle nor a single edge.
    126 
    127 Finally, we obtain that the only case when the answer is non-existent is when all the biconnected components are single edges or simple cycles, that is, the graph is a union of disconnected [cactuses](https://en.wikipedia.org/wiki/Cactus_graph). Otherwise, a couple of DFS are sure to find three vertex-disjoint paths. This yields an *O*(*n* + *m*) solution; a few logarithmic factors for simplification here and there are also allowed.
    128 
    129 **Challenge**: how many graphs *G* on *n* labeled vertices exist such that there exist two vertices of *G* connected by three disjoint paths? (Hint: we have already shown that it suffices to count the number of disjoint unions of *cacti*.) Find the answer modulo 109 + 7. Can you come up with any polynomial-time solution? An *O*(*n*3) solution? Maybe even better?