Search code examples
c++algorithmbinary-searchdivide-and-conquer

Codechef Wormholes: What's wrong with my logic?


I've been trying to solve this problem from Codechef. But there's something wrong with my logic that I'm unable to correct and I cannot wait for editorials to come up because the contest runs for many days (like 200 days).

My code:

#include <bits/stdc++.h>

using namespace std;

struct exam {int s,e;};

int main() {
    int n,x,y;
    scanf("%d%d%d",&n,&x,&y);

    exam ar[n];
    int v[x],w[y];

    for (int i = 0; i < n; ++i) scanf("%d%d",&ar[i].s,&ar[i].e);
    for (int i = 0; i < x; ++i) scanf("%d",&v[i]);
    for (int i = 0; i < y; ++i) scanf("%d",&w[i]);
    stable_sort(v,v+x); stable_sort(w,w+y);

    int mini = 1e6;

    for (int i = 0; i < n; ++i) {

        int *t1 = lower_bound(v,v+x,ar[i].s);

        if (*t1 > ar[i].s && t1 > v) --t1;
        if (*t1 > ar[i].s && t1 == v) continue;

        int *t2 = lower_bound(w,w+y,ar[i].e);

        if (t2 == w+y) continue;

        mini = min(mini,(*t2-*t1)+1);
    }

    printf("%d",mini);
    return 0;
}

And sadly this code doesn't pass two test cases:

Can anyone tell me what's wrong with my logic?


Solution

  • Change

    `if (*t1 > ar[i].s && t1 > v) --t1;
     if (*t1 > ar[i].s && t1 == v) continue;`
    

    To

    if (*t1 != ar[i].s) {
        if (t1 == v)
          continue;
        else
          --t1;
    }