maroonrk's blog

By maroonrk, history, 7 months ago, In English

We will hold AtCoder Grand Contest 043. You may confuse this with AGC042, but it is 043. AGC042 was prepared as a mirror of WTF 2020 and we keep it as is.

This contest counts for GP30 scores.

The point values will be 400-700-900-1200-1400-2100.

We are looking forward to your participation!

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

»
7 months ago, # |
  Vote: I like it +20 Vote: I do not like it

So it clashes with JOI, right xD?

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

    Thank you for pointing it out. I didn't notice the time of the second mirror was modified.

    I'm sorry that we cannot move the contest time. Please enjoy the mirror for 4.5 hours. (or enjoy AGC for 120mins?)

»
7 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Bump.

Starts in 10 minutes and isn't on the sidebar currently :p

»
7 months ago, # |
  Vote: I like it -64 Vote: I do not like it

It would be perfect if Atcoder used codeforces style contest timing, like xx:x5

»
7 months ago, # |
  Vote: I like it +19 Vote: I do not like it

How to solve C and D?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How Did you solved B ? is there any pattern ??

    TC -2
    
     2 3 1 1 3 1 2 3 1 2 
      1 2 0 2 2 1 1 2 1 
       1 2 2 0 1 0 1 1 
        1 0 2 1 1 1 0 
         1 2 1 0 0 1
          1 1 1 0 1
           0 0 1 1
            0 1 0
             1 1
              0 
               
      TC-1
            	
     1 2 3 1  
      1 1 2 
       0 1 
        1
    
    • »
      »
      »
      7 months ago, # ^ |
      Rev. 2   Vote: I like it +16 Vote: I do not like it

      The possible answer is 0, 1 or 2, and two case exists:

      If the sequence doesn't contain 2, the answer is 0 or 2. If the sequence contains 2, the answer is 0 or 1.

      We can operate the sequence, according to following ways.

      If the sequence doesn't contain 2, change 1 to 0 and change 3 to 1. If the sequence contains 2, change 2 to 0 and change 1,3 to 1.

      Now the sequence contains only 0 and 1, and only 1 matters.

      For each element, if i-th element is 1, add (n-1)C(i), and find the sum modulo 2. Let's define this value as k. If k is 0, the answer is 0. Otherwise, if the original sequence contains 2, the answer is 1. Otherwise the answer is 2.

      The sequence of the sample tests is changed like this:

      TC 1 : 1231 -> 1011
      
      1 0 1 1
       1 1 0
        0 1
         1
      
      TC 2 : 2311312312 -> 0111110110
      
      0 1 1 1 1 1 0 1 1 0
       1 0 0 0 0 1 1 0 1
        1 0 0 0 1 0 1 1
         1 0 0 1 1 1 0
          1 0 1 0 0 1
           1 1 1 0 1
            0 0 1 1
             0 1 0
              1 1
               1
      
      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        what is the proof of adding (n-1)C(i), in your explanation for every 1 here.

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

          Consider this case:

          0 0 0 0 0 0 1 0 0 0
           0 0 0 0 0 1 1 0 0
            0 0 0 0 1 0 1 0
             0 0 0 1 1 1 1
              0 0 1 0 0 0
               0 1 1 0 0
                1 0 1 0
                 1 1 1
                  0 0
                   0
          

          Because the answer is 0 or 1, we need only parity of the value, and because the parity of (a-b) and (a+b) are same, we can replace |a-b| with (a+b). Now we can find this adding pattern follows Pascal's triangle, and it's parity can be found using the number of factor 2 of nCr. In the first line of the case, each 1 doesn't affect other 1s, so we can add all values respectively.

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

        btw, $$$C(n, k)$$$ is odd iff $$$k$$$ is submask of $$$n$$$.

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I have understood the case when sequence contains 2. If there is no 2 in sequence, how can you change 1 to 0 and 3 to 1?

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          In this case, we can subtract 1 from each element. Now each element is 0 or 2, and if we divide each element by 2, each element becomes 0 or 1. Because the answer also comes in half in this operation, we have to multiply 2 by the result.

»
7 months ago, # |
  Vote: I like it +14 Vote: I do not like it

How to solve B?

»
7 months ago, # |
  Vote: I like it +98 Vote: I do not like it

How to solve?

»
7 months ago, # |
  Vote: I like it +25 Vote: I do not like it

Thank you for participation!

Editorial is up!

»
7 months ago, # |
  Vote: I like it +84 Vote: I do not like it

Wow, I couldn't believe my eyes when I was copying xor transorm in C xd. I think this problem could have easily been D on a regular Codeforces round.

