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.
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…
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
Something might be wrong in your calculation bcoz bitset allows to make only one binary search in this case O(10^5) and it then directly goes to print answer.
I think it might be 0.36 sec
@anushi Nope. It’s 36 seconds. Observe that in the worst case, you are using O(N*logN) per query. So It’s O(Q*N*logN). The only advantage in your solution is that you are breaking the loop if you find mismatches which are greater than 2. So that gives some optimization. But in the given test, both the sub arrays are same. So no mismatches so your code runs till the length of given subarrays. So O(N) per query.
You can check your code with given test to see your self.
See the optimization is done using bitset and in this test case it for loop runs only once & it then prints the answer.
If you have any doubt in how many times the loop has run you can put a counter & check its value!
Here ans is number of mismatches you are calculating in the loop. You are breaking the loop if it’s greater than or equal to 2. But in the given test, this never happens. Infact, answer if always 0. i.e “YES” always. So you will run from l to r for each query. which is O(Q.N) in total. And this solution(\approx 10^{10} operations) can’t run in 2 seconds.
Yes the loop runs for all l to r but see that just after loop there is one if condition and u can say that loop is effective only for i=l for other times it is just not doing anything that is why it don’t add to complexity.Specially it can’t be O(nlogn) bcoz for that each time loop needs to do a binary search which is not the case.
Well, leave about logN part, atleast you accepted that it’s O(N) per query. What I am saying is, O(Q*N) itself is very high to pass in 2 seconds. And it’s taking nearly 36 seconds to run.
Your input is not even worst case it is the best case in fact in which complexity is only O(Q*log(N)) which can easily be obtained in 2sec but u r getting it in 36 sec.
Make sure that the time for giving input is not counted.
Also, my submission passed in 1.03 sec which is not just around the constraints & I don’t think that code chef test cases don’t have q=10^5 & n=10^5 so for any case with this q and n yours input was the best! so if were the case I would have got TLE
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.
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
