Everule's blog

By Everule, history, 2 years ago, In English

I think that linear algebra, is a unnecessarily intimidating tool, to solve a problem I believe is far easier, and needlessly intimidates those without formal knowledge of linear algebra, which is a significant part of codeforces. I know I didn't. Therefore I want to show a step by step problem solving process that will lead to the concept of linear basis at the end, with no formal knowledge required.

We start with the elementary problem of linear basis. Given an array $$$A = [a_1, a_2, \ldots a_n]$$$, where $$$a_i \le 2^d$$$, Choose some subset of elements in $$$A$$$, and XOR them. Find the number of distinct elements you could make.

We start by using a simple dp. Let $$$X_i$$$ be the set of elements you could make with the first $$$i$$$ elements of $$$A$$$. Then its easy to see that $$$X_{i+1}$$$ contains $$$x$$$ and $$$x \bigoplus a_{i+1}$$$ for every $$$x \in X_i$$$. This is an $$$O(2^dn)$$$ algorithm, which is too inefficient.

We need to put some constraints on what $$$X_i$$$ looks like to make further progress. Let us assume $$$x,y$$$ are two elements in $$$X_i$$$. Then $$$x \bigoplus y$$$, must also be in $$$X_i$$$. This is because I can just take the elements I used to make $$$x$$$ and the elements I used to make $$$y$$$. The elements used in both simply cancel out. This means that the new set of elements used to make $$$x \bigoplus y$$$ is also a subset of $$$[a_1, a_2, \ldots, a_i]$$$, and therefore in $$$X_i$$$.

This provides us with an equally powerful converse.

Let $$$x$$$ be some element in $$$X_i$$$, and $$$y$$$ some element not in $$$X_i$$$. Then $$$x \bigoplus y$$$, cannot be in $$$X_i$$$, because if I could make $$$x$$$ and $$$x \bigoplus y$$$, I could make $$$x \bigoplus x \bigoplus y = y$$$.

Another way of thinking about this is, we want to attack $$$y$$$ with some set of elements in $$$[a_1, a_2, \ldots a_i]$$$, and kill it by getting it to $$$0$$$.

If I could kill $$$x$$$ and $$$y$$$, I can kill $$$x \bigoplus y$$$ by killing $$$x$$$ first, then $$$y$$$.

If I can kill $$$x$$$ but not $$$y$$$, neither can I kill $$$x \bigoplus y$$$, because I could already get $$$y$$$ to $$$x \bigoplus y$$$, but I couldn't kill that either.

I recommend spending a minute internalizing this.

Now let us try adding a new element $$$a_{i+1}$$$ to $$$X_i$$$ again. I check if I can make $$$a_{i+1}$$$. If I can, I can simply ignore it. If I cannot, then $$$x \bigoplus a_{i+1}$$$ for $$$x \in X_i$$$ is a new element too. So the size of $$$X$$$ will double. Obviously the set can double only $$$d$$$ times. This gives an algorithm in $$$O(n + d2^d)$$$ or $$$O(n + 2^d)$$$ depending on implementation.

if $$$2^d$$$ is large, this algorithm doesn't work either, as we cannot explicitly store $$$X$$$. This means we will need to compress $$$X$$$ in some way. To do that, notice that there are only at most $$$d$$$ elements that matter, because the ones that I ignored, may as well not have been there. So just storing the elements $$$[a_{i_1}, a_{i_2}, \ldots, a_{i_k}]$$$, that doubled the size of $$$X$$$, is enough. $$$X$$$ is just the set of the XORs of every subset of the compressed array.

While we successfully compressed $$$X$$$, we lost our ability to quickly check if $$$a_{i+1}$$$ is in $$$X$$$. We need to get that back.

We cannot guarantee much about the structure of $$$[a_{i_1}, a_{i_2}, \ldots a_{i_k}]$$$. So it is hard to see an algorithm that does this quickly. However it is important to notice that its not the elements itself that are important, but more so what is the set that is generated by the compressed elements. So any edits made to the array, is okay as long it doesn't change the produced set.

We now show that the set $$$[a_{i_1}, a_{i_2}, \ldots a_{i_k}]$$$ and $$$[a_{i_1} \bigoplus a_{i_2}, a_{i_2}, \ldots a_{i_k}]$$$, produce the same $$$X$$$. Or more generally, I can take any element, and xor it with some other element, and it will produce the same set $$$X$$$. This is easy to prove, because if I was using $$$a_{i_2}$$$ in the first set, I use the first and second element in the second set. If I was using both $$$a_{i_1}$$$ and $$$a_{i_2}$$$, then I just need the second element. It is equally good.

While this is enough to solve the given problem, it doesn't do the idea enough justice. In fact, any invertible XOR transformation from $$$[a_1, a_2, \ldots, a_k]$$$ to $$$[b_1, b_2, \ldots, b_k]$$$ will produce the same set.

