Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

witua's blog

By witua, 9 years ago, translation, In English,

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".


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.


Let generate all lucky number between 1 and 1010. Consider all segment [1;L0], [L0 + 1;L1], [L1 + 1;L2] ... Then the result equals to product of intersection of segments [1;L0] and [1;n] by L0 plus size of intersection of [L0 + 1;L1] and  [1;n] multiplied by L1 and so on.

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).


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.


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.


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).

Complexity of this algorithm is O(m * log(n) + n * log(n) * C), where C is equal to 30.
 
 
 
 
  • Vote: I like it
  • +34
  • Vote: I do not like it

9 years ago, # |
  Vote: I like it +2 Vote: I do not like it
I think that in solution of Div2 A it should be "if n mod i = 0" instead of "if i mod 2 = 0" :)
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it
For E, shouldn't it say:

"Subtract(l, r, d) - subtract number  d from all  D i"
"Minimum(l, r)  < 0, let j = Left(l, r), assign  D j new value" - if you update those where  Minimum(l, r)  = 0, then the Count queries will fail right?
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it
For Lucky Array (Div1 E) ,
How to implement Subtract(l, r, d) and Count(l, r) operations?
Segment_Tree?
Who can explain the solution in detail ?
  • 9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Yes, you can use segment tree. A lot f information is on e-maxx.ru/algo , but that is in Russian language. You can use Google to find about somthing like "Range modifications with segment tree".
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

include<stdio.h>

int main(){ int n ; scanf("%d" , &n); printf((n%4 && n%7 && n%47 && n%74 && n%477)?"NO":"YES"); return 0; }

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem 122A, A. Lucky Division, what is the meaning of evenly divided, because this has been accepting the answers for 49 as YES. I don't understand why it should be a YES?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because 49 is divided by 7

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, I do understand that, but what is the meaning of term evenly divided in the problem statement. I didn't understand the context of this word because 7 divides 49, 7 times which isn't even.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        "Evenly" means "exactly" here

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks for the Help, Mate. Noobie to this world. ^_^

»
21 month(s) ago, # |
Rev. 4   Vote: I like it +1 Vote: I do not like it

Lucky Array 121E — 72 testcases and still passes O(n*m*log(10^4)) :0 Code

  • »
    »
    10 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    It's actually faster than $$$O(n\cdot m\cdot log(n))$$$ because you only update the BIT when a number becomes or "unbecomes" lucky, this can only happen at most 60 times per number, so it's actually $$$O(n(m+60 \log n))$$$.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Still more than 4 sec. :D

      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        It's a perfectly valid solution, the heaviest part $$$O(nm)$$$ has a small constant because it's very simple and cache-friendly. I have just written a blog post about this, I believe people will find it useful.

      • »
        »
        »
        »
        7 weeks ago, # ^ |
        Rev. 2   Vote: I like it +5 Vote: I do not like it

        I have implemented the same code and it passed all test cases, and worst time was around 2 secs.

        Submission

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem (Div 2A), How 799 is YES? Here every digit is not 4 or 7 and also the number is not evenly divided by 4 or 7.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the logic behind 2C ? The editorial is very short and unclear.