witua's blog

By witua, 13 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 di = 4 and di + 1 = 7 and di - 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 si, si = si - 1 + (Ai - Ai - 1) * ci. 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, Lj + Ri ≤ k, Luckyj - Luckyi + 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 Ai always is  ≤ 10000. Let Di - difference between minimum lucky number which is greater than or equal to Ai and Ai. 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 Ai (l ≤ i ≤ r), Minimum(l, r) - minumum number of all Di (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 Di (Di = 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 Di might be less than 0. So, while, Minimum(l, r)  ≤ 0, let j = Left(l, r), assign Dj new value (use Set(j, Dj')), 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

| Write comment?
13 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" :)
13 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 Di"
"Minimum(l, r)  < 0, let j = Left(l, r), assign Dj new value" - if you update those where Minimum(l, r)  = 0, then the Count queries will fail right?
13 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 ?
  • 13 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".
    • 5 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      How is the TC of this step "while, Min(l,r) < 0, Set(j, Dj)" under Log(n) and overall TC of add/count operations m*Log(n)?

      Entire sub-array might become < 0 after an add operation and this can happen for multiple/many add operations.

»
6 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?

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

    Because 49 is divided by 7

    • »
      »
      »
      6 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.

»
6 years 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

  • »
    »
    5 years 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))$$$.

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

      Still more than 4 sec. :D

      • »
        »
        »
        »
        5 years 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.

      • »
        »
        »
        »
        4 years 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

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

IN problem Div1(A) or Div2(c) how to create those lucky numbers from 1 to 10^10?

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

    For each length of number L, the are only 2^L possible lucky numbers (since there are 2 possibilities for each digit: 4 or 7).

    Generate instead all possible bitmasks of length L (for L = 1 to 10), and replace 0s with 4s, 1s with 7s. Note that you need to include bitmasks with leading zeros.

    Python implementation: https://paste2.org/YfMYvaXe

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

Test Case 26: Input is 799 and output should be "NO" but the answer is "YES", can anyone explain?

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

    Yesh because 799 % 47 == 0 and 47 is lucky number