CLONEME Editorial (Unofficial)

editorial
, , , ,
21

@anushi

Observe this:

.....
while(q--){
   cin>>l>>r>>x>>y;
   .....
 
   for(i=l;i<=r && ans<2;i++){
      .....
   }
}

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.

2 Likes
22

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.

for(i=l;i<=r && ans<2;i++){
if(bit[a[i]]){
…
bit[a[i]]=false;
…
}
}

23

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.

3 Likes
24

Hey dear! Can you please tell how you generated the test case?? Thanks! :slight_smile:

25

@vijju123 With the attached generator.

26

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

27

Range trimming is only for checking values till that we running loop from l to r but while calculating rank you have to consider full range

28

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.

29

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

30

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

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
32

Yeah that would be a cool way.