codeforces-scrape

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

110.md (8148B)


      1 Source: https://codeforces.com/blog/entry/2547
      2 
      3 1. [Lucky Number](https://codeforces.com/contest/110/problem/A) (Div2 A)
      4 
      5 In this problem you just need to find a number of lucky digits in *n* and output *YES* if it number is equal to 4 or 7, *NO* otherwise.
      6 
      7 2. [Lucky String](https://codeforces.com/contest/110/problem/B) (Div2 B)
      8 
      9 To solve this problem you need to notice that result is a prefix of string *abcdabcdabcd*...*abcd* and output first *n* characters of this string.
     10 
     11 3. [Lucky Sum of Digits](https://codeforces.com/contest/109/problem/A) (Div1 A, Div2 C)
     12 
     13 Let result number contains *a* digits 4 and *b* digits 7. Obviously, that *a* * 4 + *b* * 7 = *n*. Loop through all values of *b*. If we know *b*, we can calculate *a*, ![](https://espresso.codeforces.com/7bd51d538b3a44338bb8ec74cf8fd74d2ccdd720.png). Among all pairs (*a*;*b*) we need to choose one with *a* + *b* minimum. Among all that pairs we need to choose one with *b* minimum. Output will be an integer 444...444777...777, here number of digits 4 equal to *a*, number of digits 7 equal to *b*.
     14 
     15 4. [Lucky Probability](https://codeforces.com/contest/109/problem/B) (Div1 B, Div2 D)
     16 
     17 Let *L*[*i*] - *i*-th lucky number, starting from 1 (*L*[0] = 0, *L*[1] = 4, *L*[2] = 7...). At first choose first *k* lucky number, then second *k* numbers and so on. For each of that group lets find answer, result will be a sum of each of this probabilities. Let index of current first number if *i*, last - *j* (*j* = *i* + *k* - 1). Then we need to find intersection of intervals [*p**l*;*p**r*] and (*L*[*i* - 1];*L*[*i*]], and also [*v**l*;*v**r*] and [*L*[*j*];*L*[*j* + 1]), product of that values will be a number of ways in which *p* < *v*, similarly for *p* > *v*. Sum of all that values for each group will be a total number of ways, then result = total number of ways / ((*p**r* - *p**l* + 1) * (*v**r* - *v**l* + 1)).
     18 
     19 5. [Lucky Tree](https://codeforces.com/contest/109/problem/C) (Div1 C, Div2 E)
     20 
     21 Solve this problem using dynamic programming. Consider that root of a tree is vertex with number 1. Let *F*(*x*) - number of vertex in subtree of vertex *x* for which there is a path containing lucky edge. We will calculate *F*(*x*) using recursion. If *x* is a leaf, than *F*(*x*) = 0. Else, if there is an edge from *x* that leads to *y* and this edge is lucky, then to *F*(*x*) we need to add *C*(*y*), otherwise we add *F*(*y*), here *C*(*y*) - number of vertex in subtree of *y*, including *y*. But, to solve this problem we need to know also *F*'(*x*) - number of vertex which are not in subtree of *x* and there exits a path from *x* to that vertex that contains lucky edge. For a root of tree, *F*'(*x*) equals to 0. We should go recursive from root, and if we are in vertex *x* now, we suppose that *F*'(*x*) is already calculated. If from *x* we can directly go to *y* and that edge is lucky, then *F*'(*y*) = *C*(0) - *C*(*y*), otherwise *F*'(*y*) = *F*'(*x*) + *F*(*x*) - *F*(*y*).
     22 
     23 After that, result equals to ![](https://espresso.codeforces.com/a469bcff2ba54b589c564da0614137dfef5c6602.png).
     24 
     25 6. [Lucky Sorting](https://codeforces.com/contest/109/problem/D)(Div1 D)
     26 
     27 At first, if our array is already sorted, just return 0. Otherwise, if there is no lucky number in *A*, then output  - 1. Otherwise, let *B* is sorted *A* (array from input). Now, for all numbers in *A* we know a final position in *B*. Let *k* is an index of minimal lucky number in *A*. If we want to place integer from position *i* to *j*, we need *A*[*j*] to be lucky number. If is not so, we just *Swap*(*A*[*j*], *A*[*k*]), then *A*[*j*] contains lucky number. After that we can *Swap*(*A*[*i*], *A*[*j*]) and number *A*[*i*] is on position *j*. So, to place one number to it's position in *B*, we need at most two operations and total number that replacements will be not more than *n*, so answer'll contain at most 2*n* operations.
     28 
     29 7. [Lucky Interval](https://codeforces.com/contest/109/problem/E) (Div1 E)
     30 
     31 That is only onw variation of solution, there are diffrent other, which uses same thinking.
     32 
     33 With constraints for *a* and *b* to 107 problem can be solved using KMP algorithm: consider a string *F*(1)*F*(2)*F*(3)*F*(4)...*F*(3 * 107). We need to find first occurrence after index *a* of string *F*(*a*)*F*(*a* + 1)*F*(*a* + 2)...*F*(*a* + *l* - 1). Complexity of that algorithm is *O*(*a* + *l*), obviously, that fails on time and memory. Lets try to optimize this algorithm using some facts from "Lucky numbers theory".
     34 
     35 Split all number interval on block with sizes 100: [0;99], [100;199] and so on. Introduce a concept "class of block". Class number of a block equals to *F*(*i* / 100), where *i* - any number from that block. There are 8 different block classes. There are at most 6 consecutive blocks with same class. All that can be seen using brute force.
     36 
     37 Note #1: if *l* ≥ 1000, then ![](https://espresso.codeforces.com/b2f7b2a20e6084a8624fed211f44e485358d8cbe.png).
     38 
     39 Proof: consider a string *F*(100 * *k*)*F*(100 * *k* + 1)...*F*(100 * *k* + 99). Number of different that strings is equal to number of different classes. For example, for first class that string looks like this:
     40 
     41 00001001000000100100000010010000001001001111211211000010010000001001001111211211
     42 
     43 00001001000000100100
     44 
     45 for second:
     46 
     47 11112112111111211211111121121111112112112222322322111121121111112112112222322322
     48 
     49 11112112111111211211
     50 
     51 and so on. According to the structure of that strings, different block (by classes) can't intersect (there'll be no match). Hence, any sequence of of consecutive blocks which contain at least two blocks of different classes will match only with the same sequence, so shift will be multiple of 100. Since there is no more than 6 consecutive blocks with the same classes, if *l* ≥ 1000 then, obviously, this interval will contain at least two blocks with different classes.
     52 
     53 So, problem with *l* ≥ 1000 can be solved using KMP with complexity *O*((*a* + *l*) / *C*), where *C* equals 100, let function that do that is named *Solve*(*l*, *r*).
     54 
     55 Now we need to solve problem for *l* < 1000. At first, let *a*' is minimal number that *F*(*a*') = *F*(*a*), *F*(*a*' + 1) = *F*(*a* + 1), ..., *F*(*a*' + *l* - 1) = *F*(*a* + *l* - 1), *a*' / 100 = *a* / 100, that can be done using brute force. Then result is the minimum of next numbers:
     56 
     57 - *r* = *Solve*(*a*', *a*' + *l* - 1);
     58 
     59 - Minimum *r*', for which *r* - *r*' <  = 1000, *r*' > *a*, *F*(*r*') = *F*(*a*), *F*(*r*' + 1) = *F*(*a* + 1), ..., *F*(*r*' + *l* - 1) = *F*(*a* + *l* - 1).
     60 
     61 - Minimum *a*'' for which *a*'' > *a*, *a*'' - *a* ≤ 1000 and *F*(*a*'') = *F*(*a*), *F*(*a*'' + 1) = *F*(*a* + 1), ..., *F*(*a*'' + *l* - 1) = *F*(*a* + *l* - 1).
     62 
     63 That solves the problem of some non-100-multiple shifts, but that may be a doubt. Consider input interval is in just one block with class *C*. Then, probably, it is better to go to block with class *C* + 1, for example (397;1) → (400;1). Actually, second point solves that problem, because if block with class *C* + 1 is before *C* (and only in that case we will choose *C* + 1), then next block after current have class *C* + 1. To proof this we can use this note (which can be proofed using brute forces):
     64 
     65 Note #2: if there is two consecutive block, then absolute difference between they classes is not more then 1.
     66 
     67 Hence, if after block *C* (in which input interval is) goes block with class *C* - 1, then we will go to block *C* before *C* + 1, otherwise we will choose it (*C* or *C* + 1).
     68 
     69 Thus, problems solves by accurate analysis all moments. Complexity of solution is *O*((*A* + *L*) / 100), my solution works 1.5 sec. and use 250 mega bytes of memory.
     70 
     71 There are also solution which decompose of blocks with sizes depentding on *l*, that one work faster.