### 300iq's blog

By 300iq, 4 weeks ago, ,

Hello everyone, this winter at Petrozavodsk was my third (Petrozavodsk) contest, now it is loaded on the gym.

Thanks to the testers MiFaFaOvO, ko_osaga, Radewoosh, ksun48, xiaowuc1, ainta, molamola., Endagorion, antontrygubO_o, tEMMIE.w.

• +204

 » 4 weeks ago, # |   +11 Thank you for your nice problem set, 300iq teacher! And could you provide the Editorial?
•  » » 4 weeks ago, # ^ |   +11 Sure! Added it to the blog.
 » 4 weeks ago, # |   +2 Whats the difficulty level? do you have editorials ?
 » 4 weeks ago, # |   +20 Wow, the English is really good in these problem statements! Thanks a lot.
•  » » 4 weeks ago, # ^ |   +21 I have friends with good English skills ;)
•  » » » 4 weeks ago, # ^ |   +41 wtf how to be friend with 300iq
•  » » » » 4 weeks ago, # ^ |   +80 learn english
•  » » » » » 4 weeks ago, # ^ |   -9 hi sirs... my english not so good, is that why lgm and other codeforces competitor don't replied to me ?? thanks sirs for the help
•  » » » » » » 4 weeks ago, # ^ |   -9 i have the same problems too ... :(any tips?
•  » » » » » » » 4 weeks ago, # ^ |   +15 Hey, I don't have too much experience, but I've gotten a lot of success asking people for help with good grammar.Some other things that help are: 1.) A clearly defined problem. 2.) Some code (if applicable). 3.) An explanation of what you've done so far, and of your code (even if it's easy for you to read, it's not always easy).Also read this: https://codeforces.com/blog/entry/64993
 » 4 weeks ago, # |   +1 colors in the blog reminds me of something very related to me <3
 » 3 weeks ago, # | ← Rev. 2 →   +10 My pseudo-solution for EFirst until there are two equal elements erase both of them. Now if we are left with less than $50$ elements we can for each $x$ calculate $(a_1 \mod x) \oplus (a_2 \mod x) \oplus \ldots \oplus (a_k \mod x)$ directly and check if it equals 0.If not we compute prefix xors, to be able to compute in constant time parity of numbers in any interval. Now for each $x$ we iterate over all bits $b$ such that $2^b \geq x$ in decreasing order and for each we want to know parity of count of numbers such, that $b$-th bit is set in $a_i \mod (x + 1)$. To do this we can run through all intervals $[l, r) = [a(x + 1), (a + 1)(x + 1))$ and in each of them set of numbers with $b$-th bit set is exactly $[l + b, l + 2b), [l + 3b, l + 4b), \ldots, [l + (2k+1)b, r)$, which is $1$ interval on first run with largest possible $b$ at most $2$ on second, $4$ on third etc. Now since $k$ is large, the function $(a_1 \mod x) \oplus (a_2 \mod x) \oplus \ldots \oplus (a_k \mod x)$ looks random, so on average the first run will happen for each $x$, second for half of them, third for one fourth, and so on, which adds to total $O(n \log ^2 n)$Except it's bullshit, because for example if after erasing numbers we are left with integers from $[4\cdot 10^5, 5\cdot 10^5)$ if we pick $x$ such that $2x \leq 4\cdot 10^5, 3x > 5\cdot 10^5$, we're left with numbers from $[4\cdot 10^5 - 2x, 5\cdot 10^5 - 2x)$, which is sequence of consecutive numbers of length divisible by $4$, least of which is even, so since $2x \oplus (2x + 1) \oplus (2x + 2) \oplus (2x + 3) = 0$ their xor is $0$, so my solution will run through all iterations for all such $x$-es and will take total of $O(n^2)$.Fortunately there were only random testcases, so reasoning based on randomness of function $(a_1 \mod x) \oplus (a_2 \mod x) \oplus \ldots \oplus (a_k \mod x)$ holds.