maroonrk's blog

By maroonrk, history, 5 weeks ago, In English

We will hold AtCoder Regular Contest 107.

The point values will be 300 — 400 — 500 — 600 — 800 — 900.

We are looking forward to your participation!

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

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Auto comment: topic has been updated by maroonrk (previous revision, new revision, compare).

»
5 weeks ago, # |
Rev. 2   Vote: I like it +33 Vote: I do not like it

The contest starts in ~10 mins.

»
5 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Best of LUCK!!

»
5 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

Maths only round?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

MathCoder ew

»
5 weeks ago, # |
  Vote: I like it +30 Vote: I do not like it

Just counting and counting and still counting...

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    F is not counting anyway.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it -35 Vote: I do not like it

      F looks like greedy to me, but I lack confidence in implementing what I am thinking :D

»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

What's the solution of C?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The swappable rows and cols are independent of each other. Both build components. In each component there are factorial(componentSize) permutations. Multiply all of them.

    Which rows and cols are swappable can be found by brute force in O(n^3)

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I did the same. But idk why my 2nd sample was coming wrong.

      Can you take a look once? Submission

      Thank you :)

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I did the same thing, in sample test case 1 there were 1 swappable pair of rows and 2 swappable pair of columns, so how is the answer 12?

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

        for sample test case 1:

        3 13
        3 2 7
        4 8 9
        1 6 5
        

        Edges in column:

        1 -- 2
        1 -- 3
        

        which means there is only one component whose size is 3(1,2,3).

        Edges in row:

        1 -- 3
        

        which means there are 2 component, whose sizes are 2 (1,3) and 1(2).

        then the ans = fact[3] * fact[2] * fact[1] = 12.

        Reference soln: link

»
5 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

Honestly, math homework today felt a bit boring :/

»
5 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

good atCombinatory Regular contest.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

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

    For the columns, you count the number of connected components (I use a dsu for this). Do the same for the rows. Now count the number of permutations for each component. The answer is the product of all those numbers.

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

      I did the same thing. Instead of using dsu, I did BFS. But, my solution doesn't match output of sample 2.

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

      Oh shit, I just made a stupid bug in my code lol.

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

    Basically solve independently for rows and columns and multiply the answer for both of them.

    Make a network where i,j is connected if rows i and j can be exchanged. Now the answer is the multiplication of the factorial of the size of each connected component(since size! ways to arrange these components).

    Do the same for columns.

    Reference link — link

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

    Observe that switching rows has no effect on columns that you can switch, and vice versa. So now, the switching of rows and columns is independent of one another. Now we just need to find which rows we can switch ($$$O(n^3)$$$). The number of ways we could arrange these rows is $$$m!$$$ for each group of size $$$m$$$ that we can switch (By group I mean a set of rows that we can arrange in any order). We can find each of these groups with DSU. Do the same for columns, and multiply for your answer

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

