№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Название |
---|
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 :) !
Can someone give a detailed explanation of the solution of problem J?
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.
Why this submission in problem B 98083230 didn't get TLE ?