CLONEME Editorial (Unofficial)

editorial
, , , ,
21

In this case ans will be 1 (since 1 element differ at pos 1).
So for ans=1 we have to check if there is any element in range l:r which lies in between these two and since there it is it should output NO.

22

Bcoz u have to consider whole range while calculating elements in mid.
And if you are calculating rank you have to take care to count only the elements less than the max value one but count all elemnts less than or equal to that min value one.Then only you will get AC

23

@anushi if BIT is not set, then we don’t continue with those operations. But, we are doing O(1) by checking the condition and the loop is of O(n). So, that is still O(n*q)

1 Like
24

This is an inefficient solution for given constraints…

However i need some help on my one of the solutions if anyone could. I did this by a q*(logn)^2 logic but that gave me tle in 3rd subtask, i tried to optimize the solution a lot but it didnt pass

Link to solution : https://www.codechef.com/viewsolution/14203109

Logic : I did it using persistent segment trees. i stored count of elements as well as hash value of them in the tree. Then using binary search and qry function(which returns cumulative hash uptil required position)i found 1st xth position for a,b c,d such that cumulative hash uptil that xth position doesnt match. and checked the cumulative hash of the values on the right side of this position. If they are equal then yes else no.

Even after loads of submissions i coudnt remove the tle by this logic but i really want to know reason for tle considering my friends q*(logn)^3 logic passed.
If anyone could tell me.

Later on i combined bs with qry and did in q*logn which passed

1 Like
25

Your solution will run quite fast on a randomised test case . But we can deliberately create test cases where your solution would take forever to run.

One of the possible hacks is

N = 10**5
Q = 10**5
hack = range(1 , N - 3 + 1)
hack += [N]*3
hack[1] = hack[2] = 1
print "1"
print N , Q
print ' '.join(map(str , hack))
for _ in range(Q):
    print 1 , N - 3 , 2 , N - 2

It is a test case in which , the first range freq[1] = 3 , freq[2…99997] = 1 and for the second range freq[1] = 2 , freq[2…99997] = 1, freq[100000] = 1 . I guess we can hack a lot of solutions using this test case.

Input file

2 Likes
26

How every one guessed this technique of hashing…??
I mean most of the solutions are based on the technique of raising the sum of elements to some power like 2,3/2,even 4…i mean is there any standard method of doing such question…Any one knows any links to learn about this hashing and all…cz i didnt heard about it until now…

27

Weak test cases are getting quite common here since last few long contests.

4 Likes
28

I find the concept of having public hacks (like they have in Codeforces Educational rounds) after contest ends . In this way we can have more robust test cases .

3 Likes
29

Yeah that would be a cool way.

30

@abx_2109: Could you provide more insight of your solution.How is taking sum of power 3/2 helping us?

31

Can someone please tell me what is wrong with my solution - https://www.codechef.com/viewsolution/14259973

I created a hash value corresponding to each range and if it was different for both ranges then I calculated values x from first range and y from second range that were mismatched and then checked their position

I just want to know what is wrong in my approach or possibly in my implementation

32

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!

1 Like