maroonrk's blog

AtCoder Grand Contest 043 (not 042!) Announcement
By maroonrk, history, 5 years 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

Comments Comments (68)
| Write comment?
»
5 years ago, # |
  Vote: I like it +20 Vote: I do not like it

So it clashes with JOI, right xD?

→ Reply
  • »
    »
    5 years 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?)

    → Reply
»
5 years 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

→ Reply
»
5 years 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

→ Reply
»
5 years ago, # |
  Vote: I like it +19 Vote: I do not like it

How to solve C and D?

→ Reply
  • »
    »
    5 years 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
    → Reply
    • »
      »
      »
      5 years 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
      → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
        • »
          »
          »
          »
          »
          5 years 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.

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

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

        → Reply
      • »
        »
        »
        »
        5 years 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?

        → Reply
        • »
          »
          »
          »
          »
          5 years 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.

          → Reply
»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

How to solve B?

→ Reply
»
5 years ago, # |
  Vote: I like it +98 Vote: I do not like it

How to solve?

→ Reply
»
5 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Thank you for participation!

Editorial is up!

→ Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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.

      → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
»
5 years 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

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

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

    → Reply
»
5 years 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!

→ Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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?

      → Reply
  • »
    »
    5 years 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.

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

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

    → Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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?

    → Reply
    • »
      »
      »
      5 years 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?

      → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
»
5 years 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!

→ Reply
  • »
    »
    5 years 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?

    → Reply
»
5 years 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}}$$$?

→ Reply
  • »
    »
    5 years 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)$$$

    → Reply
»
5 years ago, # |
  Vote: I like it +191 Vote: I do not like it

Trying to solve E be like

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve B?

→ Reply
»
5 years ago, # |
  Vote: I like it +42 Vote: I do not like it

Reading on problem E https://arxiv.org/pdf/1203.3602.pdf

→ Reply
  • »
    »
    5 years 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 :|

    → Reply
»
5 years ago, # |
  Vote: I like it +45 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years 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).

    → Reply
»
5 years 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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    Can you please reread the statement?

    → Reply
  • »
    »
    5 years 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.

    → Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years 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
→ Reply
»
5 years 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

→ Reply
  • »
    »
    5 years 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

    → Reply
»
5 years ago, # |
  Vote: I like it -18 Vote: I do not like it

too hard!

→ Reply
»
5 years 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.

→ Reply
»
5 years 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;

}

→ Reply
»
5 years 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 :)

→ Reply
»
5 years 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?

→ Reply