COOLCHEF EDITORIAL using binary search

Yeah so in worst case freq of all elements can be 2
So why won’t the complexity be
N/2 per query ?
log(2)+log(2) + … N/2 times

freq can be more than 2 also

But what about freq=2 ?

I think complexity is around log(n) only

Okay cool nice approch.
Even editorial was O(sqrt(n)) per query.
Yours is much more optimized.

2 Likes

So this approach is easy+less time taking+optimized

I appreciate your effort of making an editorial :slight_smile:

Yeah if u think so…
I will need time to understand it.

I just did with the motive of spreading nice approaches which can help somebody who doesn’t know sqrt decompostion

1 Like

You can check my code to understand it better

I know right

“After summation complexity will be around log2(n) per query”

8 Likes

Instead of motivating them, you should learn sqrt decomposition and even encourage them to do so
I don’t believe this approach is better.
I might be wrong.

1 Like

Consider a test case where the given n is even and there are n/2 unique elements all occur twice…i.e the array is [ 1 1 2 2 3 3 4 4 . . . . (n/2) (n/2) ]…and all q queries are [1,n], you can see that your approach will evaluate (n/2) keys with log(2) time for binary search, and thus even the complexity will be O ( q * n * log(2) ) for such test case. You were just lucky that your code was not tested for such case.

1 Like

I told him the same…
He was like there will be element with freq > 2 :frowning:

2 Likes

Please see the 2 optimization conditions in the code and editorial.Those 2 conditions got me from 60 to 100

I’ve benchmarked your code using the test case generated by this (as mentioned by the users above). It took 40.56 seconds. You can try running it yourself and see.

def COOLCHEF():
	N, Q = 3 * 10 ** 4, 3 * 10 ** 3
	B = 2

	print N, Q
	for x in xrange(N / B):
		for _ in xrange(B):
			print 1 + x, 
	print
	for _ in xrange(Q):
		print 0, 0, 0, N - 1

Note that the inputs are not even worst case. The actual solution will be at least 1000 (N: *10, Q: *100) times slower on worst case input.

As pointed out by @l_returns and @tejas_919, turns out you just got lucky that the test cases were so horrible.

6 Likes

I have learnt sqrt decomposition now

3 Likes

That’s really very nice. Good !!

I still can’t believe such solutions fetch 100 points on CodeChef. You don’t even have to think too much to find test cases to avoid such solutions, but as it turns out, there are none. All the test cases shouldn’t just be randomized, as that would have lots of elements with frequency 1, which defeats the actual purpose of the problem. This is some really lazy setting and testing.

1 Like