### maroonrk's blog

By maroonrk, history, 3 months ago, ,

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!

• +264

 » 3 months ago, # |   +20 So it clashes with JOI, right xD?
•  » » 3 months ago, # ^ |   +77 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?)
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +45 Good News: According to the JOI Mirror site, you can choose your favorite start-time now!
 » 2 months ago, # |   +7 Bump.Starts in 10 minutes and isn't on the sidebar currently :p
 » 2 months ago, # |   -64 It would be perfect if Atcoder used codeforces style contest timing, like xx:x5
•  » » 2 months ago, # ^ |   +128 No it wouldn't
 » 2 months ago, # |   +19 How to solve C and D?
•  » » 2 months ago, # ^ |   0 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 
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +16 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 
•  » » » » 2 months ago, # ^ |   0 what is the proof of adding (n-1)C(i), in your explanation for every 1 here.
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 2 months ago, # ^ |   +40 btw, $C(n, k)$ is odd iff $k$ is submask of $n$.
•  » » » » 2 months ago, # ^ |   0 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?
•  » » » » » 2 months ago, # ^ |   0 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.
 » 2 months ago, # |   +14 How to solve B?
 » 2 months ago, # |   +98 How to solve?
 » 2 months ago, # |   +25 Thank you for participation!Editorial is up!
 » 2 months ago, # |   +84 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.
•  » » 2 months ago, # ^ |   +16 Yes, we misjudged the difficulty of C, but you don't need xor-transform to solve it. Please check the editorial.
•  » » » 2 months ago, # ^ |   +6 That's very clever trick! But it is even more thinking in a problem that required more thinking for me than ABDE combined xD.
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +55 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.
 » 2 months ago, # |   +146 Best contest of the year for me so far... A-D are all just brilliant... Omg
•  » » 2 months ago, # ^ |   +54 And that's just the first AGC this year...
 » 2 months ago, # |   +4 How to solve question A of this round? As I am not able to understand the editorial. Thanks!
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 2 months ago, # ^ |   0 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?
•  » » 2 months ago, # ^ |   +1 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.
 » 2 months ago, # | ← Rev. 2 →   -26 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,13For 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.
•  » » 2 months ago, # ^ |   +18 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?
•  » » » 2 months ago, # ^ |   0 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?
•  » » » » 2 months ago, # ^ |   +10 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.
 » 2 months ago, # | ← Rev. 2 →   +26 Great contest! I think you should consider adding this testcase in $B$ Spoiler3111...1112My 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!
•  » » 2 months ago, # ^ |   +9 "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?
 » 2 months ago, # |   +23 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}}$?
•  » » 2 months ago, # ^ |   +24 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)$
 » 2 months ago, # |   +191 Trying to solve E be like
 » 2 months ago, # |   +1 How to solve B?
 » 2 months ago, # |   +42 Reading on problem E https://arxiv.org/pdf/1203.3602.pdf
•  » » 2 months ago, # ^ |   0 Provided the solution for $1$ out of $n$, but the AND and OR constructions were not very helpful :|
 » 2 months ago, # |   +45 Do you know that E is rng_58's hardest problem?
•  » » 2 months ago, # ^ |   +18 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).
 » 2 months ago, # |   0 Can you upload the testcases to dropbox?
 » 2 months ago, # | ← Rev. 4 →   0 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 121112311 2 -> 12 1 -> 11 1 -> ignore 1 1 -> ignore 1 2 -> 12 3 -> 13 1 -> 2now 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
•  » » 2 months ago, # ^ |   +41 Atcoder shuffles the cases so that the failed ones are always the last.
•  » » » 2 months ago, # ^ |   0 ohh,i see :) Grand contest are tough.
•  » » » » 2 months ago, # ^ |   +8 In fact,it's the same to all Atcoder contests.
•  » » 2 months ago, # ^ |   0 I think this is the longest sentence I've read today.
•  » » » 2 months ago, # ^ |   0 well you know words are funny thing .....
 » 2 months ago, # |   0 Can anyone explain me, why my solution for problem A got WA?
•  » » 2 months ago, # ^ |   0 Can you please reread the statement?
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Check this test: 3 3 .## .## #.# Your output is 2, the answer is 1.
•  » » » 2 months ago, # ^ |   0 How the answer is 2 in this case?2 2# .. #
•  » » » » 2 months ago, # ^ |   0 Both # have to be removed because they are start and end points
•  » » » » » 2 months ago, # ^ |   0 3 3.##.###.#what should be answer in this case? it should be 2.
•  » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 You can reach the following setup doing one flip only ... ... ##. 
•  » » » » » » » 2 months ago, # ^ |   0 How? one flip at index (1,1) and other At destination(3,3).
•  » » » » » » » » 2 months ago, # ^ |   +10 Read the statement once more
•  » » 2 months ago, # ^ |   +1 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.
•  » » » 2 months ago, # ^ |   0 thanks ,now i got .
 » 2 months ago, # |   +22 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}}$. ProofWe can divide the numbers into groups $p_1 \times 1, p_2 \times 2, p_3\times 3$ and sort them by their largest one.
 » 2 months ago, # |   0 Can anyone please check my code for task A and let me know why it is wrong? Many thanks! :) My code is here
•  » » 2 months ago, # ^ | ← Rev. 3 →   0 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
 » 2 months ago, # |   -18 too hard!
 » 2 months ago, # |   -10 About the problem C. Why the point corresponding to a defeteded state is in the independent set of maximum weight.
»
2 months ago, # |
Rev. 3   -33

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


}

•  » » 2 months ago, # ^ |   0 Your DP transformation is wrong. You can have a look at my blog(https://blog.csdn.net/qq_42886072/article/details/105023236)
 » 2 months ago, # |   0 https://atcoder.jp/contests/agc043/submissions/11116664Need help in First Ques Kinda Weak in DP :)
 » 2 months ago, # |   0 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?
 » 2 months ago, # | ← Rev. 2 →   0 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?