We will hold AtCoder Beginner Contest 254.
- Contest URL: https://atcoder.jp/contests/abc254
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20220604T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: PCTprobability, m_99
- Tester: Nyaan, kyopro_friends
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation!
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).
Personally, I found problem F quite interesting. I solved it using difference array and the Sparse Table.
Link to My Solution
Care to state the gcd properties you used?
Here
Is the judger down now?
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]);
I think it should be
range_gcd_D1(h1 - 1, h2 - 1)and same forD2. I did that, and also $$$N = 1$$$ is an edge case.Submission
I used 1 based index so it will work for h1 to h2-1 , also I took Care of Special Case . The Blunder I did was In the macro I defined ll as unsigned long long int instead of long long int while solving a problem yesterday and did not change it back and it made lose point and ranks despite writing the code correctly. Thanks anyways.
Editorial of D
What is "square divisor of an integer N"?
A divisor which is a perfect square , if N = 2^3 * 3^2 * 5*7 then f(N) = 2^2 * 3^2 * 5^6
I solved F in 16 minutes and D in an hour. I must be stupid...
D is a great problem
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
That's a great solution! Thanks for sharing.
I have no idea why My submission got WA,it passed the samples local.
Your submission gives wrong answer on second sample.
But it's correct on my laptop
I have no idea.
WA
AC
They are actually SAME, but there's only a little difference.
.
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
Based on one of your old comments, I fixed your link:
https://atcoder.jp/contests/abc254/submissions?f.Task=&f.LanguageName=&f.Status=&f.User=hit7sh
Thanks!
Can someone explain D more clearly ?? I am not able to understand it !!?
Better explanation : https://www.geeksforgeeks.org/count-of-pairs-in-an-array-whose-product-is-a-perfect-square/
This helped a lot tyty
Thanks. Just need to change the final answer from
(f*(f-1))/2to(f*f).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
Not to complain or anything but I just don't get Problem D... I tried hard but still won't get into my brain.
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
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).
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.
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.
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
The answer is
when k does not exceeding n and k is a square-free number.
A grammar mistake: when k not exceeding n -> when k doesn't exceed n.
btw ,what you've achieved is a beautiful expression !
fixed.
(BTW, the $$$O(\sqrt n)$$$ solution is added.)
Just curious, did you find this expression by looking up for 1,2,3,6,7,8,9,12,17 in OEIS?
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.
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.
I think it won't be a long time before you reach red.
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.
Does anyone notice the gap between F and G?
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.
Why are you screaming?
Anyone elaborate how greedy works in problem Ex?
In jiangly's solution, why should we sort
f[0]andf[1]from large to small, match the large elements and recursively operate on the smaller ones? have no idea how to prove 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]$$$:
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.)
Thank you, sir. This simple example just enlightens me.
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.