How to solve CLONEME(JUNE17) for 30 and 100 pts?

general
, ,
21

@ash_king_1 Can you please elucidate your approach? Why are you taking the modulus with 3?

22

@bansal1232 taking modulus is just a way of mapping the number, I mean you could take mod with any prime number. for example, 1 is mapped to 1, 2 is mapped to 2 3 is mapped to 0 and so on. And when we sum the range if the sums are not closed than 3 we can simply discard them.

23

I actually have similar solution with you mate, except I used hashing (P^i * a[i]) to check for similarity, same with persistent tree. Used two primes for hashing to lessen clash, see my solution

24

But how could you able to avoid collision? And what will happen if I assume any other number rather than 3?

25

Please use proper Latex format for Mathematics. It’s being cumbersome to comprehend your approach without proper formatting.

26

There is only one mismatch, so you can binary search the mismatch while you go down the trees.

1 Like
27

@bansal1232 yes I am not avoiding collision that’s why I am getting tle, what I am doing is if let’s say the difference is more than or equal ‘3’ the 2 subarrays definitely differ by more than 1 element and if it’s less, then I am just sorting and comparing the subarrays. It only works for 2nd subtask.

28

Hey, which part of my answer couldn’t you comprehend?

29

Hey, @sinus_070, I understood the majority part of the solution, but can you explain a bit more as to how, you did the last part of your solution?
“You can do this offline using seg/fenwick tree, by sorting the queries with respect to the values for whose position is to be found.”

Lets say the array is [1,3,2,4,3,4].

Query is : L1 = 1, R1 = 2 and L2 = 5 and R2 = 6
So, ranges are {1,3} and {3,4}, Now {1,4} will mismatch when I sort these subarrays, and now I am supposed to check their indices, how am I supposed to do this?
Are you referring to Binary Search in an MST?

30

So I need p(3) in [1,2] and p(4) in [5,6]. I have two queries of (p(v) in [l,r]). Now I sort {v,l,r} w.r.t ‘v’. Before I answer each query {v,l,r}, I update all 'i’s with 1 in the segtree (which was initially filled with 0s) where ai<v. So, when I get a query(v,l,r), I just need sum(l to r) in the segtree, this will give me the number of elements < ai, so you get the position.

For p(3) in [1,2], I’d have updated all 'i’s with 1 where ai <3. So I get 1+0.
So for p(4) in [5,6], it would be {1,1,1,0,1,0}. So, when I need sum in [5,6], I get 1+0.

31

@abdullah768 You cannot ignore overlapping parts.

1 2 3 4 5

For this array, let the query be

1 4 2 5

If you ignore the overlapping parts and just check 1 & 5, you have one mismatch and the answer is YES but in reality the answer is NO.

32

@abx_2109 I have tried the same approach as you have described but still I am getting WA. Can you please look into my


[1]. It would be of great help.


  [1]: https://www.codechef.com/viewsolution/14267731
33

Finally found the reason, and it is the silliest one ever. I was printing “N0” instead of “NO” and it led to all those 10 WAs. I need to be careful next time about this.

34

@ista2000
for checking mismatch of one element.

first I am dividing subarray into two parts and compare both subarray.

if both subarray are having different hash value means both of them

having atleast one different element in each subarray so ans = “NO”

else if one of them having different hash

one having different hash value, I will check further after

dividing that subarray into two parts.

1 Like
35

Hey man why you did this in last part -> Now your job is to check if position of 'a' in l1 to r1 is same as 'b' in 'l2' to 'r2'. ?

36

I made a video editorial on this problem here:

Cheers :slight_smile:

1 Like