Doubt in Sliding Window Median CSES problem

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

Hello everyone, I am trying to do Sliding Window Median problem from CSES. I have thought of multiset approach which is pretty close to one of its solutions and wrote this peice of code.

My Code

int l=0, r;
for(r=0;r<n;r++) {

    if(!up.empty() && *up.begin() <= a[r]) {
        up.insert(a[r]);
    }
    else {
        low.insert(a[r]);
    }
    
    if(up.size() > low.size()) {
        low.insert(*up.begin());
        up.erase(up.begin());
    }

    if(up.size()+1 < low.size()) {
        up.insert(*low.rbegin());
        multiset<int>::iterator itr = low.end();
        itr--;
        low.erase(itr);
    }
    
    if(r >= k-1) {
        
        cout << *low.rbegin() << " ";
        if(!low.empty() && low.count(a[l])) {
            low.erase(low.find(a[l]));
        }
        else if(!up.empty() && up.count(a[l])) {
            up.erase(up.find(a[l]));
        }
        l++;
    }
}
cout << "\n";

When I ran it on larger test case, it is taking this much time.

real    0m50.343s
user    0m50.003s
sys     0m0.195s

And, on the running the USACO solution, following same approach.

USACO solution

void ins(long val) {         // insert val into sets
    long a = *low.rbegin();  // current median
    if (a < val) {
        up.insert(val);
        if (up.size() > M / 2) {
            low.insert(*up.begin());
            up.erase(up.find(*up.begin()));
        }
    } else {
        low.insert(val);
        if (low.size() > (M + 1) / 2) {
            up.insert(*low.rbegin());
            low.erase(low.find(*low.rbegin()));
        }
    }
}

void er(long val) {  // erase from sets
    if (up.find(val) != up.end()) up.erase(up.find(val));
    else low.erase(low.find(val));
    if (low.empty()) {
        low.insert(*up.begin());
        up.erase(up.find(*up.begin()));
    }
}
low.insert(arr[0]);
for (int i = 1; i < M; i++) ins(arr[i]);
cout << *low.rbegin() << " ";
for (long i = M; i < N; i++) {
    if (M == 1) {
        ins(arr[i]);
        er(arr[i - M]);
    } else {
        er(arr[i - M]);
        ins(arr[i]);
    }
    cout << *low.rbegin() << " ";
}

It is taking this much time.

real    0m1.396s
user    0m1.178s
sys     0m0.214s

Now, I am not able to understand that why the time taken is increasing so drastically, even though the complexities are same. I can share the complete code also if it would help. Thanks

Comments (2)

Write comment?

sammyuri

6 months ago, # |

+11

The issue here is low.count(a[l]) and up.count(a[l]). The time complexity of count in a multiset is I believe $$$O(log(n) + k)$$$, where $$$n$$$ is its size and $$$k$$$ is the number of elements it counted. So if the multiset entirely consists of one repeated value and you count that value, the time complexity is actually $$$O(n)$$$ and the algorithm as a whole runs in $$$O(n^2)$$$ rather than the intended $$$O(n log(n))$$$.

You can replace low.count(a[l]) with low.find(a[l]) != low.end() (same for up) and it should pass.

→ Reply

Surge226

5 months ago, # ^ |

Oh, I did not know that. Thanks a lot for helping sammyuri.

Surge226's blog