### maroonrk's blog

By maroonrk, history, 2 months ago,

We will hold AtCoder Regular Contest 124.

The point values will be 300-400-500-700-800-900.

We are looking forward to your participation!

• +87

 » 2 months ago, # | ← Rev. 2 →   +6 I have a question. That is if I register for a contest and I don't participate in that contest(don't submit anything). is it impacts my rating? (the question is for both codeforces and atcoder).
•  » » 2 months ago, # ^ |   0 No.
 » 2 months ago, # |   0 Hope for a good contest.I hope to become green in Atcoder.
•  » » 4 weeks ago, # ^ |   0 Good luck bro!
 » 2 months ago, # |   0 Hope for a good contest!
 » 2 months ago, # |   +2 Who's the problem setter of D?(I'll knit his name on my death list.)
 » 2 months ago, # | ← Rev. 2 →   0 Why does using set gets TLE submission while simple sort works submission .Are sets slower? also, which 1 test case does this(C) fail on?
•  » » 2 months ago, # ^ |   0 Hey, do you mind explaining your approach to B ?
•  » » 7 weeks ago, # ^ |   0 Your C fails probably bc of int32 overflow of LCM. Btw LCM is usually calculated as a/gcd(a, b)*b for this reason but in this case only long long should help.
•  » » » 7 weeks ago, # ^ |   0 Thanks for the reply but I have used long long(#define int long long). The problem with my C is in the approach itself as pointed out in this comment https://codeforces.cc/blog/entry/93165?#comment-820716
 » 2 months ago, # |   0 https://atcoder.jp/contests/arc124/submissions/24542794 Can anyone help me find what's wrong in my solution in problem B? It is passing 34 cases but failing in 7
•  » » 2 months ago, # ^ |   +3 I got similar results before accounting for duplicate items.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 I think I did account for duplicate items.Can you please check my code what's wrong?
•  » » » » 2 months ago, # ^ |   0 Sorry, getting ready to die in global round.If it turns out to be a coincidence matching the number of WA results, sorry for the distraction!fwiw, I remember getting funny stuff from: 3 2 2 1 2 2 1 
 » 2 months ago, # |   +17 Can someone please explain the dp part in the editorial for E?
 » 2 months ago, # |   +8 Codeint n; cin>>n; int a[n+1][2]; a[0][0]=0;a[0][1]=0; for(int i=1;i<=n;i++) cin>>a[i][0]>>a[i][1]; int dp[n+1][2]; dp[0][0]=0;dp[0][1]=0; for(int i=1;i<=n;i++) { int x=gcd(dp[i-1][0],a[i][0])*gcd(dp[i-1][1],a[i][1]); int y=gcd(dp[i-1][0],a[i][1])*gcd(dp[i-1][1],a[i][0]); if(x>y) { dp[i][0]=gcd(dp[i-1][0],a[i][0]); dp[i][1]=gcd(dp[i-1][1],a[i][1]); } else { dp[i][0]=gcd(dp[i-1][0],a[i][1]); dp[i][1]=gcd(dp[i-1][1],a[i][0]); } } cout<
•  » » 2 months ago, # ^ |   0 It's a greedy strategy... it will make locally "correct", but globally wrong choices. Example: 3 3 2 1 6 1 2 The correct output is 2. Your program tries to save a common factor of 3 after the first two packs, but this dooms it to a worse final result. The test data was probably not very good if this approach was able to pass 72/73 test cases.
•  » » » 2 months ago, # ^ |   0 https://atcoder.jp/contests/arc124/submissions/24552411Can you please check this one out what's wrong here? It passes 72/73 cases as well.Brief explanation : I am storing all those primes that are divisors of all pairs' at least one number and updating answer for all permutations of those primes. According to the order of primes in each permutation, I am adding a number to the red bag if it has a prime divisor whose exponent is greater than the other pair member. Is there anything wrong with my logic or do I have a bug?
•  » » » » 2 months ago, # ^ |   +3 3 2 12 18 3 2 3 Correct output is 6. Your output is 3. Also, as you may realize, it would TLE on this input, since there are too many relevant primes: 1 58642669 223092870 
 » 2 months ago, # |   0 How large would the number of divisors of a number be?I used to assume it was at most $\sqrt n$.
