Luffy_18's blog

Help Needed: Codeforces Round 973 (Div. 2) D. Minimize the Difference
By Luffy_18, history, 8 hours ago, In English

problem.

Hi everyone,
I’ve been trying to solve problem D: Minimize the Difference from Codeforces Round 973 (Div. 2). I’ve spent quite a bit of time debugging my code, but I can’t figure out why it’s not working as expected. :(

Here’s what I tried to do:
I sorted the input intervals by their start times.

I used a priority queue to keep track of the active intervals within the current window.

As I slide the window from d to n, I:

-Remove intervals that are no longer in the range.

-Add new intervals that fall within the range.

I kept track of the window with the maximum and minimum number of intervals by checking the size of the priority queue.

However, it's giving WA on testcase 2.

Code:

#include <bits/stdc++.h>
using namespace std;

#define sp " "
#define newline cout << "\n"
#define yes cout << "YES"
#define no cout << "NO"
#define int long long
#define yesif(flag) cout << ((flag) ? "YES" : "NO")
#define all(a)  a.begin(), a.end()
#define pb(a) push_back(a)

typedef long long       ll;
typedef pair<int, int>  pii;
typedef pair<ll, ll>    pll;
typedef vector<int>     vi;
typedef vector<ll>      vll;
typedef vector<pii>     vpii;
typedef vector<pll>     vpll;
typedef map<int, int>   mii;
typedef map<ll, ll>     mll;
typedef set<int>        si;
typedef set<ll>         sl;

template<typename T> void sort_unique(vector<T> &vec){sort(vec.begin(),vec.end()); vec.resize(unique(vec.begin(),vec.end())-vec.begin());}
template<typename T> void scan(vector<T> &v){for(auto &i :v) cin >> i;}
template<typename T> void print(vector<T> &v){for(auto &i :v) cout << i << " ";}

#ifdef LOCAL
#include "debug.h"
#else
#define bug(...) 
#endif

void print(priority_queue<pair<int,int>,vector<pair<int, int>>, greater<pair<int, int>>> pq){
    while(pq.empty() == false) {
        cout << pq.top().first << " " << pq.top().second << endl; pq.pop();
    }
}
void tTestCase() {
    int t;
    cin >> t;
    while (t--) {
        int n, d, k;
        cin >> n >> d >> k;
        vpii points;
        for (int i = 0; i < k; ++i) {
            int a, b; cin >> a >> b;
            points.push_back({a, b});
        }   
        sort(all(points));

        bug(points);
        priority_queue<pair<int,int>,vector<pair<int, int>>, greater<pair<int, int>>> pq;
        int indx = 0, res1 = 0, res2 = 0, temp1 = 0, temp2 = INT_MAX ;

        for (int i = d; i <= n; ++i){
            
            while(pq.empty() == false and pq.top().second < (i - d + 1)){
                // if(!pq.empty())
                  pq.pop();
            }

            while(indx < k and   points[indx].first <= i and points[indx].second >= (i - d + 1)) {
                   pq.push(points[indx]);
                indx++;
            }   

            int sz = pq.size();
            bug(sz);
            if(sz > temp1) {
                temp1 = sz;
                res1 = i - d + 1;
            }
            if(sz < temp2) {
                temp2 = sz;
                res2 = i - d + 1;
            }

        }
        cout << res1 << " " << res2;

        newline;
    }
}

void solve() { 
    tTestCase(); 
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();

    return 0;
}

If anyone could kindly review my code and point out what I’m doing wrong, I’d be immensely grateful! :)

Any feedback or suggestions to improve the implementation or debug this further would mean a lot. Thank you so much in advance for your time and help! ^ ^

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Luffy_18 (previous revision, new revision, compare).

→ Reply
»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Luffy_18 (previous revision, new revision, compare).

→ Reply
»
4 hours ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

The link for the problem leads to a different one (probably the contest ID is wrong)

Edit: The name of the problem is wrong, not the link

→ Reply
  • »
    »
    a moment ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I sincerely apologize for the oversight; I mistakenly typed 2014 instead of 2013.

    → Reply
»
50 minutes ago, # |
  Vote: I like it +1 Vote: I do not like it

The issue is that the priority queue is sorted by decreasing index of the left bound. That means that if the intervals are $$$(1,4)$$$ and $$$(2,3)$$$, when $$$i=4$$$, the code will check the first one (since its left bound is smaller) and, as it overlaps with the range, won't remove it. That means that the second one won't be removed when it should and the number of overlapping intervals will be wrong.

The fix is simple: Replace while(pq.empty() == false and pq.top().second < (i - d + 1)) with while(pq.empty() == false and pq.top().first < (i - d + 1)){ and pq.push(points[indx]); with pq.push({points[indx].second, points[indx].first});. Now the priority queue will be sorted based on the right bound instead of the left one.

Fixed code
Bonus: Solution without a priority queue
→ Reply