Two Sets

Problem Link 

In this problem, we must divide a set of numbers into two sets such that if number x goes into set A, then the number A – x must also be put into set a and similarly, if number x is put into set b, then the number b – x must also be put into set b. If we had to actually go about assigning numbers to either set A or set b and then checking if the conditions above have been met, it would take way too long. This is because for each number we have two choices: put it in set a or put it in set b. This yields a time complexity of O(2n) which easily TLEs with n <= 1e5. There are some numbers that can go in either set if both the numbers A – x and B – x exist. There are also some numbers that can only be placed in set A since the number A – x exists in the array but not B – x and the same goes for numbers that can only be placed in only set B. there are also number that can’t be put in set A or B since neither of the numbers A – x and B – x exist. In this case, the numbers can’t be split into two sets, so we just print -1 and exit. With this, we can make an important observation: if there’s a number a that can only be put in set A and a number b that can only be put in set B and the numbers A – a and B – a happen to be the same (or A - b and B - b happen to be the same) (let’s call this number y), then we can’t divide the numbers into two sets since y must be present in both of the sets All we need to do is check if this situation arises with the given set of numbers. We can do this using DSU. If a number x can only belong to A, then the number A - x can only belong to set A, so we draw an edge between A and x and A and A-x. Similarly, if a number x can only belong to B, then the number B - x can only belong to set B so we draw an edge between B and x and B and B - x. But if a number can be placed in both sets since both the numbers A - x and B - x exist, we draw an edge between x and A - x and x and B - x. Then all we need to do is check if nodes A and B are connected by some series of edges since this implies that some number along the chain must be added to both sets. We can do this by using a DSU to check if A and B are part of the same component.

Code

#include <iostream>

#include <vector>

#include <iostream>

#include <set>

#include <algorithm>

using namespace std;

struct DSU {

    vector <int> link, sz;

    DSU (int s) {

        link = sz = vector <int> (s+1);

        for (int i = 1; i <= s; i++) {

            link[i] = i;

            sz[i] = 1;

        }

    }

    int head(int x) {

        while (x != link[x])

            x = link[x];

        return x;

    }

    bool same(int a, int b) {

        return head(a) == head(b);

    }

    void unite(int a, int b) {

        a = head(a);

        b = head(b);

        if (a == b)

            return;

        if (sz[a] < sz[b])

            swap(a, b);

        sz[a] += sz[b];

        link[b] = a;

    }

};

vector <int> c;

int get_id(int x) {

    return lower_bound(c.begin(), c.end(), x) - c.begin();

}

int main() {

    int n, a, b;

    cin >> n >> a >> b;

    set <int> exists;

    vector <int> nums(n);

    c = vector <int> (n);

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

        int x;

        cin >> x;

        nums[i] = x;

        c[i] = x;

        exists.insert(x);

    }

    sort(c.begin(), c.end());

    c.erase(unique(c.begin(), c.end()), c.end());

    DSU dsu(n+5);

    vector <int> ans(n);

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

        int x = nums[i];

        bool f1 = false, f2 = false;

        if (exists.find(a - x) != exists.end())

            f1 = true;

        if (exists.find(b - x) != exists.end())

            f2 = true;

        if (f1 && f2)  {

            int id1 = get_id(x);

            int id2 = get_id(a - x);

            int id3 = get_id(b - x);

            dsu.unite(id1, id2);

            dsu.unite(id1, id3);

        } else if (f1) {

            int id1 = get_id(x);

            int id2 = get_id(a - x);

            dsu.unite(id1, n);

            dsu.unite(id1, id2);

        } else if (f2) {

            int id1 = get_id(x);

            int id2 = get_id(b - x);

            dsu.unite(id1, n+1);

            dsu.unite(id1, id2);

        } else {

            cout << "NO\n";

            return 0;

        }

    }

    if (dsu.same(n, n+1)) {

        cout << "NO\n";

    } else {

        cout << "YES\n";

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

            int id = lower_bound(c.begin(), c.end(), nums[i]) - c.begin();

            if (dsu.same(n, id))

                cout << 0 << ' ';

            else

                cout << 1 << ' ';

        }

        cout << '\n';

    }

}