A XOR transformation is one where $$$b_i$$$ is the XOR of $$$a_j$$$ for all $$$j$$$ in some subset of $$$1,2,3,\ldots, k$$$. An invertible XOR transformation, is one where there exists some XOR transformation from $$$b$$$ back to $$$a$$$.

Let $$$X_a$$$ be the set of elements that are produced by $$$[a_1, a_2, \ldots, a_k]$$$ and similarly define $$$X_b$$$. Then because $$$b_i$$$ belongs to $$$X_a$$$ by definition, every element of $$$X_b$$$ also belongs to $$$X_a$$$, implying $$$X_b \subseteq X_a$$$. But as the operation is invertible, we can similarly argue that $$$X_a \subseteq X_b$$$. This is only possible if $$$X_a = X_b$$$.

Any set of the smallest size that produces $$$X$$$ is a XOR basis, and we can choose any basis of $$$X$$$ we want.

Let us now ask ourselves, what do I want my basis to look like. If some element had a "unique" bit, it would be easy to check if the element should be added to make $$$y$$$. I just need to see if the unique bit exists in $$$y$$$. In fact, we can do this. Let us look at the bits in decreasing order.

If no element has this bit set, we can ignore this bit. If there is already just one element with this bit set, its good already. If there are more than one, we just pick any element, and XOR it with all the other elements with this bit set to make this element the only element with this bit set.

Now since we know if this element is included, by checking the unique bit, we know when to XOR $$$y$$$ with this element. Now we need to check if the new $$$y$$$ can be made from the other elements of the basis. The other elements form a smaller basis, and we can repeat the process, and its trivial to check in a basis with only $$$0$$$. Therefore inductively we have found an efficient, $$$O(poly(d))$$$ way to check if $$$y$$$ is in the basis.

I will leave optimizing this to $$$O(d)$$$ as an exercise, as my goal was to explain the conceptual underlying forces that allow the algorithm to work.

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you use the same explanation for ternary XOR (carry-less addition)?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +75 Vote: I do not like it

    The article basically reinvents Gaussian elimination without referring to it explicitly. The same reasoning can be used to explain basis construction in any vector space, except for you'd need to use

    $$$[a_{i_1}, a_{i_2}, \dots, a_{i_k}] \to [a_{i_1} + k a_{i_2}, a_{i_2}, \dots, a_{i_k}]$$$

    instead of $$$a_{i_1} \oplus a_{i_2}$$$ and say "unique non-zero element" instead of "unique bit"...

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, I get that it's still a reduced version of the theory of linear algebra in this specific case and a more educational/explainable way. That's why I'm asking about extending, to keep the educational aspect.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I use the fact $$$Z_2$$$ has characteristic 2 freely, however with only slight modifications, you can prove that this works for all vector spaces $$$F^n$$$.

»
2 years ago, # |
  Vote: I like it +93 Vote: I do not like it

Great job! This is a very simple concept that is usually hidden behind way too much math jargon. I'm not saying math is bad, but this is a beginner friendly topic and not all beginners on a CP site know math. I don't think I've seen any explanations accessible to small schoolboys till now.

Anyways here's something I'd like to add, the magic algo:

for(auto& i : basis)
	x = min(x, x^i);
if(x)
	basis.push_back(x);

x will become the smallest value you can get by xor-ing x with values that can be represented using that basis. In particular, if x = 0, then we could represent this number before and there is no need to add it to the basis. This short algo works the same way — every number will have some unique bit others don't but I will not rigorously prove it here.

And of course, there must be some exercises.

https://atcoder.jp/contests/abc141/tasks/abc141_f

https://atcoder.jp/contests/abc236/tasks/abc236_f

https://codeforces.com/problemset/problem/1101/G

https://atcoder.jp/contests/agc045/tasks/agc045_a

https://codeforces.com/problemset/problem/1100/F

https://atcoder.jp/contests/abc223/tasks/abc223_h

https://codeforces.com/problemset/problem/895/C

https://codeforces.com/problemset/problem/959/F

https://codeforces.com/contest/587/problem/E

...

There is a cf problem were you have n nim piles, for i-th pile it is either of size a_i or b_i with equal probability. What is the probability of you winning? Unfortunately I can't find it anymore.

This topic is very common so there should be a million more problems, but I am too lazy so I request other people to share.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    There is a cf problem were you have n nim piles, for i-th pile it is either of size a_i or b_i with equal probability

    I think you are talking about this problem

»
2 years ago, # |
  Vote: I like it +22 Vote: I do not like it

LOL, man i also write the article with this header in russian. But I didn't publish it because it didn't work out very well. Thank you for doing well what I once thought about :)

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone give a hint for the exercise with $$$O(d)$$$, please? I can't solve it faster than $$$O(d^3 / 64)$$$.

»
22 months ago, # |
Rev. 5   Vote: I like it +8 Vote: I do not like it

nice blog, i would like to share Benq presentation (from usaco.guide)related to xor basis https://drive.google.com/drive/folders/1Ll8EuA3p64JLmzImfQu5qiWvc6_QTa0E which is very beginner friendly and also have non linear algebric code for finding xor basis (like kostia comment)