Problem Name: Wormholes (ZCO12002); Refer to description for more details

Problem Statement: CodeChef: Practical coding for everyone.

I have already solved the problem using a different approach by creating my own function for lower and upper bound but when I am using the in-built function lower_bound() and upper_bound() defined in the C++ STL library I am getting WA in the last test-case only.

Below is the function which computes the minimum time as asked in the problem statement:

static ll_t compute_minimum_time(const std :: vector <std :: pair <ll_t, ll_t>> & contest_schedule, std :: vector <ll_t> & wormhole_open_time, std :: vector <ll_t> & wormhole_close_time) {

    std :: sort(wormhole_open_time.begin(), wormhole_open_time.end());
    std :: sort(wormhole_close_time.begin(), wormhole_close_time.end());

    ll_t min_time = 1e10;

    for(const auto & schedule: contest_schedule) {
        std :: vector <ll_t> :: iterator t1 = std :: upper_bound(wormhole_open_time.begin(), wormhole_open_time.end(), schedule.first);
        if(t1 == wormhole_open_time.begin()) {
            continue;
        }
        // t1 = wormhole_open_time.begin() + (t1 - wormhole_open_time.begin()) - 1;
        --t1;
        std :: vector <ll_t> :: iterator t2 = std :: lower_bound(wormhole_close_time.begin(), wormhole_close_time.end(), schedule.second);
        if(t2 == wormhole_close_time.end()) {
            continue;
        }
        min_time = std :: min(min_time, 1 + ((*t2) - (*t1)));
    }
    return min_time;
}

If you want to refer to the whole source-code then go to: Full Source-Code.

I am looking for the test-cases where my code will fail as it is failing to produce AC in the very last given case. Moreover, I would appreciate it, if someone can tell me what and where is the bug in my program in detail so that I don’t create the same bug in the future.

Thanks

Typo in line 37.

1 Like

Ya solved it thanks.