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


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 << "ms\n";
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