Блог пользователя mathusalen

Автор mathusalen, история, 5 лет назад, По-английски

I have added the SWERC contest that was held in Paris one year ago on Dec 2018 to the gym here. You can participate virtually at any time. Many thanks to dacin21 who has kindly provided me with solutions to Problem C and G.

  • Проголосовать: нравится
  • +32
  • Проголосовать: не нравится

»
5 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

Thanks for adding the contest to the gym !

Unfortunately the provided editorial only contains vague hints. Would appreciate it if someone provides detailed explanations for the hard problems :) !

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone give a detailed explanation of the solution of problem J?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    The birthday "paradox" asserts that if $$$n$$$ people choose one element each from $$$k$$$ possible elements independently, there will be a collision (two people choosing the same element) with high probability provided that $$$n^2 » k$$$. This is due to the fact that there are $$$n*(n-1)/2$$$ different couples that may collide. Thus if you have a group of 23 people there will be at least two of them with the same birthday with a probability higher than 0.5. In this case $$$k = 356$$$ and $$$n = 23$$$.

    We are goint to exploit this fact to solve the problem that can be formulated as follows: You have 4 sequences of random n-bit numbers $$$X_1$$$, $$$X_2$$$, $$$X_3$$$, $$$X_4$$$. You want to find four elements $$$x_1\in X_1$$$, $$$x_2 \in X_2$$$, $$$x_3\in X_3$$$, and $$$x_4 \in X_4$$$ such that $$$x_1 \oplus x_2 \oplus x_3 \oplus x_4 = 0$$$.

    We proceed as follows. Consider a list of about $$$2^{n/3}$$$ numbers from $$$X_1$$$ and $$$2^{n/3}$$$ number from $$$X_2$$$. There are about $$$2^{2n/3}$$$ couples so we may expect that there are $$$2^{n/3}$$$ couples such that that their first $$$n/3$$$ bits match ($$$k = 2^{n/3}$$$). So we find a list of $$$2^{n/3}$$$ couples $$$x_i, x_j$$$ such that $$$x_i\oplus x_j$$$ is zero in its first $$$n/3$$$ bits and $$$x_i\in X_1$$$ and $$$x_j \in X_2$$$.

    We do the same with $$$X_3$$$ and $$$X_4$$$ and we find $$$2^{n/3}$$$ couples such that their first $$$n/3$$$ bits match.

    Finally again by the birthday paradox we may expect that there are a couple of the first group and a couple from the second group such that their corresponding xor matches on the last $$$2n/3$$$ bits.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why this submission in problem B 98083230 didn't get TLE ?