Can anyone explain any approach for KS1 from the august long challenge

Problem link : https://www.codechef.com/AUG19B/problems/KS1

# KS1 - Guddu and his Mother

If a subarray has XOR 0 then there will be (length of subarray - 1 ) triplets.

link to the solution please.

First create the prefix XOR array then calculate the sum of distance of all pairs which having the same value ; P

worst explanation bro . you explained for only one index

i TRIED THAT APPROACH but i only got 50 points and tle in other testcases

He was talking about the underlying logic towards the solution, not the solution i guess

yeah but he cant give such kind of partial answer though

Consider the array: 1 5 2 7 6 3 5

**Step 1: Create a prefix xor array**

Your prefix xor array will be: 0 1 4 6 1 7 4 1

Started with 0 to map any upcoming zeros.

**Step 2: Map indexes of same prefix xor value**

1: 1, 4, 7

4: 2, 6

6: 3

7: 5

**Step 3: Calculate possible tiplets**

Between every pair of index (i, j) with same prefix xor value possible triplets = j - i - 1

so for xor **1** there are 3 pairs viz: **(1, 4), (1, 7) and (4, 7)** which will give 2, 5, 2 = 9 triplets and similary for xor **4** there is only one pair **(2, 6)** which will give 3 triplets

Hence, final answer is 9 + 3 = 12

See I wanted him to figure it out on his own but if u want a complete explanation here it is -

Firsty you calculate the prefix XOR array.

Eg. if array is 1 4 3 7 5 2 7.

Prefix xor array : 1 5 6 1 4 6 1

Now in this prefix xor array if 2 elements are same that means xor between these 2 array is 0.

So here 1 at 0th index and 1 at 3th index are same , so xor of 1 , 2 ,3 th elements of original array is 0. Hence xor of 4 3 7 is 0. Same for 5 2 7 and 4 3 7 5 2 7.

Now for each subarray having xor 0 you have length - 1 triplets.

So here length of subarrays are 3 , 3 , 6 so final answer is 2 + 2+ 5 = 9.

Now even after all this you will get TLE. To avoid TLE i appended each elements index in a vector with each vector having a key ( the key will be element itself).

Now for each vector having length more than 1 , I had to calculate distance between all pairs to calculate length of subarray. I had to do this in n complexity to avoid TLE. The formula was ( (index* value at index )- (n-index-1)*value at index.{This gave me length of subarrays. and finally no of triplets.}

Here is my soln : https://www.codechef.com/viewsolution/25825928

You mustâ€™ve used 2 loops to calculate the sum of distance of all pairs.

How can I do it with less than O(n^2) time complexity? Because with this approach I got only 50 points when I used two for loops(nested).

I stored indexes of elements of prefix array in seperate vectors with each element getting its own vector. Now for each vector that i got if the size of vector was more than 1 , it meant that element was present at atleast 2 places in prefix array. For all such vector iterate over them and for each index , ans = index * value_at_that_index - ( size of vector - index - 1 )* value_at_tht_index.

Thus in one iteration i was able to find distance between occurance of that element.

Thanks Sid.

Youâ€™re great. I am going to try implementing this in Java.

Although I thought using Hashmap in java but I couldnâ€™t set up the formula to get the lengths when using a hashmap.

```
for(i = 1, i < k, i++) {
if(i > 1)
temp += (vv[i] - vv[i-1] - 1) * (i - 1) + (i - 2);
cnt += (vv[i] - vv[0] - 1) + temp;
}
```

This is what Iâ€™ve done.

See if this help.

Yeah and dont forget to subtract n(n-1)/2 from this , as this is only giving distance between pairs , you have to subtract total number of pairs formed in oder to get number of triplets , as answer is lengthofsubarray - 1.

Got it. Thanks man, really appreciate your efforts in explaining.

Here is the explanation of this formula works :

Suppose an element is present at index 1 , 3 ,5 in prefix array.

So you want to find : (3- 1) + (5-1) + (5-3)

what do u see here , 1 is getting subtracted twice and added 0 times.

3 is getting subtacted once and added once.

5 is getting subtracted 0 times added twice.

So index*value - (n-index-1)*value.

https://www.codechef.com/viewsolution/25649739

the trick is-if the xor of elements of subarray of index starting from i and ends at k will be zero then u can find k-i triplets â€¦now optimise the approachâ€¦also u can view my solution