how to solve D?

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

    For D use DP approach.

    Initially lets start with k ones. Now we have to make n-k further breakdowns to have n elements. Each breakdown will result in two numbers with values half of the breakdown element. (For eg, If we decide to break down 4 1/2 elements, we will have 8 1/4 elements)

    Now lets breakdown in descending order starting from 1. (ie break some 1's -> break some 1/2's ->break some 1/4's and so on)

    Its now a n^3 dp with states as the breakdowns left(to have total n elements in the array and we initially start with k elements) and the amount of the latest value elements we have after the breakdown in the last step. This could be reduced to n^2 by prefix sums.

    Reference solution — link

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

      A much simpler approach : Let $$$dp(N,K)$$$ be the number of multi sets with sum $$$k$$$ and size $$$N$$$ . You can recursively formulate $$$ dp(N,K) = dp(N,2*K) + dp(N-1,K-1) $$$.The first term $$$dp(N,2*K)$$$ is the case when you don't take 1 and so the sequence starts from $$$\frac{1}{2}$$$ so it is equivalent of taking sum to $$$ 2*k$$$ and let the sequence to start from 1,The other term ,$$$ dp(N-1,K-1) $$$ is the case when you have taken 1 in the multiset,so your sum reduces to $$$k-1$$$ and length to $$$N-1$$$ and you can still start from 1.

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

        Does sequence will never start from 1/4 or 1/8 or 1/16.......? or are they already included in dp(N,2*K) part? I didn't understand this part.

        Update: Got it. It will be included in dp(N,2*K) part. dp(N,2*K) will not only tell the sequence starting from 1/2 but also for all 1/2^i for i>=1. because we are iterating from backward. So dp(n,2*k) will contain dp(n,4*k) and so on... Here is my accepted submission.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          can you explain more about dp(N,2*K) how it is including 1/4 ,1/8....???

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

            dp[i][2*k]+= dp[i-1][2*k-1]+dp[i][4*k]. Similarly dp[i][4*k]+= dp[i-1][4*k-1]+dp[i][8*k] and so on. So dp[i][4*k] value denotes the number of sequences which starts from 4*j=1 => means 1/4. Similarly, dp[i][8*k] for sequence starting from 1/8. and so on.

            And dp[i][8*k] is included in dp[i][4*k] which is further included in dp[i][2*k] which is included in dp[i][k].

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        ll solve(ll idx,ll n,ll k){ if(n==0 && k==0)return 1; if(k>n)return 0; if(n<=0 || k<=0 || idx>=12)return 0; if(dp[idx][n][k]!=-1)return dp[idx][n][k]; ll ans=0; ans=solve(idx+1,n,k*2)+solve(idx,n-1,k-1); ans%=M; dp[idx][n][k]=ans; return ans; }

        I am doing the same thing which you have told but getting wrong answer.I have used idx which tells the power of 2(2^idx).Can you tell me why is it giving wrong answer on 2nd test case.

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve E ?

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

    Try to brute force the first 100 rows and columns,try to find the regular pattern.

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

      It is enough if we only find the first 4 rows and columns.

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

        But I think 100 is very safe.

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

          It is right, but always prepare for memory issues

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it -33 Vote: I do not like it

        Yes. By pigeonhole principle.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://atcoder.jp/contests/arc107/submissions/17758415 My solution to A. But I kept getting TLE. What other trick should I have used in implementation?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Did you notice the constraints? a <= 1e9. Isn't it obvious you got TLE? No tricks in implementation, rather you should have realized this TLE issue, and come up with some math solution that works in O(1).

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Observe that $$$a,b,c \geq 10^9$$$. It will definitely TLE. Try to think of reducing this sum (product??) with math.

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Am I the only person who just solve A,B,D,E? :)

»
5 weeks ago, # |
  Vote: I like it +39 Vote: I do not like it

