KS1 - Guddu and his Mother

help
1

Can anyone explain any approach for KS1 from the august long challenge
Problem link : CodeChef: Practical coding for everyone

2 Likes
2

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

3

link to the solution please.

4

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

1 Like
5

worst explanation bro . you explained for only one index

1 Like
6

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

2 Likes
7

Fully documented (but not proof read!) solution here.

3 Likes
8

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

1 Like
9

yeah but he cant give such kind of partial answer though

10

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

Link to my solution

21 Likes
11

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
12

You must’ve used 2 loops to calculate the sum of distance of all pairs.

3 Likes
16

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).

18

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
19

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. :slight_smile:

1 Like
20 
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
21

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. :slight_smile:

1 Like
22

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

1 Like
23

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
24

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