maroonrk's blog

By maroonrk, history, 4 years 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

| Write comment?
»
4 years 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).

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

The contest starts in ~10 mins.

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

Best of LUCK!!

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

Maths only round?

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

MathCoder ew

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

Just counting and counting and still counting...

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

What's the solution of C?

  • »
    »
    4 years 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)

    • »
      »
      »
      4 years 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 :)

    • »
      »
      »
      4 years 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?

      • »
        »
        »
        »
        4 years 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

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

Honestly, math homework today felt a bit boring :/

»
4 years ago, # |
  Vote: I like it -12 Vote: I do not like it

good atCombinatory Regular contest.

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

How to solve C?

  • »
    »
    4 years 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.

    • »
      »
      »
      4 years 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.

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

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

  • »
    »
    4 years 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

  • »
    »
    4 years 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

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

how to solve D?

  • »
    »
    4 years 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

    • »
      »
      »
      4 years 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.

      • »
        »
        »
        »
        4 years 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.

        • »
          »
          »
          »
          »
          4 years 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....???

          • »
            »
            »
            »
            »
            »
            4 years 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].

      • »
        »
        »
        »
        4 years 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.

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

How to solve E ?

  • »
    »
    4 years 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.

    • »
      »
      »
      4 years 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.

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

        But I think 100 is very safe.

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

          It is right, but always prepare for memory issues

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

        Yes. By pigeonhole principle.

»
4 years 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?

  • »
    »
    4 years 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).

  • »
    »
    4 years 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.

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

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

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

rage quit after reading tutorial of E :(

»
4 years 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 ??

  • »
    »
    4 years 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

»
4 years 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?)

  • »
    »
    4 years 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).

    • »
      »
      »
      4 years 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.

      • »
        »
        »
        »
        4 years 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.

»
4 years 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?

»
4 years 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?

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

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

    • »
      »
      »
      4 years 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.

»
4 years 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

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

Ignore.

»
4 years 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 ?

»
4 years 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?

  • »
    »
    4 years 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).

  • »
    »
    4 years 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)

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

Why in A this code gives me wa?

code
  • »
    »
    4 years 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.

»
4 years 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

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

How to Solve B with Inclusion-Exclusion principle??

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

IOI2024 d2t2.