In this HackerRank Vim War problem solution, A war has broken down between Vim and Emacs. Gedit, being Vim’s ally, is captured by Emacs as a prisoner of war and it is up to Vim to rescue him by defeating Emacs.
For this task, Vim has to assemble an army of appropriate skills. He can choose a non-empty subset of soldiers from a set of N soldiers (numbered from 1 to N). Each soldier has some subset of skills out M of different skills (numbered from 1 to M). The skill-set of an army is the union of skill-sets of its constituent soldiers. To win the war, Vim needs to know how many different subsets of soldiers satisfy his skill-set requirement.
Problem solution in Java.
import java.io.*; import java.util.*; public class Solution { private static InputReader in; private static PrintWriter out; public static int mod = 1000000007; public static int N,M,K,s[]; public static long[] mult; public static void main(String[] args) throws IOException { in = new InputReader(System.in); out = new PrintWriter(System.out, true); N = in.nextInt(); M = in.nextInt(); s = new int[N]; for (int i = 0; i < N; i++) s[i] = Integer.parseInt(in.next(), 2); int goal = Integer.parseInt(in.next(), 2); if (goal == 0) { out.println(0); out.close(); System.exit(0); } int K = Integer.bitCount(goal); mult = new long[1<<K]; Arrays.fill(mult, 1); int w = ~goal; for (int i = 0; i < N; i++) { if ((w & s[i]) == 0) { int k = 0, a = 0; for (int j = 0; j < M; j++) if ((goal & (1 << j)) != 0) a |= ((s[i] >> j) & 1) << (k++); mult[a] = (mult[a] << 1) % mod; } } long[] m = rec(0, (1<<K)-1); long res = 0; for (int i = 0; i < 1 << K; i++) { long sign = (Integer.bitCount(i) & 1) == (K & 1) ? 1 : (mod-1); res = (res + sign * m[i]) % mod; } out.println(res); out.close(); System.exit(0); } public static long[] rec(int from, int to) { if (from == to) return new long[] {mult[from]}; int mid = (from+to) >> 1; long[] a = rec(from, mid); long[] b = rec(mid+1, to); long[] ret = new long[to-from+1]; for (int i = 0; i < a.length; i++) { ret[i] = a[i]; ret[i+a.length] = a[i]*b[i] % mod; } return ret; } static class InputReader { public BufferedReader reader; public StringTokenizer tokenizer; public InputReader(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream), 32768); tokenizer = null; } public String next() { while (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new StringTokenizer(reader.readLine()); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); } public int nextInt() { return Integer.parseInt(next()); } } }
Problem solution in C++.
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; const int Maxn = 100005; const int Maxm = 20; const int mod = 1000000007; int pw[Maxn]; int n, m; int has[1 << Maxm]; char str[Maxn][Maxm + 2], need[Maxm + 2]; int res; int main() { pw[0] = 1; for (int i = 1; i < Maxn; i++) pw[i] = 2 * pw[i - 1] % mod; scanf("%d %d", &n, &m); for (int i = 0; i < n; i++) scanf("%s", str[i]); scanf("%s", need); for (int i = 0; i < n; i++) { bool ok = true; for (int j = 0; j < m && ok; j++) ok = str[i][j] == '0' || need[j] == '1'; if (!ok) continue; int pnt = 0; int mask = 0; for (int j = 0; j < m; j++) if (need[j] == '1') mask |= (str[i][j] == '0') << pnt++; has[mask]++; } for (int i = 0; i < m; i++) for (int j = 0; j < 1 << m; j++) if (j & 1 << i) has[j ^ 1 << i] += has[j]; for (int i = 0; i < 1 << m; i++) if (__builtin_popcount(i) % 2 == 0) res = (res + pw[has[i]]) % mod; else res = (res - pw[has[i]] + mod) % mod; printf("%dn", res); return 0; }
Problem solution in C.
#include <stdio.h> #include <string.h> #include <stdbool.h> #define MAX 1048576 #define MOD 1000000007 #define clr(ar) memset(ar, 0, sizeof(ar)) #define read() freopen("lol.txt", "r", stdin) int n, m, r, pos[25], ar[MAX], temp[MAX], P[MAX], dp[MAX][2]; int Solve(){ int i, j, k, x, y, u, v, bitmask; clr(dp); for (i = 0; i < n; i++) dp[ar[i]][0]++; for (j = 1; j < 21; j++){ u = j & 1; v = (j - 1) & 1; for (i = 0; i < MAX; i++){ if (i & (1 << (j - 1))) dp[i][u] = dp[i][v]; else dp[i][u] = (dp[i][v] + dp[i + (1 << (j - 1))][v]); } } int res = P[n]; for (bitmask = 1; bitmask < MAX; bitmask++){ x = dp[bitmask][0]; if (x){ if (__builtin_popcount(bitmask) & 1) res = (res - P[x] + MOD) % MOD; else res = (res + P[x]) % MOD; } } return res; } int main(){ char str[25]; int i, j, k, x, lim; P[0] = 1; for (i = 1; i < MAX; i++) P[i] = (P[i - 1] << 1) % MOD; for (i = 0; i < MAX; i++) P[i] = (P[i] - 1 + MOD) % MOD; while (scanf("%d %d", &n, &m) != EOF){ for (i = 0; i <= n; i++){ x = 0; scanf("%s", str); for (j = 0; str[j]; j++) x = (x << 1) + (str[j] - 48); temp[i] = x; } r = n; n = 0, k = 0; memset(pos, -1, sizeof(pos)); for (j = 0; j < m; j++){ if (temp[r] & (1 << j)) pos[j] = k++; } lim = (1 << k) - 1; for (i = 0; i < r; i++){ x = 0, k = 0; for (j = 0; j < m; j++){ if (temp[i] & (1 << j)){ if (pos[j] == -1){ k = 1; break; } x |= (1 << pos[j]); } } if (!k) ar[n++] = x ^ lim; } printf("%dn", Solve()); } return 0; }