codeforces-scrape

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

448.md (5735B)


      1 Source: https://codeforces.com/blog/entry/13042
      2 
      3 [448A - Rewards](/contest/448/problem/A "Codeforces Round 256 (Div. 2)")
      4 
      5 Solution:[7139559](/contest/448/submission/7139559 "Submission 7139559 by oversolver")
      6 
      7 Because rewards of one type can be on one shelf, lets calculate number of cups — *a* and number of medals — *b*. Minimum number of shelves that will be required for all cups can be found by formula (*a* + 5 - 1) / 5. The same with shelves with medals: (*b* + 10 - 1) / 10. If sum of this two values more than *n* then answer is "NO" and "YES" otherwise.
      8 
      9 [448B - Suffix Structures](/contest/448/problem/B "Codeforces Round 256 (Div. 2)")
     10 
     11 Solution:[7139584](/contest/448/submission/7139584 "Submission 7139584 by oversolver")
     12 
     13 Consider each case separately. If we use only suffix automaton then *s* transform to some of its subsequence. Checking that *t* is a subsequence of *s* can be performed in different ways. Easiest and fastest — well-known two pointers method. In case of using suffix array we can get every permutation of *s*. If it is not obvious for you, try to think. Thus, *s* and *t* must be anagrams. If we count number of each letter in each string, we can check this. If every letter appears in *s* the same times as in *t* then words are anagrams. In case of using both structures strategy is: remove some letters and shuffle the rest. It is possible if every letter appears in *s* not less times than in *t*. Otherwise it is impossible to make *t* from *s*. Total complexity *O*(|*s*| + |*t*| + 26).
     14 
     15 [448C - Painting Fence](/contest/448/problem/C "Codeforces Round 256 (Div. 2)")
     16 
     17 Solution:[7139610](/contest/448/submission/7139610 "Submission 7139610 by oversolver")
     18 
     19 To solve this problem we need to understand some little things. First, every horizontally stroke must be as widely as possible. Second, under every horizontally stroke should be only horizontally strokes. So, if bottom of fence painted by horizontally stroke then number of this strokes must at least *min*(*a*1, *a*2, ..., *a**n*). These strokes maybe divides fence into some unpainted disconnected parts. For all of these parts we need to sum they answers. Now its clearly that solution is recursive. It takes segment [*l*, *r*] and height of painted bottom *h*. But we must not forget about situation when all planks painted with vertically strokes. In this case answer must be limited by *r* - *l* + 1 (length of segment). With given constrains of *n* we can find minimum on segment by looking all the elements from segment. Complexity in this case will be *O*(*n*2). But if we use for example segment tree, we can achieve *O*(*nlogn*) complexity.
     20 
     21 [448D - Multiplication Table](/contest/448/problem/D "Codeforces Round 256 (Div. 2)")
     22 
     23 Solution:[7139620](/contest/448/submission/7139620 "Submission 7139620 by oversolver")
     24 
     25 Solution is binary search by answer. We need to find largest *x* such that amount of numbers from table, least than *x*, is strictly less than *k*. To calculate this count we sum counts from rows. In *i* th row there will be ![](https://espresso.codeforces.com/ff7a4018dc8b9d8655be143444ca4f435a052ea8.png). Total complexity is *O*(*nlog*(*nm*)).
     26 
     27 [448E - Divisors](/contest/448/problem/E "Codeforces Round 256 (Div. 2)")
     28 
     29 Solution:[7139644](/contest/448/submission/7139644 "Submission 7139644 by oversolver")
     30 
     31 Learn how to transform *X**i* into *X**i* + 1. For this we need to concatenate lists of divisors for all elements of *X**i*. To do this efficiently, precalculate divisors of *X* (because for every *i* *X**i* consist of its divisors). It can be done by well-known method with ![](https://espresso.codeforces.com/6a50bf098f1c6c2c202d6ed065157d06f7724110.png) complexity. How to calculate divisors of divisors? Need to know that for the given constrains for *X* maximum number of divisors *D*(*X*) will be 6720 (in the number 963761198400), so divisors of divisors can be calculated in *O*(*D*2(*X*)) time. With this lists we can transform *X**i* into *X**i* + 1 in *O*(*N*) time, were *N* = 105 — is the limit of numbers in output. Now learn how to transform *X**i* into *X*2*i*. What says *X**i*? Besides what would be *X* after *i* steps, it can tell where goes everyone divisor of *X* after *i* - 1 steps. Actually, *X**i* is concatenation of all *Y**i* - 1, where *Y* is divisor of *X*. For example, 103 = [1, 1, 1, 2, 1, 1, 5, 1, 1, 2, 1, 5, 1, 2, 5, 10] = [1] + [1, 1, 2] + [1, 1, 5] + [1, 1, 2, 1, 5, 1, 2, 5, 10] = 12 + 22 + 52 + 102. How to know which segment corresponds for some *Y*? Lets *pos*(*Y*) be the first index of *Y* in *X**i*. Then needed segment starts from *pos*(*prev*(*Y*)) + 1 and ends in *pos*(*Y*), where *prev*(*Y*) is previous divisor before *Y* in sorted list of divisors. So, to make *X*2*i* from *X**i* we need to know where goes every element from *X**i* after *i* steps. We know all its divisors — it is one step, and for every divisor we know where it goes after *i* - 1 step. Thus, we again need to concatenate some segments in correct order. It also can be done in *O*(*N*) time. How to find now *X**k* for every *k*? The method is similar as fast exponentiation:
     32 
     33 *X**k* = [*X*] when *k* = 0,
     34 
     35 if *k* is odd then transform *X**k* - 1 to *X**k*,
     36 
     37 if *k* is even then transform *X**k* / 2 to *X**k*.
     38 
     39 This method takes *O*(*logk*) iterations. And one small trick: obviously that for *X* > 1 *X**k* starts from *k* ones, so *k* can be limited by *N*. Total complexity of solution is ![](https://espresso.codeforces.com/dbfa96de7a80c249e45e2c892fe3680b9c03b4f7.png).