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! ^ ^
Auto comment: topic has been updated by Luffy_18 (previous revision, new revision, compare).
Auto comment: topic has been updated by Luffy_18 (previous revision, new revision, compare).
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
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))withwhile(pq.empty() == false and pq.top().first < (i - d + 1)){andpq.push(points[indx]);withpq.push({points[indx].second, points[indx].first});. Now the priority queue will be sorted based on the right bound instead of the left one.An alternative way to solve the problem is to count the number of intervals that start and end on each index, and then use that to count the number of intervals overlapping each range.
We'll have two arrays $$$l$$$ and $$$r$$$ of size $$$n+1$$$. For each interval, we will add 1 to $$$l[a]$$$ and $$$r[b]$$$.
Then, we'll use a variable $$$c$$$ to count the number of intervals overlapping the current range. First, we'll set it to the sum of all $$$l[i]$$$ for $$$i<d$$$ minus the sum of all $$$r[i]$$$ for $$$i<d$$$, which is the number of intervals that start before and end after $$$d$$$. For each $$$i$$$, we add $$$l[i]$$$ to $$$c$$$, because these are the new intervals that overlap, and, at the end of the loop, subtract $$$r[i-d+1]$$$, because these are the intervals that won't overlap with any range after the current one.
Instead of the top of the priority queue, $$$c$$$ will be the number of overlapping ranges each time.