codeforces-scrape

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

615.md (6052B)


      1 Source: https://codeforces.com/blog/entry/22658
      2 
      3 #### [615A - Bulbs](/contest/615/problem/A "Codeforces Round 338 (Div. 2)") (Author: [TheWishmaster](/profile/TheWishmaster "Candidate Master TheWishmaster"))
      4 
      5 Let's make a counter of number of buttons that switch every lamp off. If there is a lamp with zero counter, output NO, otherwise YES.
      6 
      7 code: [15260902](/contest/615/submission/15260902 "Submission 15260902 by maxkvant")
      8 
      9 #### [615B - Longtail Hedgehog](/contest/615/problem/B "Codeforces Round 338 (Div. 2)") (Author: [TheWishmaster](/profile/TheWishmaster "Candidate Master TheWishmaster"))
     10 
     11 Way of solving — dynamic programming. We are given a graph of n vertices and m edges. We will calculate dp[i] — a maximum length of tail that is ending in i-th vertex. We can simply update dp by checking all the edges from i-th vertex(which are leading to vertices with bigger number), and trying to update them. When we have this dp, we can check the answer easily.
     12 
     13 code: [15260851](/contest/615/submission/15260851 "Submission 15260851 by maxkvant")
     14 
     15 #### [615C - Running Track](/contest/615/problem/C "Codeforces Round 338 (Div. 2)") (Author: [maxkvant](/profile/maxkvant "Candidate Master maxkvant"))
     16 
     17 The idea is that if can make a substring t[i, j] using k coatings, then we can also make a substring t[i + 1, j] using k coatings. So we should use the longest substring each time.
     18 
     19 Let n = |s|, m = |t|. On each stage we will search for the longest substring in s and s_reversed to update the answer. We can do it in several ways:
     20 
     21 * Calculate lcp[i][j] — longest common prefix t[i, m] and s[j, n], lcprev[i][j] — longest common prefix t[i, m] and s[j, 1]. Find longest means find max(max(lcp[i][1], lcp[i][2], ..., lcp[i][n]), max(lcprev[i][1], lcprev[i][2], ..., lcprev[i][n])).
     22 
     23 calculation lcp:
     24 
     25 ```
     26 for (int i = m; i >= 1; i--)
     27      for (int j = n; j >= 1; j--) 
     28           if (t[i] == s[j])
     29               lcp[i][j] = lcp[i + 1][j + 1] + 1;
     30 ```
     31 
     32 code: [15277213](/contest/615/submission/15277213 "Submission 15277213 by maxkvant")
     33 
     34 Let's check iterative t[i, i ] exists in s as a substring, t[i, i  + 1] t[i, i  + 2] .... We will make an array endPos, where endPos[j] is true when t[i, i + cur_len - 1] = s[j - cur_len + 1, j] (t[1, i — 1] greedy already got). We will update this array, adding symbols t[i], t[i + 1], t[i + 2] and so on. We will make one more array — for s_reversed. (more details in code)
     35 
     36 Overall time complexity will be ![](https://espresso.codeforces.com/f3a03408a9871145b597e03cf866970f51f2962c.png)
     37 
     38 code: [15260867](/contest/615/submission/15260867 "Submission 15260867 by maxkvant")
     39 
     40 trie solution: [15260870](/contest/615/submission/15260870 "Submission 15260870 by maxkvant")
     41 
     42 ##### bonus
     43 
     44 Can you solve with ![](https://espresso.codeforces.com/42aa5a004e63546e02757fab78f8e5705dfde32c.png) complexity? ![](https://espresso.codeforces.com/cee75da3959b285b4496c49d37809f98b73b3cfe.png)? ![](https://espresso.codeforces.com/e005d0a9c4f002790d048610174ac89e77d73473.png) ?
     45 
     46 Σ — alphabet size.
     47 
     48 #### [615D - Multipliers](/contest/615/problem/D "Codeforces Round 338 (Div. 2)") (Author: [maxkvant](/profile/maxkvant "Candidate Master maxkvant"))
     49 
     50 Let d(x) be a number of divisors of x, and f(x) be the product of divisors. Let *x* = *p*1α1*p*2α2... *p**n*α*n*, then *d*(*x*) = (α1 + 1)·(α2 + 1)... (α*n* + 1)
     51 
     52 ![](https://espresso.codeforces.com/4496cc0cc4e50c0cd2c6a877746f09868a869e28.png). There is ![](https://espresso.codeforces.com/9ca0ce272a5af9aa70858d63a60bc70966f5ea89.png) pairs of divisors of type ![](https://espresso.codeforces.com/20c08fdf66485ba15627a75eb56926f8aa1a0daa.png), ![](https://espresso.codeforces.com/a6b43b96def3df9aa82f2ce4c3c8e40eb3a75619.png), and if x is a perfect square we have one more divisor : ![](https://espresso.codeforces.com/dd68ff2d8e5b97302506ac32d308bb521ab84a26.png).
     53 
     54 for a prime *m* and *a* ≠ 0 the statement ![](https://espresso.codeforces.com/271bbaaa67ecaf8e2472aa9e7ed3c1958e7edc5f.png) (little Fermat theorem)
     55 
     56 We can see that ![](https://espresso.codeforces.com/48b6555ef95d771999dc0f06b43f70bd6caffab3.png), if a and b are co prime.
     57 
     58 Now we can count the answer:
     59 
     60 ```
     61 d = 1;
     62 ans = 1;
     63 for (int i = 0; i < l; i++) {
     64     fp = binPow(p[i], (cnt[i] + 1) * cnt[i] / 2);
     65     ans = binPow(ans, (cnt[i] + 1)) * binPow(fp, d) % MOD;
     66     d = d * (cnt[i] + 1) % (MOD - 1);
     67 }
     68 ```
     69 
     70 code: [15260890](/contest/615/submission/15260890 "Submission 15260890 by maxkvant")
     71 
     72 ##### bonus
     73 
     74 Another problem.
     75 
     76 Given secquence (*p*1, *k*1),  (*p*2, *k*2), ...,  (*p**n*, *k**n*)  
     77  (*p**i* — distinct primes) and q queries (l, r) to calculate *f*(*p**l**k**l*·*p**l* + 1*k**l* + 1... *p**r**k**r*)%*MOD*.
     78 
     79 Can you solve with ![](https://espresso.codeforces.com/e328b65025d43e9c48adb1b1b78f523231cf771e.png) complexity?
     80 
     81 Suppose `r - l + 1 = M = const` in all queries. Can you solve with ![](https://espresso.codeforces.com/fffbdc04d95419f12030ac402118fb2947edfdd8.png) complexity?
     82 
     83 #### [615E - Hexagons](/contest/615/problem/E "Codeforces Round 338 (Div. 2)") (Author: [TheWishmaster](/profile/TheWishmaster "Candidate Master TheWishmaster"))
     84 
     85 Let's see how the coordinates are changing while we move from current cell to one of the 6 adjacent cells — let's call this 6 typed of moves. If we know the number of moves of each type on our way, then we know the coordinates of the end of the way. We will divide the way into rings.
     86 
     87 ![ ](/predownloaded/27/59/2759a01f93378e9dc938b16250fa004a19bb698c.png)
     88 
     89 Let's count the number of moves of each type for the first ring. Next ring will have one more move of each type. Length of each ring = length of previous + 6. It is an arithmetic progression. Using well-known formulas and binary search we calculate the number of the last ring and overall length of previous rings. Now we have to brute-force 6 types of the last move and calculate the answer.
     90 
     91 code: [15260879](/contest/615/submission/15260879 "Submission 15260879 by maxkvant")