8

AtCoder Regular Contest 146 Announcement

 2 years ago
source link: http://codeforces.com/blog/entry/106187
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

AtCoder Regular Contest 146 Announcement

11 days ago, # |

The comment is hidden because of too negative feedback, click here to view it

11 days ago, # |

Thanks for your participation!

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

11 days ago, # |

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

11 days ago, # |

Very interesting contest and problem set!

For problem B

view answer

11 days ago, # |

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

11 days ago, # |

← Rev. 2 →  

0

couldn't solve A. Really disappointed :" 27AC but 3wa :"

11 days ago, # |

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

11 days ago, # |

The comment is hidden because of too negative feedback, click here to view it

11 days ago, # |

how to solve task B?

11 days ago, # |

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

  • 11 days ago, # ^ |

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

    • 11 days ago, # ^ |

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

  • 10 days ago, # ^ |

    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 SS is a good set, then every subset of SS 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 nn to some good sets of size n+1n+1.

    On the other hand, for a good set SS, it's necessary that there aren't two or more non-empty subsets TT of SS that the XOR of the elements in TT 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)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 dpidpi as the number of good sets of size ii.

    • 10 days ago, # ^ |

      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?

      • 10 days ago, # ^ |

        consider a set SS with size nn satisfying rank(S)=nrank(S)=n, since rank(S)rank(S) can't be more than nn, adding element to this set will cause this set have some subset of SS have xor value equal to 00.

        let's assume the element we are adding is XX, if there have some odd size subset of SS have xor value equal to XX, then this set is not valid. Otherwise, we will have some even size subset of SS whose xor value equal to XX, then we are fine. And we can add one more element YY to this set.

        When we add element YY to this set, again, if there exist some odd size subset of SS with xor value equal to YY, the set will become invalid. Otherwise there have some odd size subset of SS whose xor value equal to YY.

        let the union of XX and the subset with xor value equal to XX be AA, the union of YY and the subset with xor value equal to YY be BB, then we can find that when we take the symmetric difference of AA and BB, we will get a even size set with xor value equal to 00.

        So it is impossible to have a valid set with size more than n+1n+1.

        • 10 days ago, # ^ |

          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.

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK