In this post, we will solve 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 of M 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. Since the answer can be huge, print it modulo 10″ + 7.
Note: The chosen army’s skill-set must exactly match the skill-set requirement of Vim (i.e no extra skills must be present in the army’s skill-set than what is required).
Input Format
The first line contains N and M. the number of soldiers to choose from and the number of different skills possible respectively.
The next N lines contain M boolean characters each. If the jth character of the ¿th line is 1 , then the ith soldier possess the jth skill and if it is 0, then not.
The last line contains M boolean characters denoting the requirement skill-set of Vim where the jth character being 1 signifies that Vim wants the jth skill to be present in his final army and not, otherwise.
Output Format
Output in a single line the required answer, as explained above.
Sample Input
4 2
00
10
01
11
11
Sample Output
10
Vim War C Solution
#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("%d\n", Solve());
}
return 0;
}Vim War C++ Solution
#include <bits/stdc++.h>
#define TestBit(bits, x) ((bits & (1LL << (x))) != 0)
using namespace std;
typedef long long ULL;
ULL MOD = 1000000007;
ULL target;
int N, M;
vector<ULL> skills;
ULL Multiply(ULL a, ULL b)
{
a %= MOD;
b %= MOD;
ULL res = (a * b) % MOD;
return (res < 0) ? res + MOD : res;
}
ULL Power(ULL n, ULL e)
{
ULL res = 1;
while(e)
{
if(e & 1)
{
res = Multiply(res, n);
}
e >>= 1;
n = Multiply(n, n);
}
return (res < 0) ? res + MOD : res;
}
ULL counts[1048576] = {0};
ULL Solve()
{
for(int bit = 0; bit < M; bit++)
{
for(int mask = 0; mask < (1 << M); mask++)
{
if(TestBit(mask, bit))
{
counts[mask] += counts[mask ^ (1 << bit)];
}
}
}
ULL res = 0;
for(ULL mask = target; mask >= 0; mask--)
{
if((mask | target) != target)
{
continue;
}
ULL bits = target ^ mask;
ULL count = __builtin_popcount(bits);
ULL add = (Power(2, counts[mask]) - 1 + MOD) % MOD;
if(count % 2)
{
add = MOD - add;
}
res = (res + add) % MOD;
}
return (res < 0) ? res + MOD : res;
}
int main()
{
cin >> N >> M;
string s;
ULL mask;
for(int i = 0; i < N; i++)
{
cin >> s;
mask = bitset<20>(s).to_ullong();
counts[mask]++;
}
cin >> s;
target = bitset<20>(s).to_ullong();
cout << Solve();
return 0;
}
/*
10 6
101010
100000
000011
001001
100010
100001
001000
000000
100011
1100010
101011
4 4
1000
0011
1001
1010
1011
*/Vim War C Sharp Solution
using System;
using System.Collections.Generic;
using System.Linq;
class Solution {
const int MOD = 1000000007;
static void Main(String[] args) {
long[] two = new long[100001];
two[0] = 1;
for (int i = 1; i < 100001; i++) {
two[i] = (2 * two[i - 1]) % MOD;
}
var tmp = Console.ReadLine().Split(' ');
int n = int.Parse(tmp[0]);
int m = int.Parse(tmp[1]);
List<int> skills = new List<int>();
for (int i = 0; i < n; i++) {
skills.Add(Convert.ToInt32(Console.ReadLine().Trim(), 2));
}
int req = Convert.ToInt32(Console.ReadLine().Trim(), 2);
int[,] count = new int[1 << 20, 21];
int m2 = m;
for (int i = 0; i < m; i++) {
if ((req & (1 << i)) == 0) m2--;
}
for (int i = 0; i < n; i++) {
int k = 0;
if (((req ^ skills[i]) & skills[i]) != 0) continue;
for (int j = 0; j < m; j++) {
if (((req >> j) & 1) == 1) {
k *= 2;
if ((skills[i] & (1 << j)) != 0) k++;
}
}
count[k, m2]++;
}
for (int j = m2; j > 0; j--) {
for (int i = 0; i < (1 << m2); i++) {
count[i, j - 1] += count[i, j];
int val = (i & (1 << (j - 1)));
if (val == 0) {
count[i | (1 << (j - 1)), j - 1] += count[i, j];
}
}
}
long ans = 0;
for (int i = 0; i < (1 << m2); i++) {
int cnt = 0;
for (int j = i; j > 0; j >>= 1) {
cnt += j & 1;
}
long val = two[count[i, 0]];
if (cnt % 2 == m2 % 2) ans = (ans + val) % MOD;
else ans = (ans - val + MOD) % MOD;
}
if(req == 0) ans--;
Console.WriteLine(ans);
}
}Vim War Java Solution
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
private static final int MAX_N= 100000;
private static final int MAX_M= 20;
private static final int MODULO= 1000000007;
public static void main(String[] args) throws Exception {
Scanner in = new Scanner(System.in);
String str;
int [] skills = new int[MAX_N];
int [][] f = new int [1<< MAX_M][MAX_M + 1];
int n = in.nextInt();
int m = in.nextInt();
in.nextLine();
for (int i = 0; i < n; i++) {
boolean ok = true;
str = "";
while (ok) {
str = in.nextLine();
ok = !(str != "");
}
int value = 0;
for (int j = 0; j < m; j++)
value = value * 2 + (str.charAt(j) - '0');
skills[i] = value;
}
int target = 0;
int nuevo_m = 0;
str = "";
str = in.nextLine();
for (int i = 0; i < m; i++) {
if (str.charAt(i) == '1') {
target = target * 2 + 1;
nuevo_m++;
}
}
for (int i = 0; i < n; i++) {
int value = 0;
boolean flag = true;
for (int j = m - 1; j >= 0; j--) {
if (str.charAt(m - j - 1) == '1') {
if ( (skills[i] & (1 << j)) != 0) value = value * 2 + 1;
else value *= 2;
}
else {
if ( (skills[i] & (1 << j) ) != 0 ) {
flag = false;
break;
}
}
}
if (flag) f[value][nuevo_m]++;
}
for (int j = nuevo_m; j > 0; j--) {
for (int i = 0; i < (1 << nuevo_m); i++) {
f[i][j - 1] += f[i][j];
int value = (i & (1 << (j - 1)));
if (value == 0) {
f[i | (1 << (j - 1))][j - 1] += f[i][j];
}
}
}
int respuesta = 0;
for (int i = 0; i < (1 << nuevo_m); i++) {
int cnt = 0;
for (int j = 0; j < nuevo_m; j++) {
if ( (i & (1 << j)) != 0)
cnt++;
}
int value = getMod(2, f[i][0]);
if (cnt % 2 == nuevo_m % 2) respuesta = (respuesta + value) % MODULO;
else respuesta = (respuesta - value + MODULO) % MODULO;
}
if (target == 0)
System.out.println( (respuesta - 1 + MODULO) % MODULO);
else
System.out.println(respuesta);
}
private static int getMod(int x, int y) {
long res = 1 % MODULO;
long value = x % MODULO;
while (y>0) {
if ( (y & 1) != 0 )
res = (res * value) % MODULO;
value = (value * value) % MODULO;
y >>= 1;
}
return (int)res;
}
}Vim War Python Solution
#!/bin/python3
import math
import os
import random
import re
import sys
p = (10**9) + 7
def bool_vector(x):
return int(x, base=2)
def powers_of_two(n):
x = 1
for i in range(n):
yield x
x = (x<<1) %p
def count_C(m, skills):
C = [0]*(1<<m)
for x in skills:
C[x] += 1
for k in reversed(range(m)):
k0 = 1<<k
for j1 in range(0,1<<m, k0<<1):
for j in range(j1, j1|k0):
C[j|k0] += C[j]
return C
def subset(a,b):
return a&b == a
def count_with_C(m, requirements, skills):
remap, new_m = shuffle_bits(requirements)
skills = [bool_vector(remap(skill)) for skill in skills]
requirements = bool_vector(remap(requirements))
skills = [skill for skill in skills if subset(skill, requirements)]
m = new_m
two_pow = list(powers_of_two(len(skills)+1))
C = [two_pow[c] for c in count_C(m, skills)]
max_range = (1 << m) >>1
while max_range > 0:
for j in range(max_range):
C[j] = (C[j] - C[j|max_range]) %p
max_range >>= 1
res = C[0]
if m%2==1:
res = (-res) % p
if requirements == 0:
## the empty set does not count
res -= 1
return res
def shuffle_bits(r):
ones = [i for i,x in enumerate(r) if x=='1']
zeros = [i for i,x in enumerate(r) if x=='0']
order = zeros + ones
def f(x):
return ''.join(x[i] for i in order)
return f, len(ones)
#
# Complete the 'vimWar' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
# 1. STRING_ARRAY skills
# 2. STRING requirement
#
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
n, m = map(int, input().split())
skills = [input().strip() for _ in range(n)]
requirements = input().strip()
result = count_with_C(m, requirements, skills)
fptr.write(str(result) + '\n')
fptr.close()
