Explain a Solution!

This might be a weird question to ask here , i don’t know the rules , but can anyone explain [https://www.codechef.com/viewsolution/25520022] (https://www.codechef.com/viewsolution/25520022) this solution :wink:

1 Like

It’s hard to decipher, but at first glance it doesn’t appear to be doing anything fundamentally different to the other solutions.

Lots of people are posting solutions and descriptions of approach here, so maybe that’s worth a read :slight_smile:

1 Like

i sorted the solution according to time then i got this one at top , though mine also got accepted(after a lot hard work :grin: ) in 0.11 seconds but this seem more optimized like only in 0.06 seconds :crazy_face:

1 Like

Basically, the answer is \sum\limits_{i} (len_{i} - 1) for all the intervals that have XOR sum equal to 0 (since every i \leq k \leq j of these intervals holds the equal XOR sum condition, but we can’t take k = i, so we will have len_{i}-1 for each one), so if we handle it like prefix sums, we would have:

prefix[i] = XOR(a_{1},\ldots,a_{i}) \rightarrow XOR(a_{i},\ldots,a_{j}) = XOR(prefix[j],prefix[i-1])

Also, let’s define prefix[0] = 0 to be able to consider the whole prefix until a certain index.

So, to count the number of intervals that have XOR sum equal to 0 that end in index R, we need all the i such that 0 \leq i < R and prefix[i] = prefix[R]. However, each i defines the interval (i+1,R) so the length of this segment is R - i. Thus, R contributes with:

contribution(R) = \sum\limits_{0 \leq i < R, prefix[i] = prefix[R]} (R - i) - 1
contribution(R) = \sum\limits_{0 \leq i < R, prefix[i] = prefix[R]} R - (i + 1)
contribution(R) = Q(0,R-1,prefix[R])\cdot R - \sum\limits_{0 \leq i < R, prefix[i] = prefix[R]}(i + 1)

Where Q(L,R,x) are the number of indices L \leq i \leq R such that prefix[i] = x.

If we mantain the sum of (i+1) for each value of prefix[i] = val in sm[val] and the number of such indices that hold in sz[val], we can transform the complete sum into:

contribution(R) = sz[prefix[R]]\cdot R - sm[prefix[R]]

That’s all the idea behind the solution :smiley:

It is hard to understand what the Code does , it is much harder to understand why ? :smile: