Think whether or not binary search could be useful for this exercise. Note that there is also a linear time complexity solution which is similar to yours but avoids useles increments of j.
Basically j 's value at the i-th iteration will be greater than or equal to j's value at the (i-1)-th iteration, so instead of setting j = i you can keep the prevoius value of j. In this way both i and j are incremented at most N times, having a linear time complexity.
Your suggestion helped me a lot. But also here the problem is that the same error message: Execution timed out, occurs at subtask 4.
It can’t be because of the time complexity.
Does anyone know why this error message keeps coming up and how to fix it?
The code fails on the “No additional limitations” subtask. I do not understand why.
I don’t quite get it. If I keep the previous value of j, isn’t it possible that I skip a pair whose difference is smaller than D?
For example:
6 100
120 200 210 250 300 400
for(int i = 0, j = 1; i < N-1){
diff = p[j] - p[i];
if(diff >= D || j >= N){
i++;
}else{
j++;
count++;
}
}
200 - 120 = 80 --> smaller j++ count++
i = 0 and j = 2 and count = 1
210 - 120 = 90 --> smaller j++ count++
i = 0 and j = 3 and count = 2
250 - 120 = 130 --> bigger i++
i = 1 and j = 3
250 - 200 = 50 --> smaller j++ count++
i = 1 and j = 4 and count = 3
300 - 200 = 100 --> bigger/equal i++
i = 2 and j = 4
300 - 210 = 90 --> smaller j++ count++
i = 2 and j = 5 and count = 4
400 - 210 = 180 --> bigger i++
i = 3 and j = 5
400 - 250 = 150 --> bigger i++
i = 4 and j = 5
400 - 300 = 100 --> bigger/equal i++
i = 5 and j = 5
Count = 4
Expected = 6
When I increase j to 3, i remains 0. The difference between 250 and 120 is bigger than D, which means I increase i by 1. Then I compare 250 with 200. But I never actually compared 210 with 200, because I have already increased j to 250.
I still have a mistake in my thinking somewhere.
You are trying to count each good pair individually, but this approach is too slow because the number of “good-pairs” could be quadratic. Want you really need to do is: for each i find the smallest j such that P[j]-P[i] >= D, and update the current answer adding the new j-i-1 good pairs you just found ({i, i+1}, {i, i+1},…,{i,j-1}).
Like I said before the new j will be greater than or equal to the j of the previous iteration, so you don’t need to set j to i+1.