Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

2147483648's blog

By 2147483648, 4 years ago, In English

Given $$$a_1, \ldots, a_n$$$, $$$0 \leq a_i \lt 2^{k}$$$. We want to find $$$1 \leq i_1 \lt i_2 \lt \ldots \lt 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.

  • Vote: I like it
  • +36
  • Vote: I do not like it

»
4 years ago, hide # |
← Rev. 3  
Vote: I like it +84 Vote: I do not like it

Empty set

spoiler