HackerEarth Easy Sum Set Problem solution

In this HackerEarth Easy Sum Set problem solution In this problem, we define “set” is a collection of distinct numbers. For two sets A and B, we define their sum set is a set S(A,B) = {a+b|a relate to A, b relate to B}. In other word, set S(A,B) contains all elements which can be represented as sum of an element in A and an element in B. Given two sets A,C, your task is to find set B of positive integers less than or equals 100 with maximum size such that S(A,B) = C. It is guaranteed that there is unique such set.

HackerEarth Easy Sum Set Problem solution.

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

const int maxn = 100 + 5;
int n, m;
int a[maxn];
int c[maxn];

void chemthan() {
    cin >> n;
    assert(1 <= n && n <= 100);
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        assert(1 <= x && x <= 100);
        a[x] = 1;
    }
    cin >> m;
    assert(1 <= m && m <= 100);
    for (int i = 0; i < m; i++) {
        int x; cin >> x;
        assert(1 <= x && x <= 100);
        c[x] = 1;
    }
    vector<int> res;
    for (int i = 1; i <= 100; i++) {
        int ok = 1;
        for (int j = 1; j <= 100; j++) if (a[j]) {
            if (i + j > 100 || !c[i + j]) {
                ok = 0;
            }
        }
        if (ok) {
            res.push_back(i);
        }
    }
    static int d[maxn];
    for (int i = 1; i <= 100; i++) if (a[i]) {
        for (int j : res) {
            d[i + j] = 1;
        }
    }
    for (int i = 1; i <= 100; i++) assert(c[i] == d[i]);
    for (int i = 0; i < (int) res.size(); i++) cout << res[i] << " n"[i == (int) res.size() - 1];
}

int main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(0), cin.tie(0);
    if (argc > 1) {
        assert(freopen(argv[1], "r", stdin));
    }
    if (argc > 2) {
        assert(freopen(argv[2], "wb", stdout));
    }
    chemthan();
    cerr << "nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "msn";
    return 0;
}

Second solution

from collections import defaultdict
maxb = 20
n = int(raw_input())
assert 2 <= n <= 200000
v = map(int, raw_input().split())
assert all(0 <= x <= 1048575 for x in v)

acounts = [0 for __ in xrange(maxb)]
for x in v:
    for j in range(maxb):
        acounts[j] += (x>>j)&1

graph = defaultdict(list)
for i in range(n-1):
    a,b = map(int, raw_input().split())
    graph[a].append(b)
    graph[b].append(a)

ans = 0
p = [-1 for __ in xrange(n+1)]
q = [1]
p[1] = 0
for front in xrange(n):
    cur = q[front]
    for a in graph[cur]:
        if p[a] == -1:
            q.append(a)
            p[a] = cur

counts = [[]] + [[(v[i-1]>>j)&1 for j in range(maxb)] for i in xrange(1,n+1)]
for nid in xrange(n-1,-1,-1):
    node = q[nid]
    for a in graph[node]:
        if a == p[node]:
            continue
        for b in range(maxb):
            counts[node][b] += counts[a][b]
    ans += all(y == 0 or 0 < x < y for x,y in zip(counts[node], acounts))

print ans

coding problems solutions