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.
- Contest URL: https://atcoder.jp/contests/agc043
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20200321T2100&p1=248
- Duration: 150 minutes
- Number of Tasks: 6
- Writer: yosupo, maroonrk, sigma425
- Rated range: All
The point values will be 400-700-900-1200-1400-2100.
We are looking forward to your participation!
So it clashes with JOI, right xD?
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?)
Good News: According to the JOI Mirror site, you can choose your favorite start-time now!
Bump.
Starts in 10 minutes and isn't on the sidebar currently :p
It would be perfect if Atcoder used codeforces style contest timing, like xx:x5
No it wouldn't
How to solve C and D?
How Did you solved B ? is there any pattern ??
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:
what is the proof of adding (n-1)C(i), in your explanation for every 1 here.
Consider this case:
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.
btw, $$$C(n, k)$$$ is odd iff $$$k$$$ is submask of $$$n$$$.
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?
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.
How to solve B?
How to solve?
Thank you for participation!
Editorial is up!
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.
Yes, we misjudged the difficulty of C, but you don't need xor-transform to solve it. Please check the editorial.
That's very clever trick! But it is even more thinking in a problem that required more thinking for me than ABDE combined xD.
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.
Best contest of the year for me so far... A-D are all just brilliant... Omg
And that's just the first AGC this year...
How to solve question A of this round? As I am not able to understand the editorial. Thanks!
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.
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?
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.
https://atcoder.jp/contests/agc043/submissions/14102609
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.
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?
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?
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.
Great contest! I think you should consider adding this testcase in $$$B$$$
3111...1112
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!
"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?
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}}$$$?
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:
These are independent, so the probability is $$$1/(3*4*6*9)$$$
Trying to solve E be like
How to solve B?
Reading on problem E https://arxiv.org/pdf/1203.3602.pdf
Provided the solution for $$$1$$$ out of $$$n$$$, but the AND and OR constructions were not very helpful :|
Do you know that E is rng_58's hardest problem?
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).
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
Atcoder shuffles the cases so that the failed ones are always the last.
ohh,i see :) Grand contest are tough.
In fact,it's the same to all Atcoder contests.
I think this is the longest sentence I've read today.
well you know words are funny thing .....
Can anyone explain me, why my solution for problem A got WA?
Can you please reread the statement?
Check this test:
Your output is 2, the answer is 1.
How the answer is 2 in this case?
2 2
# .
. #
Both # have to be removed because they are start and end points
3 3
.##
.##
#.#
what should be answer in this case? it should be 2.
You can reach the following setup doing one flip only
How? one flip at index (1,1) and other At destination(3,3).
Read the statement once more
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.
thanks ,now i got .
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}}$$$.
We 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.
Can anyone please check my code for task A and let me know why it is wrong? Many thanks! :) My code is here
Your code returns 0 for the following test case, the correct answer is 1.
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
too hard!
About the problem C. Why the point corresponding to a defeteded state is in the independent set of maximum weight.
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() {
}
Your DP transformation is wrong. You can have a look at my blog(https://blog.csdn.net/qq_42886072/article/details/105023236)
https://atcoder.jp/contests/agc043/submissions/11116664
Need help in First Ques
Kinda Weak in DP :)
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?