maroonrk's blog

By maroonrk, history, 19 months ago, In English

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!

  • Vote: I like it
  • +157
  • Vote: I do not like it

| Write comment?
»
19 months ago, # |
  Vote: I like it -32 Vote: I do not like it

Why can I see Atcoder's contest here?

»
19 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Thanks for your participation!

During the contest, we realized tests of A are weak. We'll add some after_contest tests.

»
19 months ago, # |
  Vote: I like it +114 Vote: I do not like it

Thank you for participating in the contest. I hope you enjoyed it.

»
19 months ago, # |
  Vote: I like it +3 Vote: I do not like it

It took me four penalties to realize B is binary search. Pain!

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You can check out my video editorial of the first 2 problems if you want

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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'?

  • »
    »
    19 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It's similar to the construction of the xor basis.

    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wow, thank you so much. I will read this first.

  • »
    »
    19 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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$$$.

    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        19 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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$$$.

        • »
          »
          »
          »
          »
          19 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

»
19 months ago, # |
  Vote: I like it +3 Vote: I do not like it

For F, can someone explain why solving the subproblem in [2] is sufficient to solve the original problem?

»
19 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Great round with interesting problems.

»
19 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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/

  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    3
    90 10 9
    

    Your answer is 90910. Correct answer is 99010.

»
19 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I understand how to get that conclusion. I just misunderstanding that sentence...