### maroonrk's blog

By maroonrk, history, 6 weeks ago, We will hold AtCoder Regular Contest 146.

The point values will be 300-500-600-800-800-1200.

We are looking forward to your participation! Comments (30)
 » 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.
•  » » because you're weak !!
 » 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 view answerIf 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?
•  » » » I thought my idea was correct when I submitted...But then the judge returned wrong answer and I realized my greedy approach was incorrect.(after four tries)
 » 5 weeks ago, # | ← Rev. 2 →   couldn't solve A. Really disappointed :" 27AC but 3wa :"
 » You can check out my video editorial of the first 2 problems if you want
 » Maybe irrelevant, but... beg for c++20
 » how to solve task B?
 » 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  is sufficient to solve the original problem?
 » can someone explain solution of question b? I am not able to understand official editorial of b.
 » In Task A, there has been an extended testing file named as after_contest00.txt on which my solution gives verdict WA. I would love to know from your side, what could be in that test case?
 » 5 weeks ago, # | ← Rev. 2 →   Great round with interesting problems.
 » 5 weeks ago, # | ← Rev. 3 →   Can anyone tell me what is wrong with this code for problem A? I got AC * 28 and WA * 1I tried to submit other ac codes, but all of them got wa.https://paste.ubuntu.com/p/HNGXS8J7zD/
•  » » 3 90 10 9 Your answer is 90910. Correct answer is 99010.
 » 4 weeks ago, # | ← Rev. 2 →   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...