•  » » 2 months ago, # ^ |   +6 It's about $O(\sqrt[3]{n})$
•  » » » 2 months ago, # ^ |   +11 Could you explain how to achieve the $\mathcal{O}(N^{1/3})$ bound?
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   +5 There's actually an exact formula. Number of divisors equals to the multiple of [power degrees of prime factors of the number + 1];12 = 2^2 * 3^1 — > d(12) = (2+1)*(1+1) = 6I suppose it can be proven that the maximum number of divisors will have numbers which have each prime multiplied exactly once (2*3*5*7...). The maximum number which we can get like that and won't exceed 10^9 consists of 10 primes so its number of divisors will be 2^10.
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 I think I had read somewhere that the number of divisors of a number n can be shown to be asymptotically less than n^eps where eps > 0, for all n > some N.Therefore, I guess if we are truly exact then we are talking of a kind of "polynomial" of arbitrarily small degree. Maybe that would be kind of logn or (logn)^2 etc ( as it a function which grows slower than n^eps where eps > 0)Anyway, I think the n^(1/3) bound isn't really a "real" tight bound. Instead, its just probably the best bound which works when dealing with numbers that are in the range we deal with, for our purposesn < 1e9 or 1e18
 » 2 months ago, # |   +9 C with $n \leq 50$ and TL = 4 sec is the best trolling I ever seen
 » 2 months ago, # |   -8 void solve() { ll n; cin>>n; vector a(n),b(n); ll x=0,y=0; for(ll i=0;i>a[i]; } for(ll i=0;i>b[i]; } unordered_map mp; for(ll i=0;i s; for( auto i : mp) { if(i.second>=n) { s.insert(i.first); } } cout<
•  » » 2 months ago, # ^ |   0 Your code is not giving the correct answer for this test case — 3 1 1 2 3 3 1Correct answer : 0Your Answer : 1,2I think your logic is flawed as you have not accounted for identical elements in the original array.
•  » » 2 months ago, # ^ |   0 I think u should also use map since values were around 2^30 and maps are better to pass test cases where collision might occur but still I think that can be fixed in case of unordered maps and also u have used a nested loop to calculate the candidates for x , i.e the same xor value, u could have done in a single loop a[0]^b[j] , j running from 0 to n( since a[0]^b[0]=a[1]^b[1] ....)my code
•  » » 2 months ago, # ^ |   0 instead of vector use set to take input of a,b. and for checking count of map of XORs use min(a.size(),b.size()). my submission
 » 2 months ago, # |   0 what is the logic in A can anyone explain plz!
 » 2 months ago, # |   0 C can be solved by using randomized algorithm: https://atcoder.jp/contests/arc124/submissions/24542820
•  » » 2 months ago, # ^ |   +3 This only works because the test data for C is pretty weak. Here's a small, easy-to-construct input on which it will fail 100% of the time: 3 3 10 5 14 7 6 
•  » » » 6 weeks ago, # ^ |   0 Yeah luckily, there isn't a hacking round at Atcoder. I hope the admin can allow it. But how can you come up with the idea though?
•  » » » » 6 weeks ago, # ^ |   0 My thought process was something like this: SpoilerI figured it was easiest to reason about the second choice that a greedy strategy makes in each permutation, since the first choice doesn't really matter and a lot of stuff can affect the later choices. If I want every second choice to have a chance to be a mistake, there needs to be only one real optimal configuration. Easy enough: I can start with (1,2), (1,2), (1,2), with as many as I end up needing. Then I can build traps freely with odd primes, so long as no odd prime appears on every card.Then, for each set of two cards, I can insert a fresh odd prime on only those 2 cards to bait the greedy strategy into losing the factor of 2 if those are the first two cards. You can see the result.
 » 2 months ago, # |   0 Applying std::random_shuffle 1000 times makes my fake solution to C pass...
 » 2 months ago, # |   -8 I don't know if the time complexity of my algorithm is correct. Is there anyone can tell me? `#include #define int long long using namespace std; const int maxn=55; const int inf=1ll<<60; int gcd(int x,int y) { return y==0?x:gcd(y,x%y); } int lcm(int x,int y) { return x/gcd(x,y)*y; } struct Node { int x,y; Node(int x=0,int y=0):x(x),y(y) {} bool operator < (const Node &rhs) const { return x==rhs.x?y st[maxn]; signed main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int n; cin>>n; for(int i=1; i<=n; i++) { cin>>a[i]>>b[i]; } st[0].insert(Node(0,0)); for(int i=0; i
 » 2 months ago, # |   +9 Can anyone explain dp part? That's the most important part in the editorial for E
 » 2 months ago, # | ← Rev. 2 →   0 Why is it sufficient for checking for only n distinct values of X. Shouldn't it be $n^2$ for different values across a^b where a , b = arrays(a,b) which could be at max $n^2$
