HackerRank Vim War Problem Solution

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

Sample Output

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()

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python