I met a strange issue when I solve codechef problem Lowest Sum.

There is area of codes to calculate the numbers of pair(i,j) which sum(a[i] a[j])<X, the idea is to enumerate each a[i], accumulate the numbers which smaller than X-a[i] in vector b. there are two ways to find the number smaller than X-a[i] in vector b:

1. O(n):

for(int i=0; i<K&&mid-a[i]>=b[0]; i  ) {
    int j=K-1;
    while(j>=0 && mid-a[i]<b[j]) {
        --j;
    }
    ans =j 1;
}

2. O(logn)

for(int i=0; i<K&&mid-a[i]>=b[0]; i  ) {
    auto it = upper_bound(b.begin(), b.end(), mid-a[i]);
    ans  = it-b.begin();
}

O(logn) should be faster than O(n), but O(n) can passed within 2s and O(logn) TLE. What's the reason? Thanks in advance.

The code for your reference:

#include <bits/stdc  .h>
using namespace std;
using ll = long long;
int T, K, Q;
int main() {
    scanf("%lld", &T);
    while(T--) {
        cin >> K >> Q;
        vector<ll> a(K), b(K);
        for(int i=0; i<K; i  ) {
            scanf("%lld", &a[i]);
        }
        for(int i=0; i<K; i  ) {
            scanf("%lld", &b[i]);
        }
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        
        while(Q-->0) {
            int qu;
            scanf("%d", &qu);
            
            ll low = a[0] b[0];
            ll high = a[K-1] b[K-1];
            ll ans = high;
            while(low<=high) {
                ll mid = (low high)/2;
                int cnt = 0, j=K-1;
                for(int i=0; i<K&&mid-a[i]>=b[0]; i  ) {
                    /*
                    // can pass within 2 seconds
                    while(j>=0 && b[j]>mid-a[i]) j--;
                    cnt  = j 1;
                    */
                    
                    // TLE 
                    auto it = upper_bound(b.begin(), b.end(), mid-a[i]);
                    cnt  = it-b.begin();
                    
                }
                if(cnt>=qu) {
                    ans = mid;
                    high=mid-1;
                }else {
                    low=mid 1;
                }
            }
            printf("%lld\n", ans);
        }
    }
    return 0;
}

CodePudding user response：

The "code for reference" initializes j only once outside the i loop. Thus, if uncommented, the "O(n)" version actually looks like:

int j=K-1;              // <----------- HERE
for(int i=0; i<K&&mid-a[i]>=b[0]; i  ) {
    //int j=K-1;        // <----------- NOT HERE
    while(j>=0 && mid-a[i]<b[j]) {
        --j;
    }
    ans =j 1;
}

This gives an amortized O(1) runtime for the inner loop, because j can be decremented at most K times. Compared to the O(log K) for the TLE version.

Put it other way, the runtime of the entire for(int i...) loop is O(K) in the first case, versus O(K log K) in the second.