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

general
, ,
21

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

22

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

1 Like
23

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

24

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

25

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?

26

I used persistent segment tree:
for 30 pts i had solution with complexity O(N * logN * logN)
https://www.codechef.com/viewsolution/14173108
for 100 pts i optimized previous solution for O(N * logN)
https://www.codechef.com/viewsolution/14173831

27

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.

28

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

29

@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
30

I got tle in subtask 3 using my q*(logn)^2 approach … i already asked a question why is it so but i guess nobody could tell … if anyone her could help me to tell why tle in this aproach.

Link to my question thread : https://discuss.codechef.com/questions/101657/why-does-my-qlogn2-solution-gives-tle-in-cloneme

31

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.

32

@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
33

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'. ?

34

Hey guys,

I wrote an editorial of this problem on my blog.

Please take a look, and give me a feedback. I really need it.

Thanks everyone and Codechef!

35

Is there any solution which does not depend on probability of collision?

36

I made a video editorial on this problem here:

Cheers :slight_smile:

1 Like