74TrAkToR's blog

Codeforces Round #828 (Div. 3) Editorial
By 74TrAkToR, history, 18 months ago, In Russian

Спасибо за участие!

1744A - Number Replacement придумал MikeMirzayanov, подготовил 74TrAkToR

1744B - Even-Odd Increments придумал и подготовил 74TrAkToR

1744C - Traffic Light придумали MikeMirzayanov и 74TrAkToR, подготовил 74TrAkToR

1744D - Divisibility by 2^n придумал и подготовил 74TrAkToR

1744E2 - Divisible Numbers (hard version) придумал и подготовил 74TrAkToR

1744F - MEX vs MED придумал и подготовил 74TrAkToR

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +52
  • Vote: I do not like it

Comments Comments (21)
| Write comment?
»
18 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Nice Editorial, and very nice round!

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is so sad. If I knew that the max number of divisors in a number < 1e9 is 1344 I for sure could have finished question E2 because I had the same idea is the editorial. :(((

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

    I didn't knew that but the solution made sense and I didn't have any other idea so I just assumed it. If it would have failed, it would have failed. What I'm saying is sometimes you have to go with your gut instead of proving whether the solution will work. Atleast that's what I think.

    → Reply
    • »
      »
      »
      18 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      That is true but I didn't really have any gut feeling that told me that the max number of divisors would be small. In fact my gut actually told me that the number of divisors of sum n could be as big as a constant fraction of sqrt(n). But ig i should have tried it anyways.

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

    You can argue that the logic wouldnt TLE without knowing the exact number as 1344. Since the number of divisors of n = 2^a 3^b 5^c ... is given by (a+1)*(b+1)*(c+1)..., we can get a very rough estimate for the upper bound of the number of divisors as

    max divisors = (log_2(10^9)+1) * (log_3(10^9)+1) * (log_5(10^9)+1) * ...
             = 33 * 20 * 13 * 9 * ...
             < 10^5
    → Reply
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Wait I don't understand your logic for calculating upper bound of max number of divisors. Also 1e5 is too big for an n^2 algorithm isn't it?

      → Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Since x⋅y must be divisible by a⋅b, the following conclusion can be drawn: y must be divisible by a⋅b/gcd(a⋅b,x)

Can anyone please prove this how in the problem E.

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

    This is not something that you "prove". It is something that you intuitively know. When you unpack this statement it doesn't actually say much but the math makes it kind of convoluted so I'll explain it. To have some x*y be divisible by a*b, the set of prime divisors in a*b should be a subset of prime divisors in x*y. In other words, for every prime divisor in a*b, that prime divisor should also exist in x*y. Now if you think about it, gcd(a*b, x) simply means the set of prime divisors in x, which are also prime divisors in a*b. This means that the y that you choose only has to contain the prime divisors that is in a*b but not in x. This is given by the expression u gave ((x*y)/gcd(a*b, x)).

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

      Had same doubt.Thanks for explaining.

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

      how does it mean that gcd(a*b , x) means the set of prime divisors of which are also prime divisors in a*b

      → Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    Both x and y should together make up a*b
=> so x should have some part of a and some part of b. 
=> so y should have some part of a and some part of b.

    This some part which is I mentioned above is nothing but "factor of a given number"
Now x and y can be written as
x = afact1 * bfact1 * k
y = afact2 * bfact2 * k

    Here k is some constant, afact1 and afact2 is factorials of a, bfact1 and bfact2 are factorials
of b and also note that a = afact1 * afact2 = a, b = bfact1*bfact2

    so fix afact1 and bfact1 we get afact2 = a/afact1 and bfact2 = b/bfact1
    → Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The Editorial didn't add to Contest materials and lots of ppl don't know that it comes

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice Editorial,thanks.

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone know how so many solution for E were being hacked? What did the test case contain?

→ Reply
»
18 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Some please explain F

→ Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone please explain why this code is not working? This is the code for Problem D.

178113368

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

    Hi, your solution is almost correct... When choosing which indices to apply the operation on, you went from N to 1, but a bigger number doesn't necessarily mean a bigger number of twos. Take for example 5(0) and 4(2). So instead of going from N to 1, you should sort the indices by their number of twos and go from the biggest to the smallest. Hope this helps <3

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

I have a better time complexity solution for E, which works in O(sqrt(a) + 1344 * log(1344)).

I have no idea why this works. Can somebody please help? https://codeforces.com/contest/1744/submission/186708442

The code iterates through all factors of a (say p) and finds the largest factor of b (say q) such that x = a * q / p and y = b * p / q. Then it takes the multiple of x just smaller or equal to c and the same for y. The code then swaps the numbers and does it again.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

2333 But I'm a Chinese primary student.

→ Reply