Not able to understand why this gives TLE

help
1

Problem Link: VCS Problem - CodeChef

Approach:
Both ignored and tracked is the intersection of the ignored and tracked array.
Both unignored and untracked = N - union_of_ignored_and_tracked.
Since ignored and tracked arrays are sorted, we can find the intersection and union in O(m+k)

Code:

#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;
const int REM = 1e9 + 7;

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << std::fixed;
    cout << std::setprecision(6);

    int t;
    cin >> t;

    while (t--) {
        int n;
        int m;
        int k;

        cin >> n >> m >> k;

        int arr[n];
        int ignored[m];
        int tracked[k];

        for (int i = 0; i < m; i++) {
            cin >> ignored[i];
        }

        for (int i = 0; i < k; i++) {
            cin >> tracked[i];
        }

        int inter = 0;
        int uni = 0;

        // Computing the intersection of ignored and tracked
        int i = 0;
        int j = 0;
        while (i < m && j < k) {
            if (ignored[i] < tracked[j]) {
                i++;
            } else if (ignored[i] > tracked[j]) {
                j++;
            } else {
                inter++;
                i++;
                j++;
            }
        }

        // Computing the union of ignored and tracked
        i = 0;
        j = 0;
        while (i < m && j < k) {
            if (ignored[i] < tracked[j]) {
                uni++;
                i++;
            } else if (ignored[i] > tracked[j]) {
                uni++;
                j++;
            } else {
                uni++;
                i++;
                j++;
            }
        }
        while (i < m) {
            uni++;
        }
        while (j < k) {
            uni++;
        }

        cout << inter << " " << n - uni << endl;;

    }

}
2

Hello there
You are not incrementing iterator i and j in the while loop which makes it non terminating loop(infinite loop).
Use this instead

while (i < m) {
    uni++;
    i++;
}
while (j < k) {
  uni++;
  j++;
}

Thanks

1 Like
3

Sorry my bad, just missed it!
Thanks :slight_smile: