codeforces-scrape

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

122.md (4692B)


      1 Source: https://codeforces.com/blog/entry/2956
      2 
      3 **1. [Lucky Div (Div2 A)](/contest/122/problem/A "122A - Lucky Division")**
      4 
      5 In this problem you just need to loop through the integers *i* from 1 to *n* determine, is *i* lucky, if yes, then try, if *n* mod *i* = 0, then answer is "YES". If there are no such *i*, answer is "NO".
      6 
      7 **2. [Lucky Substring (Div2 B)](/contest/122/problem/B "122B - Lucky Substring")**
      8 
      9 Notice, that answer is either one digit or -1. So, if there are no 4 and 7 digits, then answer is -1. Else, if there is more or equel number of digits 4, then answer is 4, else answer is 7.
     10 
     11 **3. [Lucky Sum (Div1 A + Div2 C)](/contest/121/problem/A "121A - Lucky Sum")**
     12 
     13 Let generate all lucky number between 1 and 1010. Consider all segment [1;*L*0], [*L*0 + 1;*L*1], [*L*1 + 1;*L*2] ... Then the result equals to product of intersection of segments [1;*L*0] and [1;*n*] by *L*0 plus size of intersection of [*L*0 + 1;*L*1] and  [1;*n*] multiplied by *L*1 and so on.
     14 
     15 **4. [Lucky Operation (Div1 B + Div2 D)](/contest/121/problem/B "121B - Lucky Transformation")**
     16 
     17 Notice, that if there exits such *i* that *i* mod 2 = 0 and *d**i* = 4 and *d**i* + 1 = 7 and *d**i* - 1 = 4 then after that operation there will be a loop. So, let we simple do all operation from left ro right, and, when we will win our loop, just return a rusult (which variates by *k* mod 2 (*k* is one that leaves after operation from left side).
     18 
     19 **5. [Lucky Permuation (Div1 C + Div2 E)](/contest/121/problem/C "121C - Lucky Permutation")**
     20 
     21 If *n* ≤ 14 let find out, is *k* more than *n*! or not? If yes, then return -1. Then, notice, that since *k* ≤ 109, then at most 13 elements from right (suffix) will change. So, element from left of this part (prefix) will not change (then we can just find a number of lucky numbers on than range). To find result for the rest of the permutation (suffix) we need to find *k*-th permutation of number from 1 to *t* (*t* is maximun integer, such that *t*! ≤ *k*). After we find that permutation, we can just loop through that permutation and count result.
     22 
     23 **6. [Lucky Segments (Div1 D)](/contest/121/problem/D "121D - Lucky Segments")**
     24 
     25 Lei calculate arrays *L* and *R*. Let for all lucky *i*, *L*[*i*] = number of operation needed to move every segment, which's right end is to left from *i* to *i*. *R*[*i*] = number of operation needed to move every segment which left end is to right to *i*. How to calculate such array? Just use a sorting. Let arrange array *A* of pairs of integers, first - number, second equals to 0, if that number end of some segment, 1 if that number is lucky. Then, iterate from left to right, counting number of segment end we counted and *s**i*, *s**i* = *s**i* - 1 + (*A**i* - *A**i* - 1) * *c**i*. The same way you can use to *R*. Now, to find the answer we must find (using method of two pointers of binary search) pair of indexes *x* and *y*, such that  *i* ≤ *j*, *L**j* + *R**i* ≤ *k*, *Lucky**j* - *Lucky**i* + 1 ≤  min_size_of_input_segment. Also, is this problem you should arrange function *Mul*(*a*, *b*), which return *min*(*a* * *b*, *INF*). Since simple multiplication overflows, then you can use multipling modulo 264 or double or min-long-arithmetic.
     26 
     27 **7. [Lucky Array (Div1 E)](/contest/121/problem/E "121E - Lucky Array")**
     28 
     29 In this problem you can use many different algorithms, here is one of them. Obviously, number of different lucky number is 30, because *A**i* always is  ≤ 10000. Let *D**i* - difference between minimum lucky number which is greater than or equal to *A**i* and *A**i*. Now, we need to have 5 (but you can use less number) of operation on *D*: Subtract(l, r, d) - subtract number *d* from all *A**i* (*l* ≤ *i* ≤ *r*), Minimum(l, r) - minumum number of all *D**i* (*l* ≤ *i* ≤ *r*), Count(l, r) - how many times that minimum occared in that interval, Left(l, r) = leftmost occarence of that minimum, Set(i, d) - assign *d* to *D**i* (*D**i* = *d*). Now, we can do our operations. If our operation is "count", then we need to find minimum number *d* (*d* =  Minimum(l, r)), if it is equal to 0, then answer is Count(l, r, 0), otherwise, answer is 0. If out operation is "add", then we need to Subtract(l, r, d), but now some *D**i* might be less than 0. So, while, Minimum(l, r)  ≤ 0, let j = Left(l, r), assign *D**j* new value (use Set(j, *D**j*')), which can be calculated with complaxity *O*(1).
     30 
     31 Complexity of this algorithm is *O*(*m* * *log*(*n*) + *n* * *log*(*n*) * *C*), where *C* is equal to 30.