We will hold AtCoder Regular Contest 146.
- Contest URL: https://atcoder.jp/contests/arc146
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20220820T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: PCTprobability
- Tester: maspy, tatyam
- Rated range: — 2799
The point values will be 300-500-600-800-800-1200.
We are looking forward to your participation!
Why can I see Atcoder's contest here?
Here is the discussion area of Atcoder
You should go https://www.atcoder.jp/contests/arc146
It seems that Atcoder doesn't have a discussion system so they put their discussion area in codeforces.
Thanks for your participation!
During the contest, we realized tests of A are weak. We'll add some after_contest tests.
Thank you for participating in the contest. I hope you enjoyed it.
Very interesting contest and problem set!
For problem B
If you're wondering how the the greedy approach in problem B is a kind of binary search, it is because the answer range shrinks by a factor of ½ each time you decide a bit's value.
It took me four penalties to realize B is binary search. Pain!
Why do you submit if you're not sure your idea is correct?
You can check out my video editorial of the first 2 problems if you want
For the editorial of problem C, I really wonder, how could someone come up with the idea of 'adding element' to construct S from smaller size to larger one. Which part of the problem statement inspires you to consider it in this way?
For instance, as for me, I feel it is difficult to handle the original problem, so that I decide to try to calculate the complementary set of S (but end up with nothing). Would someone like to share how you adjust your thought step by step and finally realize that maybe we should try 'adding element'?
It's similar to the construction of the xor basis.
Wow, thank you so much. I will read this first.
Although I didn't come up with the solution during the contest, I thought I understood why we should try to add elements after reading the editorial. I'll try to explain it here.
For convenience, let's call the set that satisfies the conditions a "good" set.
On the one hand, according to the conditions, if $$$S$$$ is a good set, then every subset of $$$S$$$ is also a good set. As a result, we can reach every good set from some smaller good sets (i.e. its proper subsets). To make the problem more solvable, it's obvious that we should extend a good set of size $$$n$$$ to some good sets of size $$$n+1$$$.
On the other hand, for a good set $$$S$$$, it's necessary that there aren't two or more non-empty subsets $$$T$$$ of $$$S$$$ that the XOR of the elements in $$$T$$$ is zero. (it's easy to prove if you understand the editorial, so the proof is omitted) Combined with the Pigeonhole principle, the size of a good set must be $$$O(N)$$$. After exploring the properties of good sets, we can find that only the size of a good set is small enough to be a DP state, so that we should try to define $$$dp_i$$$ as the number of good sets of size $$$i$$$.
I think your way of thinking is very intuitive. Thank you for sharing your great idea.
May I ask one more thing about how to reach the conclusion that the size of good set should be O(N), based on Pigeonhole principle?
consider a set $$$S$$$ with size $$$n$$$ satisfying $$$rank(S) = n$$$, since $$$rank(S)$$$ can't be more than $$$n$$$, adding element to this set will cause this set have some subset of $$$S$$$ have xor value equal to $$$0$$$.
let's assume the element we are adding is $$$X$$$, if there have some odd size subset of $$$S$$$ have xor value equal to $$$X$$$, then this set is not valid. Otherwise, we will have some even size subset of $$$S$$$ whose xor value equal to $$$X$$$, then we are fine. And we can add one more element $$$Y$$$ to this set.
When we add element $$$Y$$$ to this set, again, if there exist some odd size subset of $$$S$$$ with xor value equal to $$$Y$$$, the set will become invalid. Otherwise there have some odd size subset of $$$S$$$ whose xor value equal to $$$Y$$$.
let the union of $$$X$$$ and the subset with xor value equal to $$$X$$$ be $$$A$$$, the union of $$$Y$$$ and the subset with xor value equal to $$$Y$$$ be $$$B$$$, then we can find that when we take the symmetric difference of $$$A$$$ and $$$B$$$, we will get a even size set with xor value equal to $$$0$$$.
So it is impossible to have a valid set with size more than $$$n + 1$$$.
The analysis based on linear basis is cool. This really makes sense that the size of S is O(n). Thank you, and I will think about this further.
For F, can someone explain why solving the subproblem in [2] is sufficient to solve the original problem?
Great round with interesting problems.
Can anyone tell me what is wrong with this code for problem A? I got AC * 28 and WA * 1
I tried to submit other ac codes, but all of them got wa.
https://paste.ubuntu.com/p/HNGXS8J7zD/
Your answer is 90910. Correct answer is 99010.
For the editorial of problem C: “Rephrasing the conditions：The condition is satisfied if and only if there is no non-empty subset of S whose size is even and the XOR of whose elements is 0.” how to get this conclusion?
I understand how to get that conclusion. I just misunderstanding that sentence...