•  » » 2 months ago, # ^ |   +5 Think it in this way that a[0] can map with b[0] to ..... b[n-1] so we will have n different values of xor (a[0]^b[k]) and hence we need to check for only n possible values because the xor for every pair in each matching needs to be same Here is my submission
 » 2 months ago, # |   0 Can someone explain how to get the formula $f(n) = g(n) - 2 \sum^{n-1}_{0} g(i)C(n-i-1)$ in problem F?
•  » » 7 weeks ago, # ^ | ← Rev. 4 →   0 To get $f(n)$ you need to subtract from $g(n)$ all the cases where they met before $n$. Suppose the LAST time they met before meeting again at $n$ is after moving right $i$ times.Then, both of the animals should move $n - i$ times right. During this phase the camel should always be strictly faster than the cat (or vice versa). This is known to be $C(n -i - 1)$. See the lattice paths interpretation of Catalan number: catalan
•  » » » 7 weeks ago, # ^ |   0 Thanks!! I get it.
•  » » » 6 weeks ago, # ^ |   0 Can u explain dp part in the editorial for E ?
•  » » » » 4 weeks ago, # ^ |   +3 Were you able to find the dp for E? Please share if you could find it
•  » » » » » 4 weeks ago, # ^ |   0 I do not have it. In the editorial for E, they just said to use dp to solve without explaining how to use dp ~~~~~
 » 5 weeks ago, # | ← Rev. 2 →   0 I am getting WA in problem B in three testcases.After so much trying i still cant figure out whats wrong .Please help me out.Here is my Submission
•  » » 5 weeks ago, # ^ |   0 remove duplicate numbers in rslt
 » 4 weeks ago, # | ← Rev. 2 →   -8 Can someone explain, how did we prove that N+M-K+2*max(R,B) is the minimum(for problem D: Yet Another Sorting Problem) from the below argument: Argument from the official editorial on AtcoderHere, it is possible to prove that f ( i ) ≤ f ( i + 1 ) holds where f ( i ) = i + N + M − K i + 2 max ( R i , B i ) . From this, we can state that we need at least N + M − K 0 + 2 max ( R 0 , B 0 ) operations.clyring
•  » » 4 weeks ago, # ^ |   0 Why tag me
•  » » » 4 weeks ago, # ^ |   +8 Thought that you could have helped seeing the other comments on this page. Sorry for the tag. Removed it now.
•  » » 4 weeks ago, # ^ |   0 This proves a lower bound since if the original list is sorted after $j$ operations, then $f(j) = j+N+M-K_j + 2 \max(R_j,B_j) = j + N + M - (N + M) + 2 \max(0, 0) = j,$since there are exactly $N + M$ components each of size $1$ in that case. But since $f$ is increasing and obviously $j \geq 0$ it must further hold that $j = f(j) \geq f(0) = N+M-K_0+2 \max(R_0,B_0)$. The editorial then continues by describing a specific strategy that achieves this lower bound and must therefore be optimal.
•  » » » 4 weeks ago, # ^ |   0 Thanks for your reply.I might not have been clear with my doubt. The doubt was that how did the editorial claim that N+M-K+2*max(R,B) steps were needed at any point. After going through your comment, I went through the greedy strategy mentioned and it seems that the strategy helps to break open the the claim.Thanks again, clyring. If not for you I would have given up on this problem.For people who come later with the same confusion, the minimum steps can be rewritten as (N+M-(K-max(R,B))) + max(R,B). The second term max(R,B) is the number of steps required to join a pure red or pure blue component to another red/blue component(not necessarily pure). We do so because for swaps to occur a component must have both a red and blue node.By doing so, we decrease the number of components by max(R,B). Now, K(final)=K(initial)-max(R,B). And since in a single step we can decrease the number of components just by one we need at least N+M-K(final) steps to have the sorted array.