By the way, how is it possible to come up with so cool easy problems like A and B? Problems that are doable in 5 minutes are almost never fun, but you guys somehow constantly manage to get them. But the whole problemset was brilliant either way.

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

    Yes, we misjudged the difficulty of C, but you don't need xor-transform to solve it. Please check the editorial.

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

      That's very clever trick! But it is even more thinking in a problem that required more thinking for me than ABDE combined xD.

      • »
        »
        »
        »
        7 months ago, # ^ |
        Rev. 2   Vote: I like it +55 Vote: I do not like it

        For me C was far easier than B or D (which I couldn't even solve ;_;)

        I guess it greatly depends on how good you are at combinatorics.

»
7 months ago, # |
  Vote: I like it +146 Vote: I do not like it

Best contest of the year for me so far... A-D are all just brilliant... Omg

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

    And that's just the first AGC this year...

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

How to solve question A of this round? As I am not able to understand the editorial. Thanks!

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

    Consider any path from the left-top corner to the right-bottom. Since we must invert blocked cells in that path, just take contiguous blocked cells and invert them(They represent one rectangle that we are going to change). So our problem is to find a path which has minimum number of contiguous blocked cells. It can be done with simple dp.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I got what we are trying from your explaination but i am not getting the thing that as given in the editorial how does the Z value decreases by atmost one only in one flip operation?

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

    Every step from a white cell to a black cell has cost 1, else cost 0. Find cheapest path from start to end, ie dijkstra.

»
7 months ago, # |
Rev. 2   Vote: I like it -26 Vote: I do not like it

B soln — First do a few steps until all numbers are either {0,2}s or {0,1}s.
Now see the contribution of every index. I saw the following pattern (can be proven using induction).
N here is the size of the remaining array.
For odd N, consider all odd indexes which are subsets of N. For ex, for 13 = 1101(base 2) odd subsets are 1,101,1001,1101 or indexes 1,5,9,13
For even N, consider all indexes i for N-1 and also consider index+1.
For ex, for 14, we consider 1,5,9,13 for 13 and also 1+1,5+1,9+1,13+1 or 1,2,5,6,9,10,13,14.

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

    First do a few steps until all numbers are either {0,2}s or {0,1}s

    Consider a string like 2111...1113. After the first step this becomes 1000...002, so it takes $$$\mathcal{O}(n)$$$ steps to arrive at a sequence containing only $$${0, 1}$$$ or $$${0, 2}$$$. Did the tests not contain a case like this?

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can this still be defeated if I store the sequence as vector of pairs (value, number of occurences) where two consecutive pairs have different values?

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

        221221...2212111...1113 should hack that. The 2111...1113 in the end acts just as it did earlier, forcing us to simulate O(n) steps, and the 221221...221 sequence at the start just shifts itself once at every step: 011011... -> 101101... -> 110110..., so at every step there are O(n) segments of different values.

»
7 months ago, # |
Rev. 2   Vote: I like it +26 Vote: I do not like it

Great contest! I think you should consider adding this testcase in $$$B$$$

Spoiler

My solution tries to do what is written in the statement naively until there are only $$$2$$$ different digits left in the sequence. Then it does something similar to what editorial solution does for $$$01$$$ case. On random $$$N = 10^6$$$ tests it only does $$$35-45$$$ steps, while on the testcase above it will certainly get TLE because of $$$O(N^2)$$$ complexity.

Thanks to kostia244 for coming up with this testcase!

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

    "It's enough to have random testcases only, nobody will make some shitty $$$O(n^2)$$$ with clever break pass." – Yeah How many times have I already seen something like this?

»
7 months ago, # |
  Vote: I like it +23 Vote: I do not like it

In D, why is the number of permutations that can be created from a sequence of blocks $$$a_1, \dots, a_K$$$ equal to $$$\frac{N!}{\prod_{i = 1}^{K} \sum_{j = 1}^{i} a_{j}}$$$?

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

    Let say $$$a_1,a_2,a_3,a_4$$$ are $$$3,1,2,3$$$, respectively.

    The permutation with this condition looks like: [abc][d][ef][ghi]

    The conditions are:

    • a should be the biggest among abc.
    • d should be the biggest among abcd.
    • e should be the biggest among abcdef.
    • g should be the biggest among abcdefghi.

    These are independent, so the probability is $$$1/(3*4*6*9)$$$

»
7 months ago, # |
  Vote: I like it +191 Vote: I do not like it

Trying to solve E be like

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve B?

»
7 months ago, # |
  Vote: I like it +42 Vote: I do not like it
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Provided the solution for $$$1$$$ out of $$$n$$$, but the AND and OR constructions were not very helpful :|

»
7 months ago, # |
  Vote: I like it +45 Vote: I do not like it

Do you know that E is rng_58's hardest problem?

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

    Well the free group idea came up a few times for sure, but constructing the appropriate word should be pretty novel (I saw it for two points before, but not the general case).

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you upload the testcases to dropbox?

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

can anyone explain why my logic failed on question B. i took the difference when two adjacent elements were different and removed the elements when they were similar for example 12111231

1 2 -> 1

2 1 -> 1

1 1 -> ignore

1 1 -> ignore

1 2 -> 1

2 3 -> 1

3 1 -> 2

now the new series is 11112 did the same again if the arr ends with length 1 , then print the arr[0] else 0 it worked for 36 test case but from 37 — 46 it failed. can anyone explain how the consecutivily 36 test cases were passed but rest all 10 failed

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain me, why my solution for problem A got WA?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please reread the statement?

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

    Check this test:

    3 3
    .##
    .##
    #.#
    

    Your output is 2, the answer is 1.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How the answer is 2 in this case?

      2 2

      # .

      . #

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Both # have to be removed because they are start and end points

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          3 3

          .##

          .##

          #.#

          what should be answer in this case? it should be 2.

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

    You basically search the path with least black cells, what is not asked.

    You need to find the path with the least changes from white to black, and count them.

»
7 months ago, # |
  Vote: I like it +22 Vote: I do not like it

For D, after fixing the number of blocks with length $$$1,2,3$$$ (denoted by $$$p_1,p_2, p_3$$$). The number of ways is $$$\frac{(3n)!}{p_1! p_2! p_3! 2^{p_2} 3^{p_3}}$$$.

Proof
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please check my code for task A and let me know why it is wrong? Many thanks! :) My code is here

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

    Your code returns 0 for the following test case, the correct answer is 1.

    1 5
    #####
    

    You fill dp and dp2 independently when in fact you need to fill them at the same time. The reason being that values from both dp arrays are needed to calculate the next element.

    You can have a look at my code

