### ACCOUNT_FOR_BAD_ROUNDS's blog

By ACCOUNT_FOR_BAD_ROUNDS, history, 3 months ago,

There not so many div.1 rounds at all in the last months. Thanks to such users as little_angel, zxyoi, these rare rounds becomes unrated.

Thousands of contestants are angry of you. GYUS, YOU ARE SUCH A SLUTS.

• -47

By ACCOUNT_FOR_BAD_ROUNDS, 3 months ago,

Given $a_1, \ldots, a_n$, $0 \leq a_i < 2^{k}$. We want to find $1 \leq i_1 < i_2 < \ldots < i_T \leq n$, s. t. $a_{i_1} \oplus \ldots \oplus a_{i_T} = 0,\ T \geq 1$. This is well known problem, which can be solved in $O(k^2)$ with Gaussian Elimination technique ($O\left(\frac{nk^2}{w} + \frac{k^3}{w}\right)$ to be more precise).

But what if we want to minimize $T$ (still assuming $T \geq 1$)? I only came up with smth like $O^*(n^k)$ by trying to bruteforce all subsets with size $\leq k$ and checking whether or not we can get xor sum $0$ from this subset.

Can we do better, maybe some $O(polylog(n,\ k))$? Would appreciate any help, thanks.

• +36