maroonrk's blog

By maroonrk, history, 3 years ago, In English

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!

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

| Write comment?
»
3 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

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

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

Hope for a good contest.

I hope to become green in Atcoder.

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

Hope for a good contest!

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

Who's the problem setter of D?

(I'll knit his name on my death list.)

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

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?

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

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

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

    I got similar results before accounting for duplicate items.

»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Can someone please explain the dp part in the editorial for E?

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it
Code

Problem C

Can anyone tell whats wrong in this code..it is passing 72/73 test cases..What is that one case which it is failing at?

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

    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.

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

      https://atcoder.jp/contests/arc124/submissions/24552411

      Can 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?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it
        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
        
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How large would the number of divisors of a number be?

I used to assume it was at most $$$\sqrt n$$$.

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

    It's about $$$O(\sqrt[3]{n})$$$

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

      Could you explain how to achieve the $$$\mathcal{O}(N^{1/3})$$$ bound?

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

        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) = 6

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

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

        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 purposes

        n < 1e9 or 1e18

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

C with $$$n \leq 50$$$ and TL = 4 sec is the best trolling I ever seen

»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it
void solve()
{  
    ll n;
    cin>>n;
    vector<ll> a(n),b(n);
    ll x=0,y=0;
    for(ll i=0;i<n;i++)
    {
        cin>>a[i];
       
    }
    for(ll i=0;i<n;i++)
    {
        cin>>b[i];
       
    }
    
    unordered_map<ll , ll> mp;
    for(ll i=0;i<n;i++)
    {
        for(ll j=0;j<n;j++ )
        {
            mp[a[i]^b[j]]++;
        }
    }
   
    set<ll> s;
    
    for( auto i : mp)
    {  if(i.second>=n)
    {
        s.insert(i.first);
    }
    }
    cout<<s.size()<<endl;
    for( auto it=s.begin();it!=s.end();++it)
    {
        cout<<*it<<"\n";
    }
}

LINK Can somebody tell me which cases are missing using above approach in problem B? I got 38xAC and 3xWA

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

    Your code is not giving the correct answer for this test case —

    3 1 1 2 3 3 1

    Correct answer : 0

    Your Answer : 1,2

    I think your logic is flawed as you have not accounted for identical elements in the original array.

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

Applying std::random_shuffle 1000 times makes my fake solution to C pass...

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

I don't know if the time complexity of my algorithm is correct. Is there anyone can tell me?

#include<bits/stdc++.h>
#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<rhs.y:x<rhs.x;
	}
};

int a[maxn];
int b[maxn];
set<Node> 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<n; i++) {
		for(auto x:st[i]) {
			st[i+1].insert(Node(gcd(x.x,a[i+1]),gcd(x.y,b[i+1])));
			st[i+1].insert(Node(gcd(x.x,b[i+1]),gcd(x.y,a[i+1])));
		}
	}
	int ans=0;
	for(auto x:st[n]) {
		ans=max(ans,lcm(x.x,x.y));
	}
	cout<<ans;
}
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Can anyone explain dp part? That's the most important part in the editorial for E

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

