### maroonrk's blog

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

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


}

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