rage quit after reading tutorial of E :(

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

How to solve B ???
I registered but did not submit any solution .. Will my rating effected by this contest ??

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

    For B rewrite the equation as $$$(A + B) - (C + D) = k$$$
    Loop through all possible values of $$$(A + B)$$$ and calculate how many pairs($$$1 <= a <= n$$$, $$$1 <= b <= n$$$) can form $$$(A + B)$$$ same for $$$(A + B) - k$$$ = $$$(C + D)$$$ and multiply the both
    Submission: Link

    And nothing will happen to your rating

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Who can give a rather elegant proof for E? (Or just case handling?)

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

    My proof contains a bit of cases but is overall quite clean.

    Let us show four facts (true for cells with indexes $$$\ge 5$$$):

    1) The configuration x x does not occur. This follows directly from the statement.

    2) The configuration 2 1 2 does not occur. Indeed, it would generate

    ? 0 0
    2 1 2
    

    but we have already established that 0 0 cannot occur.

    3) The configuration 1 2 1 does not occur. Indeed, it would generate

    ? 0 0
    1 2 1
    

    but we have already established that 0 0 cannot occur.

    4) The configuration 0 2 0 does not occur. Indeed, it would generate

    2 1 2
    0 2 0
    

    but we have already established that 2 1 2 cannot occur.

    Now that we have these four facts, consider three consecutive cells x y z. It holds $$$y\not= x$$$ and $$$y\not=z$$$.

    1. If $$$y=0$$$ then $$$y=mex(x, z)$$$.
    2. If $$$y=1$$$ then either $$$y=mex(x, z)$$$ or $$$x=z=2$$$ which is impossible.
    3. If $$$y=2$$$ then either $$$y=mex(x, z)$$$ or $$$x=z=0$$$ which is impossible or $$$x=z=1$$$ which is impossible.

    Thus we have proven that $$$y=mex(x,z)$$$. As a consequence (by induction on the indices) we get

    $$$ a(i,j)=mex(a(i,j-1), a(i-1, j)) = mex(a(i-1, j-2), a(i-1, j)) = a(i-1, j-1) \,.$$$

    Hence we have shown $$$a(i,j) = a(i-1,j-1)$$$ for any $$$i,j$$$ large enough ($$$i,j\ge 5$$$ should be enough).

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

      Unless I'm missing something, I think you just proved the inductive step: $$$a_{i,j-1} = a_{i-1,j-2} \implies a_{i,j} = a_{i-1,j-1}$$$, but you haven't proved the existence of a base case, like for example: $$$a_{5,5}=a_{4,4}$$$. Moreover, if we can prove this base case, we may use the same reasoning to prove $$$a_{5+i,5+j}=a_{4+i,4+j}$$$ in general, without any inductive step.

      Here is my hopefully-with-not-so-many-cases case analysis attempt:

      We'll use the main fact that (ignoring the first row and column) no 2 adjacent (with a common side) entries have the same value on them.

      Let's take an arbitrary 4x4 subrectangle that doesn't include the first row or column. We'll show that $$$x=y$$$.

          . . . .
          . . . .
          . . x z
          . . w y
      

      There are 2 cases:

      1. If $$$w \neq z$$$, then $$$x$$$ and $$$y$$$ (by the main fact) should be different from $$$w$$$ and $$$z$$$ and so they should be equal to each other (since there are 3 possible values) and we're done.
      2. If $$$w = z$$$, let's assume that $$$x \neq y$$$ to reach a contradiction. Let $$$a$$$, $$$b$$$ and $$$c$$$ be the 3 different values.
          . . . .
          . . . ?
          . . a b
          . ? b c
      

      By the main fact, the $$$?$$$ signs may be $$$a$$$ or $$$c$$$. There are 2 cases:

      • 2.a) Both $$$?$$$ signs are $$$c$$$. Then, by the main fact, we have two $$$b$$$ above:
          . . . .
          . . b c
          . b a b
          . c b c
      

      but $$$a = mex(b,b) = c$$$. Contradiction.

      • 2.b) At least one $$$?$$$ sign is $$$a$$$. Without loss of generality, suppose the bottom row $$$?$$$ sign is $$$a$$$. Then, we have $$$mex(a,a) = mex(a) = b$$$ and $$$mex(b,b) = mex(b) = c$$$, so $$$b$$$ and $$$c$$$ should be $$$0$$$ and $$$1$$$ in some order (since the $$$mex$$$ of a singleton may not be greater than $$$1$$$). So $$$a$$$ needs to be $$$2$$$, and then $$$b = mex(a) = mex(2) = 0$$$ and $$$c = mex(b) = mex(0) = 1$$$. Replacing $$$a$$$, $$$b$$$ and $$$c$$$, we have:
          . . . .          . . . .          . . . .          . . q 0  
          . . v ?    A)    . 2 v ?    B)    . 2 1 ?    C)    . 2 1 2
          . u 2 0    =>    2 u 2 0    =>    2 0 2 0    =>    2 0 2 0 
          t 2 0 1          t 2 0 1          1 2 0 1          1 2 0 1
      

      Since entries above and to the left of a $$$2$$$ should be $$$0$$$ and $$$1$$$ (in some order), we know that t u v should be either 0 1 0 or 1 0 1. So, by the main fact, we can reveal both $$$2$$$ in step A. Then, since $$$mex(2,2)=0$$$ we know in step B that t u v was actually 1 0 1. By the main fact, we know in step C that the $$$?$$$ sign should be $$$2$$$, and again, since it has a $$$1$$$ to its left, there must be a $$$0$$$ above.

      Finally, by the main fact, $$$q=2$$$, but then: $$$0 = mex(2,2) = mex(2,q) = 1$$$, which is a contradiction.

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

        You are right. On the other hand, your solution is clean and correct.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

