chokudai's blog

AtCoder Beginner Contest 254 Announcement
By chokudai, history, 3 years ago, In English

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!

  • Vote: I like it
  • +75
  • Vote: I do not like it

Comments Comments (48)
| Write comment?
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Is the judger down now?

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

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]);

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

Editorial of D

What is "square divisor of an integer N"?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

    → Reply
»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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

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

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

→ Reply
»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

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

    Your submission gives wrong answer on second sample.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      But it's correct on my laptop

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    I have no idea.

    WA

    AC

    They are actually SAME, but there's only a little difference.

    → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -12 Vote: I do not like it

Thanks for the contest. I loved Solving Problem D and F. https://atcoder.jp/contests/abc254/submissions?f.Task=&f.LanguageName=&f.Status=&f.User=hit7sh

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

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

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

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

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

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

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

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

    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.

    → Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +10 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 3   Vote: I like it +1 Vote: I do not like it

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

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

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

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

      → Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

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

    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.

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

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

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

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

        → Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Does anyone notice the gap between F and G?

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it -19 Vote: I do not like it

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.

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

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

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

    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.

    → Reply