In B-XOR Matching 2

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$$$

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

    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

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

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?

  • »
    »
    3 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    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

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

      Thanks!! I get it.

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

      Can u explain dp part in the editorial for E ?

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

        Were you able to find the dp for E? Please share if you could find it

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

          I do not have it. In the editorial for E, they just said to use dp to solve without explaining how to use dp ~~~~~

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

            In problem E we have to find the number of ways to select exactly 1 ball from each cell for all sequences C such that

            C(i)<=a(i) and min(C(1),C(2)....,C(n)) =0.
            

            Please note that we have to consider every ball different from while selecting but we have to consider them identical while transferring ( Since only number of balls transferred matters to us) .

            After performing the given operations let's say an index i contains x balls. Some of it (possibly 0) must be in index i-1 originallly. So when we are selecting a ball from this index we can either select a ball that was originally present in index i-1 or a ball that was originally present in ith position.

            We can find answer for sequences C such that min(C)=0 by finding Count(Minimum in C is atleast 0)- Count (Minimum in C is atleast 1)

            We will write a dp(i,j,k) where,
            i represents index of the current position 
            
            j represents whether the ball that we selected for the first place was originally at first place or last place 
            
            k represents whether the ball that we will select for ith place came from i-1th position or ith position. 
            

            For position j, 0 represents that the ball we will select for 0th position was originally at 0th position and 1 represents that the ball we will select for 0th position was originally at last position.

            For dp(i,j,k) there are 2 transitions dp(i+1,j,0) and dp(i+1,j,1).

            If k==0 this means the ball we are going to select for position i was originally in place i and if we are going to transition to dp(i+1,j,0) that means the ball that we are going to select for position i+1 was originally in position i+1. So we don't have to worry about it. Now number of ways to select a ball for this position A(i)-C(i). Since we have to consider every C(i) we can add A(i)-0+A(i)-1+A(i)-2.......... which will result in an Arithmetic Progression.

            Similary we can count for each transition very easily.

            Final answer that we will return is dp[n][1][1]+dp[n][0][0]. dp[n][0][1] is a wasted state because we initially assumed that the ball that we are selecting for position 0 was originally at position 0. But dp[n][0][1] represents the number of ways such that the ball that we are selecting for position n was intially at position n-1 which contradicts our original assumption.

            The final answer will be FIND_ANSWER(0)-FIND_ANSWER(1). where FIND_ANSWER(m) gives answer for all sequences C such that minimum in C is atleast m.

            You can refer to semiexp's code for help.

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

              Thank you for your help

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

              can you explain more about dp transform

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

                The main problem in writing dp for this probem was the circular nature of array. Since the last element will have an effect on first one and the first one will have a effect on last one as well. So we will initially assume what the last position will be doing. If j=0 then it means the ball selected for position 0 was initially present in 0 else if j=1 then it means the ball selected for position 0 was initially present in 1

                For each i and j there are four possible transition :-

                dp[i][j][0]-> dp[i+1][j][0]
                dp[i][j][0]->dp[i+1][j][1]
                dp[i][j][1]->dp[i+1][j][0]
                dp[i][j][1]->dp[i+1][j][1]
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 years ago, # ^ |
                    Vote: I like it +5 Vote: I do not like it

                  I got it. Thank you very much for the clear explanation

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  14 months ago, # ^ |
                    Vote: I like it +5 Vote: I do not like it

                  thank youu very muchh !!!

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

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

»
3 years ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

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 Atcoder

clyring

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

    Why tag me

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

      Thought that you could have helped seeing the other comments on this page.

      Sorry for the tag. Removed it now.

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

    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.

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

      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.

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

I think Problem C — LCM of GCDs, lacks of perfect test cases.

This is my submission:

#include<bits/stdc++.h>
using namespace std;

#define LL long long
#define LD long double

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    LL t=1,n,a,b,c,d,e,f,ac,bd,ad,bc;
    while(t--)
    {
        cin>>n;
        LL arr[n];
        LL brr[n];
        for(LL i=0; i<n; i++) cin>>arr[i]>>brr[i];

        a=arr[0];
        b=brr[0];

        for(LL i=1; i<n; i++)
        {
            c=arr[i];
            d=brr[i];
            ac=__gcd(a,c);
            bd=__gcd(b,d);
            ad=__gcd(a,d);
            bc=__gcd(b,c);

            if(ac*bd/__gcd(ac,bd)>ad*bc/__gcd(ad,bc))
            {
                a=__gcd(a,c);
                b=__gcd(b,d);
            }
            else
            {
                a=__gcd(a,d);
                b=__gcd(b,c);
            }
        }

        e=a*b/__gcd(a,b);

        a=arr[n-1];
        b=brr[n-1];

        for(LL i=1; i<n; i++)
        {
            c=arr[n-1-i];
            d=brr[n-1-i];
            ac=__gcd(a,c);
            bd=__gcd(b,d);
            ad=__gcd(a,d);
            bc=__gcd(b,c);

            if(ac*bd/__gcd(ac,bd)>ad*bc/__gcd(ad,bc))
            {
                a=__gcd(a,c);
                b=__gcd(b,d);
            }
            else
            {
                a=__gcd(a,d);
                b=__gcd(b,c);
            }
        }

        f=a*b/__gcd(a,b);

        cout<<max(e,f)<<"\n";
    }

    return 0;
}

For the following test case, my solution is supposed to get WA.

5

3 2

1 6

1 2

1 6

3 2

My output is 1 where the answer should be 2.