He was talking about the underlying logic towards the solution, not the solution i guess
1 Like
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
21 Likes
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 : CodeChef: Practical coding for everyone
7 Likes
You must’ve used 2 loops to calculate the sum of distance of all pairs.
3 Likes
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.
5 Likes
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. 
1 Like
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.
1 Like
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.
1 Like
Got it. Thanks man, really appreciate your efforts in explaining.
1 Like
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.
7 Likes
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
1 Like
u can use a pair to store the numbers and the corresponding positions, then sort the array and maintain a frequency array. Now while counting the pairs to get all the permutations u will get a series (the positions need to be in ascending order for this).
My approach: CodeChef: Practical coding for everyone
Because when i==0 the value in the vector at 0 is 0 and the expression for calculating distance becomes 0 as we are doing multiplication with 0 . Hence to avoid that i guess.
See EG : 5 2 7
PREFIX ARRAY : 5 7 0
Now no elements are repeating so is answer 0 ? No right .
Thus if in prefix array we encouter 0 that means from index 0 till that index subarray is 0.( Length of subarray will be 3 hence ans+=v[i][j]{which is the index of 0 i.e 2 in this case}) . Final answer 2.
Hope this helps
@rakesh_54
3 Likes
Thanks a lot man ! understood it completely.
1 Like
In order to calculate the distance between the all pair you can keep track of index of last same element to find the current distance and the occurance of that element till now.
With basic hashing
It will go in just O (N) 
1 Like
I am describing tha same approach in different manner using Hashing in O (N) ; P