»
7 months ago, # |
  Vote: I like it -18 Vote: I do not like it

too hard!

»
7 months ago, # |
  Vote: I like it -10 Vote: I do not like it

About the problem C. Why the point corresponding to a defeteded state is in the independent set of maximum weight.

»
7 months ago, # |
Rev. 3   Vote: I like it -33 Vote: I do not like it

Regarding Q.NO. 1 In the first question i have changed every black index to 0 and white index to 1 . so the problem is to calculate the n+m-(max no. of white cells that you encounter which is essentially sum of the 1's ) and it can be done by the help of a dp . I have written code for the same , i am getting "AC" on first 5-6 cases and after that there is "WA". please help me with that.

Below is my code .

include <bits/stdc++.h>

using namespace std;

define ll long long

define l long

define pb push_back

define mp make_pair

define mt make_tuple

int main() {

ios_base::sync_with_stdio(false);
cin.tie(NULL);

    int n,m;
    cin>>n>>m;
    string s;
    int a[n][m];
    for(int i=0;i<n;i++)
    {
        cin>>s;
        for(int j=0;j<m;j++)
        {
            if(s[j]=='.')
            a[i][j]=1;
            else
            a[i][j]=0;
        }
    }

    int sum[n+1][m+1];
    for(int i=0;i<n+1;i++)
    {
        for(int j=0;j<m+1;j++)
        {
            if(i==0||j==0)
            sum[i][j]=0;
        }
    }
    for (int y = 1; y <=n; y++)
    {
         for (int x = 1; x <= m; x++)
         {
            sum[y][x] = max(sum[y][x-1],sum[y-1][x])+a[y-1][x-1];
          }
    }

    cout<<n+m-1-sum[n][m]<<endl;



return 0;

}

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://atcoder.jp/contests/agc043/submissions/11116664

Need help in First Ques

Kinda Weak in DP :)

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How can I prove the greedy algorithm is correct in C? I know that one vertex has more weight than the sum of weights of all vertices of smaller weight. This makes us consider vertices in descending weight order, but what should we do with vertices of equal weight?

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

I need help with the first sample of the problem C. How can vertices $$$(x_2, y_1, z_1), (x_1, y_2, z_1), (x_1, y_1, z_2), (x_2, y_2, z_2)$$$ form an independent set if there are edges $$$(x_1, x_2), (y_1, y_2), (z_1, z_2)$$$? I think these vertices form a 4-clique. For example, according to definition, $$$(x_1, y_1, z_2)$$$ should be adjacent to $$$(x_2, y_2, z_2)$$$ because there are edges $$$(x_1, x_2)$$$ and $$$(y_1, y_2)$$$ (the graph has parallel edges). Shouldn't maximum weight independent set be just $$$(x_2, y_2, z_2)$$$ as this vertex is adjacent to every vertex that has either of $$$x_1, y_1, z_1$$$, that is, every other vertex?