fengyecong Can you explain your solution for D? or can anyone try to explain this?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D's editorial, how do you make sure that when you multiply k by 2 continuously, it does not get too large?

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

    $$$k>n$$$ is zero.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh.. So sad I thought of this dp during contest but I keep thinking that k could be out of range.. Thanks.

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

Can somebody please explain problem B Quadruple ??

»
5 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

Here are video editorials of A-D and a screencast of doing badly on all of them

»
5 weeks ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

Ignore.

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

maroonrk Can we expect tommorow's ABC 181 to be resheduled in clash to cf round #680 ?

»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Is it possible to solve problem A in c++? I used the approach recommended in the tutorial but got the wrong answer for large a b c inputs

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As you didn't show us your submission I assume that u didn't check the overflow here. See this solution to better understand-

    #include<bits/stdc++.h>
    using namespace std;
    #define int long long int
    #define mod 998244353
    const int N=1e5+5;
    signed main()
    {
        ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        int a,b,c;cin>>a>>b>>c;
        int s1=a*(a+1)/2,s2=b*(b+1)/2,s3=c*(c+1)/2;
        cout<<((((s1%mod)*(s2%mod))%mod)*(s3%mod))%mod;
        return 0;
    }
    
»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Could someone explain why it's possible to obtain any permutation in a connected component for problem C? Editorial says that we can swap A and D in a sequence A-B-C-D, where we can swap connected elements, by a sequence of adjacent swaps. But after we swap A and B, we get a sequence B, A, C, D, where it might be impossible to swap A and C. What obvious fact am I missing?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Say among four columns A, B, C and D, you can swap pairs (A, B), (A, C) and pairs (C, D), so all of these form a single component.

    We can achieve all orderings by an order of swaps. Starting from ABCD, to get BDAC, we make swaps to get ABCD -> BACD-> BCAD-> BDAC, to get CBDA, we follow ABCD-> ABDC-> CBDA.

    We can see that for a pair(x, y), we can achieve this swaps through a sequence of swaps, if x and y lie in same connected component. Visualize like moving on a path over spanning tree formed by these edges (pairs).

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

    let's denote the transposition of positions i and j by (i j).

    then (A C) = (A B)*(B C)*(A B) (* denotes the function composition)

    it's easy to prove inductively that in order to generate the entire permutations, you only need N-1 transpositions forming a spanning tree, using the above equality.

    (this is also one of the basic exercise you'll find in any group theory course)

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Math only round and require great mental affect.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For A , I don't really understand why // is needed instead of just / in the Python solution. Both feels like it does the same thing but using just divide / gets the wrong answer.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why in A this code gives me wa?

code
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This overflows because you multiplicate three multiplicators, then use the mod operation. Since the mod value is at about 2^30 that would require the integer type to be about 90 bit. Use instead something like cout<<((((s1%mod)*(s2%mod))%mod)*(s3%mod))%mod; multiplication one value at a time.

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

Problem B:

the number f ( N , K ) of pairs of integers ( a , b ) such that 1 ≤ a , b ≤ N and a + b = K .

f(N,K)=min(K−1,2N+1−K)forK=2,3,…,2N.

Here, I observed that it can be K-1 if both a and b are positive but I didn't understand 2nd part 2N+1-K. How this comes up? what is the proof?

UPD: got it.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please share it!!

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For N=5, K=7, a+b can be (1+6), (2+5), (3+4), (4+3), (5+2) and (6+1).[considering 1<=a,b<=+Infinity]

      now, because of N=5, we have to take (5+2) as the highest sum within constraints. We can make the formula as (5-2+1)==(5-(K-5))+1==(N-(K-N))+1==(2N+1-K).

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

Can anybody tell me why I am getting TLE. Link To My Submission

»
5 weeks ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

How to Solve B with Inclusion-Exclusion principle??

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

    For context, the editorial of problem B says that it can also be solved using "inclusion-excusion and so on" in $$$O(1)$$$. Would be great if someone could briefly explain the approach.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it