ACCOUNT_FOR_BAD_ROUNDS's blog

By ACCOUNT_FOR_BAD_ROUNDS, history, 3 months ago, In English

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.

Full text and comments »

 
 
 
 
  • Vote: I like it
  • -47
  • Vote: I do not like it

By ACCOUNT_FOR_BAD_ROUNDS, 3 months ago, In English

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.

Full text and comments »

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