| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | jiangly | 3670 |
| 3 | Kevin114514 | 3657 |
| 4 | maroonrk | 3355 |
| 5 | Um_nik | 3353 |
| 6 | squareOf105 | 3346 |
| 7 | tourist | 3343 |
| 8 | strapple | 3324 |
| 9 | heuristica | 3322 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | AmShZ | 143 |
| 5 | Um_nik | 141 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 134 |
| 9 | maroonrk | 133 |
| 10 | qwexd | 130 |
| Название |
|---|



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 ?