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! ^ ^

https://codeforces.me/contest/2013/problem/C

Hi everyone,
I’m trying to solve the problem using a recursive approach, but I’m running into issues. My iterative solution works perfectly and gets accepted, but when I try to implement it recursively, the solution doesn’t behave as expected.

I suspect there might be an issue with how I’m handling the recursion termination or updating the string in the recursive calls, but I’m not sure.

Here’s the iterative solution that works.

Here’s the recursive solution that I’m struggling with:

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

int f(string &s1, string &s2, int i, int n, bool first) {
    if ((s1.size() + s2.size()) > n or (i >= (2 * n)))
        return -1;
    cout << "? " << s1 + s2 << endl;

    int check;
    cin >> check;
    if (first) {
        if (check) {
            s2 = s1 + s2;
            return 1;
        } else {
            if (s1 == "0") {
                s1 = "1";
                return 1 + f(s1, s2, i + 1, n, first);
            } else {
                return -1;
            }
        }
    } else {
        if (check) {
            s1 = s1 + s2;
            return 1;
        } else {
            if (s2 == "0") {
                s2 = "1";
                return 1 + f(s1, s2, i + 1, n, first);
            } else {
                return -1;
            }
        }
    }
}

void tTestCase() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        string s = "";
        int i = 0;

        while (i < (2 * n) and i >= 0) {
            string t = "0";
            int temp = f(t, s, i, n, true);
            if (temp <= 0)
                break;
            i += temp;
        }
        while (i < (2 * n) and i >= 0) {
            string t = "0";
            int temp = f(s, t, i, n, false);
            if (temp <= 0) {
                break;
            }
            i += temp;
        }
        if (s.size() != n)
            s = s + "1";
        cout << "! " << s << endl;
    }
}

void solve() { tTestCase(); }

int main() { solve(); }

Could someone help me debug this and point out what might be going wrong? I’d appreciate any guidance to fix the recursive approach while keeping the logic consistent with the iterative one.

Thanks in advance!