Im very excited about this blog, as it took me quite a lot of effort and scavenging through the internet to completely grasp the concept of this technique(That's probably because I have almost zero knowledge in Linear Algebra or I'm just plain dumb). So I feel like I genuinely conquered a challenge, and I really want to share it with someone. But there's no way my CP friends circle will believe it, they'll think I'm just trying to show off :P
So here I am, sharing it on CF. I also created a personal blog, so that if I ever feel like sharing something again(not only about CP), I can write a blog there. I also added this same post there, you can read it there if you prefer dark theme. I'll be pleased to hear any thoughts on the blog or if I can improve it in some way ^_^
Since it concerns Linear Algebra, there needs to be a lot of formal stuff going on in the background. But, I'm too much inconfident on this subject to dare go much deep. So, whenever possible, I'll try to explain everything in intuitive and plain English words. Also, this blog might take a while to be read through completely, as there are quite a few observations to grasp, and the example problems aren't that easy either. So please be patient and try to go through it all, in several sits if needed. I believe it'll be worth the time. In any case, I've written the solutions, codes, and provided links to their editorials(if available). I'll provide more details in the solutions tomorrow and put more comments in the codes, since I'm really tired from writing this blog all day.
Now, the problems that can be solved using this technique are actually not much hard to identify. The most common scenario involves: you'll be given an array of numbers, and then the problem asks for an answer by considering all the xor-sums of the numbers in all possible subsets of the array. This technique can also be used in some online-query problems: the problem can provide queries of first type instructing you to insert numbers in the array(_without removal_, I don't know how to solve with deletion of elements) and in-between those queries, asking for answers in separate queries of second type.
The whole technique can be divided into two main parts, some problems can even be solved by using only the first part(Don't worry if you don't understand them completely now, I explain them in details right below): 1. Represent each given number in it's binary form and consider it as a vector in the $$$\mathbbZ_2^d$$$ vector space, where $$$d$$$ is the maximum possible number of bits. Then, xor of some of these numbers is equivalent to addition of the corresponding vectors in the vector space. 2. Somehow, relate the answer to the queries of second type with the basis of the vectors found in Part 1.
Let me explain the idea in plain English first, then we'll see what the $$$\mathbbZ_2^d$$$ and vector space means. I'm sure most of you have already made this observation by yourselves at some point.
This is all there is to it. Transforming xor operations to bitwise addition modulo $$$2$$$ and, in some cases, vector addition in this way can be helpful in some problems. Let's see one such problem. Before that, let me explain in short what vector space and $$$\mathbbZ_2^b$$$ meant earlier. I apologize to any Linear Algebra fans, since I don't want to write formal definitions here to make things look harder than it is. I'll explain the idea of these terms the way I find them in my mind, kindly pardon me for any mistakes and correct me if I'm wrong.
So, what we've seen is that the xor-operation is equivalent to vector addition in a $$$\mathbbZ_2^d$$$ vector space. See how unnecessarily intimidating this simple idea sounds when written in formal math!
A few important properties of independent vectors and vector basis that we will need later on(I find these pretty intuitive, so I didn't bother with reading any formal proofs. Let me know in the comments if you need any help):
For a set of independent vectors, we can change any of these vectors by adding to it any linear combination of all of them, and the vectors will still stay independent. What's more fascinating is that, the set of vectors in the space representable by some linear combination of this independent set stays exactly the same after the change.
Notice that, saying all subsets of a set yeild non-zero xor is equivalent to saying all subsets of that set yeild different xor-sum. The the xor-sums of segments in the answer partition need to be independent vectors. This is the first of the two main observations.
I apologize for my terrible Linear Algebra knowledge. I would write this blog without using any of it if I could. I don't want to spread any misinformation. So please let me know in comments if you find any mistakes/wrong usage of notations.
I plan to write on Hungarian Algorithm next. There's just so many prerequisites to this algorithm. It'll be an enjoyable challenge to write about. I'd be glad if you can provide me some resource links in the comments to learn it from, though I already have quite a few.
But this is all just language, apart from that, thanks a lot. I never tried to learn Gaussian elim because it looked tough ( saw long codes everywhere, and couldn't understand without the correlation with Linear Algebra ). But now I feel it's so easy.
didnt understand a thing . imma newbie ... is it ok for beginners to not understand the first problem solution .. like i was able to code for problem 1 but it passed only 3 TC , failed at 4th test case
If we have to count the number of distinct integers that can be possible using OR over the set of the given elements. then can we solve this problem using gaussian elimination technique? How can we solve this problem?
as it is problem for ongoing contest can u plz help me with this after 1 day..the contest will be over till then..thanks in advance i am very much curious to know its solution that solves it in an optimal time.
DrSwad , -is-this-fft- in problem 5, Is the idea is like this, addition in a vector space is closure and x should be present in the given vector space. So to form a subsequence with xor sum equals to x, from non-basis vectors we have xor sum of the form (K xor x), and as addition is closure so it is possible to form vector of the form K from basis vectors?
Consider a case where all numbers (in space)of a given dimension have 1. Then we cannot find a basis (with size>1) for which a value could be responsible for that same dimension ( since all values of basis would have 1) so how to use atmost d numbers in basis?
1) "We will build the basis from the most significant bit down (like problem 3)" I understand that in this problem, we need to build the basis from the most significant bit down because we could have msb that is greater than > 65 and it wouldn't be algorithmically efficient to build it from lsb (harder to maintain which bits are set in mask). But do we really need to do same for problem 3? I have posted my doubts in comments below : -768724.
2) "You need a bitset or something like that to store basis this large". By large you mean that bitset for 65 small bits, right (and not 9592 bits bitset)? Because we only need to maintain this 65 small bits and one msb separately?
1) Generating basis vectors algorithm : Is it true that the bits for which basis are found will always be the same despite the order in which we insert vectors? And why so? I understand that the basis vectors can be different but will the bits position for which basis are found will be same?
3) In problem 3, why do we need to alter the definition "alter the definition of F(b). Instead of F being the first position with a set bit, let it be the last position with a set bit"? Can't we just calculate the maximum xor in the same manner as given in solution ( i.e going from highest bit to lowest bit) without changing the definition at all? What does changing the definition achieve if the basis bits position we are going to find will be the same (assuming my doubt 1 is true)?
1 and 3: The process of "basis building" here is called Gaussian Elimination. We have an independent set of vectors and we want to build a basis out of it. The main property here is that, we can mix up these vectors (i.e. xor them to each other in ANY way we want), and the span doesn't change. So we apply Gaussian Elimination, i.e. we are inserting all vectors into a matrix, and get it down to row echelon form.
Yes, just because I tried to find a counter test case and couldn't. What is mind-boggling is that the value of the vectors in the basis can be different and you still can get the XOR of all the possible subsets using these different bases.
You can exploit the fact that basis vectors are independent, so you can't get one of them using a linear combination of the others. That means if you didn't include a vector and then included it, the resulting value will surely change. So, you will have exactly $$$2^\textsz$$$ different values.
For problem 3, this approach can also work: after forming basis with the given n elements using the earlier mentioned implementation(where f(i) is the 1st position with set bit), we can just iterate from 2^21 to 0 and the first element which can be formed from the basis will be the answer. PS: Correct me if I'm wrong
I understand that the vector space generated by all the subsets of segments is the same as the one generated by the subsets of prefixes. It's also clear why every non-empty subset of segments in the final division should generate a different xor-sum.
I thought about it the whole day and here is what I came up with. whenever you create a basis the first number you push you in your basis is pref[n] i.e. the last prefix element. Now if the basis has size k, then you will push k-1 more elements in your basis but no matter how many elements you push into the basis the last prefix will always be pref[n] hence
the whole array will be divided. Intrinsically that is the reason why if all the elements of the array sum to 0 (xor-sum up I mean) then you will never be able to push pref[n] in the basis hence you will never be able divide the whole array into complete segments.
3a8082e126