Блог пользователя chokudai

Автор chokudai, история, 2 года назад, По-английски

We will hold AtCoder Beginner Contest 254.

The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation!

  • Проголосовать: нравится
  • +75
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Thanks to the authors for the contest. I really liked thinking about problem F(although I couldn't solve it during the contest but will definitely upsolve it).

»
2 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Is the judger down now?

»
2 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

What is the edge case in F I did this let D1[i] = A[i+1]-A[i] , D2[i] = B[i+1]-B[i] ans = gcd(range_gcd_ofD1(h1,h2-1),range_gcd_ofD2(w1,w2-1),A[h1]+B[w1]);

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Editorial of D

What is "square divisor of an integer N"?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    A divisor which is a perfect square , if N = 2^3 * 3^2 * 5*7 then f(N) = 2^2 * 3^2 * 5^6

»
2 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

I solved F in 16 minutes and D in an hour. I must be stupid...

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For D, you can find for each 1<=i<=N, the minimum number j, such that i*j = square number, then count all multiples of j such that the multiple 'x' = j*k, where k is a perfect square. Submission

»
2 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

I have no idea why My submission got WA,it passed the samples local.

»
2 года назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

.

»
2 года назад, # |
Rev. 2   Проголосовать: нравится -12 Проголосовать: не нравится
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain D more clearly ?? I am not able to understand it !!?

»
2 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

My review on the contest :

Problem A : Easy ace, basic case handelling or strings
Problem B : Easy, can be brute forced or calculated by nCr formula (as it is the pascal triangle)
Problem C : Easy, basic greedy Algorithms
Problem D : Moderate, first time spending lots of time in abc D, but one of the coolest problems
Problem E : Somewhat tricky, but very obvious and standard
Problem F : Hard, cool problem, I got the solution in contest but failed to implement fast due to wasting time on D and quite some on E, but nonetheless one of the coolest problems
Problem G : Did not read
Problem Ex : I read it but no ideas so far, didn't think that much about it yet

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Not to complain or anything but I just don't get Problem D... I tried hard but still won't get into my brain.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    I solved it after contest, I think a person should solve it by themselves, because the editorial is very unclear, so I should have understand it by myself

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Imagine there are 3 numbers: 5, 20, 180. How many pairs of these numbers when multiplied becomes a square number?

    Here, we should reduce 5 to 5, reduce 20 to 5 (by 4, which is a square number) and reduce 180 to 5 (by 36, which is also a square number).

    Now, since there are three counts of 5, the answer is 3*3 = 9. The 9 pairs are: (5,5), (5,20), (5,180), (20,20), (20,5), (20,180), (180,5), (180,20), (180,180).

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I solved D in contest by using brute force to enumerate through all the possible pairs and try to find out its pattern. I found that I just need to put all prime divisors that occur an odd number of times together and then check all of its squares which is a multiple of it. It works perfectly!

    Anyways, the problem is pretty good, need some observation. I think every time when you come through an optimization problem, consider brute forcing first and try to find out how it works.

»
2 года назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

Nice Contest !
I spend lot's of time to solve problem G, but failed. Sharing another's way to solve problem Ex while using two map (or multiset). (link: https://atcoder.jp/contests/abc254/submissions/32236618)
Key point : Everytime to check both array's max element compared equal. If equal, then remove them, otherwise to make max_element divided by two.

»
2 года назад, # |
Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

D can be solved in $$$O(n)$$$ .

my solution

(I think that D can be solved in $$$O(\sqrt n)$$$)

UPD: $$$O(\sqrt n)$$$ solution: link

  • »
    »
    2 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

    The answer is

    $$$\displaystyle f(n)=\sum_k\left\lfloor\sqrt{\dfrac nk}\right\rfloor^2$$$

    when k does not exceeding n and k is a square-free number.

    • »
      »
      »
      2 года назад, # ^ |
      Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

      A grammar mistake: when k not exceeding n -> when k doesn't exceed n.

      btw ,what you've achieved is a beautiful expression !

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Just curious, did you find this expression by looking up for 1,2,3,6,7,8,9,12,17 in OEIS?

»
2 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Really enjoy this contest.

I spent 40 minutes on problem D, which is longer than I expected. This is a cool problem, and finally I used the "classic idea": fix i and count the number of j which satisfies the conditions.

Porblem E is about bfs, and after some simple calculation, we could see that the complexity is in fact bounded.

I have about 35 minutes left for problem F. It is until less than 10 minutes that I realized I should take advantage of gcd(x,y)=gcd(x-y,y), which could reduce the original problem to two independent queries of array A and B. It is a pity that I didn't finish coding before contest ends.

I learned a lot from this contest. My basic knowledge is still not solid, and I must practice more so that I could have more ideas when meeting a new problem, and find out the correct solution as soon as possible. Thanks to the writers and testers for providing such an educational contest.

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Problem D and F are typical for me. Solved Problem A~F in 30minutes this time. :p

    Problem Ex is educational for me. I learnt more about trie.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I think it won't be a long time before you reach red.

      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Still a long way to go... Now I can implement easy problems fast but have no idea when I meet hard problems like maybe difficulty>=2100 problems in AtCoder.

        Next I will try to get to 'Master' on Codeforces, but I don't have much time to compete because of the time zone, though.​

»
2 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Does anyone notice the gap between F and G?

»
2 года назад, # |
Rev. 3   Проголосовать: нравится -19 Проголосовать: не нравится

APPROACH TO PROBLEM D IN MY OWN WORDS, EVERY NUMBER CAN BE SPLIT AS A MULTIPLICATION OF PRIME NUMBERS (PRIME DIVISORS). ANY NUMBER CAN BE REPRESENTED AS 2^A * 3^B * 5^C AND SO ON.

TO BECOME A SQUARE NUMBER A, B, AND C AND OTHER POWERS SHOULD BE EVEN. WE NEED TO FIND PAIRS (X, Y) WHERE 1 <= X, Y <= N, RESULT OF X * Y = Z(SAY), Z SHOULD HAVE POWERS OF ITS PRIME DIVISORS EVEN TO BECOME A PERFECT SQUARE NUMBER.

LET X = 2^A*3^B*5^C... , Y = 2^a*3^b*5^c... AND X * Y = Z = 2^(A + a)*3^(B + b)*5^(C + c)... HERE (A + a), (B + b), AND (C + c) SHOULD BE EVEN TO BECOME A PERFECT SQUARE.

SO TO FIND THIS WE JUST TAKE THE MODULO OF EVERY POWER BY 2 AND IF IT IS ZERO THEN THAT PRIME DIVISOR IS NOT A PROBLEM FOR BECOMING IN PERFECT SQUARE, ELSE IF IT IS 1 THEN WE NEED ANOTHER NUMBER THAT HAS THE SAME PRIME DIVISOR WITH ODD POWER AND THEN IF WE MULTIPLY THEM TOGETHER WE CAN HAVE PRIME DIVISOR WITH EVEN POWER WHICH MAKES NUMBER A PERFECT SQUARE.

SO TO SOLVE THIS PROBLEM WE MAKE BUCKETS THAT WILL HELP US COUNT HOW MANY NUMBERS HAVE THE SAME ODD POWERS OF PRIME DIVISORS AND IF WE MULTIPLY THEM TOGETHER WE WILL GET EVEN POWERS OF PRIME DIVISORS AND WE WILL HAVE A PERFECT SQUARE.

EXAMPLE. BUCKET[1] ==> ANY NUMBER WHICH IS ALREADY A PERFECT SQUARE. BUCKET[2] ==> ANY NUMBER WHICH HAS ODD POWERS OF 2 IN ITS PRIME FACTORIZATION. 2^A*3^B*5^C..., HERE A IS ODD OTHERS ARE EVEN. BUCKET[3] ==> ANY NUMBER WHICH HAS ODD POWERS OF 3 IN ITS PRIME FACTORIZATION. 2^A*3^B*5^C..., HERE B IS ODD OTHERS ARE EVEN. BUCKET[4] ==> WILL BE ZERO AS IT IS ALREADY A SQUARE NUMBER(CAN’T BE REPRESENTED BY ODD POWERS OF PRIMES) BUCKET[5] ==> ANY NUMBER WHICH HAS ODD POWERS OF 5 IN ITS PRIME FACTORIZATION. 2^A*3^B*5^C..., HERE C IS ODD OTHERS ARE EVEN. BUCKET[6] ==> ANY NUMBER WHICH HAS ODD POWERS OF 2 AND 3 IN ITS PRIME FACTORIZATION. 2A*3B*5C..., HERE A AND B ARE ODD OTHERS ARE EVEN. 8 WILL GO IN BUCKET OF [2] AS IT HAS ONLY ONE ODD POWER OF 2(3 % 2 = 1).

WHEN WE MULTIPLY (COUNT[BUCKET NUMBER] * COUNT[BUCKET NUMBER] (PERMUTATION FOR COUNT 3 WE HAVE 3 CHOICES FOR X AND 3 CHOICES FOR Y TO MAKE UP A NUMBER SO THE RESULT FOR SUCH BUCKET WOULD BE 3 * 3 = 9)) COUNT OF EVERY BUCKET WE WILL GET A RESULT WHICH IS PAIRS OF (X, Y) WHERE 1 <= X, Y <= N.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Anyone elaborate how greedy works in problem Ex?

In jiangly's solution, why should we sort f[0] and f[1] from large to small, match the large elements and recursively operate on the smaller ones? have no idea how to prove it.

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    Not sure how to rigorously prove it, but here's a bit of handwaiving:

    $$$p$$$ groups values from $$$a$$$ and $$$b$$$ by their common prefix $$$v$$$ in binary notation, encoding them by only storing the number of trailing $$$0$$$s in $$$f[0]$$$ for $$$a$$$ and $$$f[1]$$$ for $$$b$$$.

    To match one $$$a_i$$$ to one $$$b_j$$$ it must have the same prefix $$$v$$$ and the same number of trailing zeroes.

    Assuming $$$f[0]$$$ and $$$f[1]$$$ have the same length, we still have to add or remove zeros from those $$$a_i$$$s, that is we have to increase or decrease values in $$$f[0]$$$ so that $$$f[0]$$$ and $$$f[1]$$$ end up with the same multiset of values. If you experiment a bit it's easy to see that sorting is beneficial.

    (Example: $$$[1, 3] \rightarrow [2, 4]$$$ costs $$$2$$$ operations, but $$$[3, 1] \rightarrow [2, 4]$$$ costs $$$4$$$)

    If $$$f[0]$$$ is shorter: We can't match all $$$f[1]$$$. We also can't get some from another $$$v$$$-group as we can not add trailing $$$1$$$s to a $$$v$$$, we can only remove them, but we process prefixes $$$v$$$ in descending order, so there aren't any left that can result in $$$v$$$ when removing a $$$1$$$.

    If $$$f[0]$$$ is larger: We can move an $$$a_i$$$ to another prefix group $$$v'$$$ by dividing until all trailing zeros have been removed and the first trailing $$$1$$$ of the prefix $$$v$$$. It seems like a good idea to do this with values that already have less trailing zeros.

    Example: Assume we have $$$f[0]=[5,3,1]$$$ and $$$f[1]=[4]$$$:

    • drop $$$3$$$ and $$$1$$$ (cost $$$4+2=6$$$), match $$$[5]$$$ with $$$[4]$$$ (cost $$$1$$$) $$$\rightarrow$$$ total cost: $$$7$$$
    • drop $$$5$$$ and $$$1$$$ (cost $$$6+2=8$$$), match $$$[3]$$$ with $$$[4]$$$ (cost $$$1$$$) $$$\rightarrow$$$ total cost: $$$9$$$
    • drop $$$5$$$ and $$$3$$$ (cost $$$6+4=10$$$), match $$$[1]$$$ with $$$[4]$$$ (cost $$$3$$$) $$$\rightarrow$$$ total cost: $$$13$$$

    I basically had the same idea when I upsolved Ex, but my implementation is not as nice.

    (I also implemented a solution based on the trie-idea after reading the editorial.)

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I have a (probably) compact proof for this.

    Obviously, if $$$f[0][k]\ne f[1][k]$$$, where $$$f[0][k]$$$ and $$$f[1][k]$$$ are the largest elements, we should divide the larger one by $$$2$$$ because we will have to do it eventually to match every element.

    Now we only need to prove that we should delete them when $$$f[0][k]=f[1][k]$$$. If we don't do this, say we choose $$$i$$$ and $$$j$$$ and match $$$f[0][k]$$$ with $$$f[1][i]$$$ and $$$f[1][k]$$$ with $$$f[1][j]$$$, then we will need $$$\log \frac{f[0][k]}{f[1][i]}+\log \frac{f[1][k]}{f[0][j]}$$$, which is obviously worse than $$$\log \frac{f[1][i]}{f[1][j]}$$$.

    And by replacing $$$i$$$ and $$$j$$$ with further elements that they originally match, we get the same result with a similar process. Then the proof is completed.