HackerRank Requirement Problem Solution

In this post, we will solve HackerRank Requirement Problem Solution.

There are n variables and m requirements. Requirements are represented as (xy). meaning that the th variable must be less than or equal to the yth variable.
Your task is to assign non-negative numbers smaller than 10 to each variable and then calculate the number of different assignments satisfying all requirements. Two assignments are different if and only if at least one variable is assigned to a different number in both assignments. Print your answer modulo 103 +7.
Input Format
The first line contains 2 space-separated integers, n and m. respectively. Each of the m subsequent lines contains 2 space-seperated integers describing the respective and y values for an (xy) requirement.

Output Format
Print your answer modulo 10 power 3 +7.

Sample Input 0

Sample Output 0

Explanation 0
There are 6 variables and 7 requirements. Let the variables be in the array a[6]
Requirements are –
a[1] <= a[3], a[0] <= a[1], a[2] <= a[4], a[0] <= a[4], a[2] <= a[5], a[3] <= a[4], a[0] <= a[2]
One of the assignments is – {1, 2, 3, 4, 5, 6}
Similarly there are 25168 assignments possible.
Result = 25168 mod 1007 = 1000.

Requirement C Solution

#include <stdio.h>
#include <stdlib.h>
#define INF 9999
#define MOD 1007
typedef struct _list{
  int mask;
  struct _list *next;
} list;
int table[13][13],dp1[13][13][14],dp3[9000][10];
list *dp2[9000];
int min(int x,int y);
int findleft(int mask,int n);
int getmask(int mask,int x,int n);

int main(){
  int n,m,x,y,i,j,k;
  list *t,*cur;
  for(i=0;i<13;i++)
    for(j=0;j<13;j++)
      table[i][j]=INF;
  scanf("%d%d",&n,&m);
  for(i=0;i<m;i++){
    scanf("%d%d",&x,&y);
    if(x!=y)
      table[x][y]=-1;
  }
  for(i=0;i<n;i++)
    for(j=0;j<n;j++)
      dp1[i][j][0]=table[i][j];
  for(k=1;k<=n;k++)
    for(i=0;i<n;i++)
      for(j=0;j<n;j++)
        dp1[i][j][k]=min(dp1[i][j][k-1],dp1[i][k-1][k-1]+dp1[k-1][j][k-1]);
  t=(list*)malloc(sizeof(list));
  t->mask=0;
  t->next=NULL;
  dp2[0]=t;
  for(i=1;i<(1<<n);i++){
    x=findleft(i,n);
    dp2[i]=dp2[i^(1<<x)];
    x=getmask(i,x,n);
    cur=dp2[i^x];
    while(cur){
      t=(list*)malloc(sizeof(list));
      t->mask=x|cur->mask;
      t->next=dp2[i];
      dp2[i]=t;
      cur=cur->next;
    }
  }
  for(i=0;i<(1<<n);i++)
    dp3[i][0]=1;
  for(i=1;i<10;i++)
    for(j=0;j<(1<<n);j++){
      dp3[j][i]=0;
      cur=dp2[j];
      while(cur){
        dp3[j][i]=(dp3[j][i]+dp3[cur->mask][i-1])%MOD;
        cur=cur->next;
      }
    }
  printf("%d",dp3[(1<<n)-1][9]);
  return 0;
}
int min(int x,int y){
  return (x>y)?y:x;
}
int findleft(int mask,int n){
  int i,j,flag;
  for(i=0;i<n;i++)
    if((1<<i)&mask){
      flag=0;
      for(j=0;j<n;j++)
        if(((1<<j)&mask) && i!=j)
          if(dp1[j][i][n]<0){
            flag=1;
            break;
          }
      if(!flag)
        return i;
    }
  for(i=-1;mask;i++,mask>>=1);
  return i;
}
int getmask(int mask,int x,int n){
  int ans=1<<x,i;
  for(i=0;i<n;i++)
    if(((1<<i)&mask) && dp1[x][i][n]<0)
      ans|=(1<<i);
  return ans;
}

Requirement C++ Solution

#include <bits/stdc++.h>
using namespace std;
#define M 10000010
const int mod = 1e3 + 7;

int flag[M], po[20], ans, a[20], b[20], n, Q, m, sum;

inline void chv(int &x, int y) {x += y; if (x >= mod) x -= mod;}

vector <int> v[20], vs[20], vb[20];

short g[8][M];

void init() {
  for (int i = 0; i < po[n - m]; i++) g[n - m][i] = flag[i];
  for (int i = n - m - 1; i >= 0; i--) {
    for (int j = po[n - m] - 1; j >= 0; j--) {
      int u = (j / po[i]) % 10;
      g[i][j] = g[i + 1][j];
      if (u < 9) {
        g[i][j] += g[i][j + po[i]];
        if (g[i][j] >= mod) g[i][j] -= mod;
      }
    }
  }
}

int main() {
  //freopen("in.txt", "r", stdin);
  scanf("%d %d", &n, &Q);

  po[0] = 1; for (int i = 1; i < 9; i++) po[i] = po[i - 1] * 10;
  int x, y;

  m = n / 2;
  while (Q--) {
    scanf("%d %d", &x, &y);
    v[x].push_back(y);
    if (x < m && y < m) vs[x].push_back(y);
    else if (x >= m && y >= m) vb[x-m].push_back(y-m);
  }

  for (int i = 0; i < po[n - m]; i++) {
    x = i;
    int bf = 1;
    for (int j = 0; j < n - m; j++) a[j] = x % 10, x /= 10;
    for (int j = 0; j < n - m; j++) {
      for (int k = 0; k < vb[j].size(); k++) {
        int u = vb[j][k];
        if (a[u] < a[j]) {
          bf = 0; break;
        }
      }
      if (!bf) break;
    }
    flag[i] = bf;
  }

  init();

  for (int i = 0; i < po[m]; i++) {
    x = i;
    int bf = 1;
    for (int j = 0; j < m; j++) a[j] = x % 10, x /= 10;
    for (int j = 0; j < m; j++) {
      for (int k = 0; k < vs[j].size(); k++) {
        int u = vs[j][k];
        if (a[u] < a[j]) {
          bf = 0; break;
        }
      }
      if (!bf) break;
    }
    if (bf) {
      int rt = 0;
      for (int j = 0; j < n - m; j++) b[j] = 0;
      for (int j = 0; j < m; j++) {
        for (int k = 0; k < v[j].size(); k++) {
          int u = v[j][k]; if (u < m) continue;
          b[u-m] = max(b[u-m], a[j]);
        }
      }
      for (int j = 0; j < n - m; j++) rt += po[j] * b[j];
      chv(ans, g[0][rt]);
    }
  }
  printf("%d\n", ans);
}

Requirement C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;

class Solution {
    const int MOD = 1007;
    static bool[,] req;
    static Dictionary<string, long> map = new Dictionary<string, long>();
    static void Main(String[] args) {
        var tmp = Console.ReadLine().Split(' ');
        int n = int.Parse(tmp[0]);
        int m = int.Parse(tmp[1]);

        if (n == 0) { Console.WriteLine(0); return; }
        if (m == 0) { Console.WriteLine(BigInteger.ModPow(10, n, 1007)); return; }

        int[] l = new int[n], h = new int[n];
        for (int i = 0; i < n; i++) h[i] = 9;

        req = new bool[n, n];

        for (int i = 0; i < m; i++) {
            tmp = Console.ReadLine().Split(' ');
            int x = int.Parse(tmp[0]);
            int y = int.Parse(tmp[1]);

            req[x, y] = true;
        }

        long ans = solve(n, l, h);
        Console.WriteLine(ans % 1007);
    }

    static long solve(int n, int[] bot, int[] top) {
        var sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.Append(bot[i]).Append(top[i]);
        }

        string key = sb.ToString();

        if (!map.ContainsKey(key)) map[key] = solve2(n, bot, top);

        return map[key];
    }

    static long solve2(int n, int[] bot, int[] top) {
        if (n == 0) return 1;
        long r = 0;

        for (int i = bot[n - 1]; i <= top[n - 1]; i++) {

            int[] bot2 = new int[n - 1], top2 = new int[n - 1];

            for (int j = 0; j < n - 1; j++) {
                bot2[j] = req[n - 1, j] ? Math.Max(bot[j], i) : bot[j];
                top2[j] = req[j, n - 1] ? Math.Min(top[j], i) : top[j];
            }

            r += solve(n - 1, bot2, top2);
        }
        return r;
    }
}

Requirement Java Solution

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

    static int n = 15;
    static int[][] adj;
    static Map<Integer, Map<Long, Long>> memoMap = new HashMap<Integer, Map<Long, Long>>();
    
    static {
        for(int v = 0;v <= n;v++) {
            memoMap.put(v, new  HashMap<Long, Long>());
        }
    }
    
    static long calcR(int[] vals, int k) {
        int[] maxV = calcFK(vals, k);
        long key = 0;
        for(int mv : maxV) {
            key = key * 10+mv;
        }
        Long ans = memoMap.get(k).get(key);
        if(ans != null) {
            return ans;
        }
        if(k == n-1) {
            ans = maxV[0]+1l;
            memoMap.get(k).put(key, ans);
            return ans;
        }else {
            ans = 0l;
            for(int v = maxV[0];v >= 0;v--) {
                vals[k] = v;
                ans += calcR(vals, k+1);
            }
            memoMap.get(k).put(key, ans);
            return ans;
        }
    }

    static private int[] calcFK(int[] vals, int k) {
        int[] ans = new int[n-k];
        for(int i = 0;i < n-k;i++) {
            ans[i] = 9;
        }
        for(int i = 0;i < k;i++) {
            int mv = vals[i];
            int[] np = adj[i];
            for(int j = 0;j < np.length;j++) {
                int npAV = np[j];
                if(npAV >= k) {
                    int val = ans[npAV-k];
                    if(val > mv) {
                        ans[npAV-k] = mv;
                    }
                }
            }
        }
        return ans;
    }
    
    static class Node{
        
        int v;
        List<Integer> adjL = new ArrayList<Integer>();
        List<Integer> adjTGL = new ArrayList<Integer>();
        int index;
        
        int color = 0;
        int startT = 0;
        int endT = 0;
        
        public Node(int v) {
            this.v = v;
        }
    }

    static long requirement(int[][] req) {
        int m = req.length;
        Node[] nodes = new Node[n];
        for(int i = 0; i < n;i++) {
            nodes[i] = new Node(i);
        }
        for(int i = 0; i < m;i++) {
            int to = req[i][0];
            int from = req[i][1];
            nodes[from].adjL.add(to);
            nodes[to].adjTGL.add(from);
        }
        process(nodes);
        return  calcR(new int[n], 0);
    }

    
    static LinkedList<Set<Node>> listSCC = new LinkedList<Set<Node>>();
    private static void process(Node[] nodes) {
        DFS(nodes);
        for(int i = 0;i < n;i++) {
            nodes[i].color = 0;
        }
        List<Node> tSL2 = tSL;
        tSL = new LinkedList<Node>();
        for(int i = 0;i < n;i++) {
            Node node = tSL2.get(i);
            if(node.color == 0) {
                Set<Node> set = new HashSet<Node>(); 
                set.add(node);
                DFS_VISIT(set, nodes, node, true);
                listSCC.add(set);
                
            }
        }
        int k = 0;
        for(int i = 0;i < listSCC.size();i++) {
            Set<Integer> set = new HashSet<Integer>();
            Set<Node> cc = listSCC.get(i);
            for(Node node : cc) {
                node.index = k;
            }
            k++;
        }
        adj = new int[k][];
        for(int i = 0;i < listSCC.size();i++) {
            Set<Integer> set = new HashSet<Integer>();
            Set<Node> cc = listSCC.get(i);
            for(Node node : cc) {
                for(int ad : node.adjL) {
                    Node na = nodes[ad];
                    if(na.index != node.index) {
                        set.add(na.index);
                    }
                }
            }
            int[] adN = new int[set.size()];
            int p = 0;
            for(int a : set) {
                adN[p++] = a;
            }
            adj[i] = adN;
        }
        n = k;
    }

    static int time = 0;
    static LinkedList<Node> tSL = new LinkedList<Node>();

    private static void DFS(Node[] nodes) {
        for(int i = 0;i < n;i++) {
            Node node = nodes[i];
            if(node.color == 0) {
                Set<Node> set = new HashSet<Node>(); 
                set.add(node);
                DFS_VISIT(set, nodes, nodes[i], false);
            }
        }
    }

    private static void DFS_VISIT(Set<Node> set, Node[] nodes, Node u, boolean transposeG) {
        time++;
        u.startT = time;
        u.color = 1;
        List<Integer> adL = transposeG ? u.adjTGL : u.adjL;
        for(int adjN : adL) {
            Node v = nodes[adjN];
            if(v.color == 0) {
                //v.parent = u;
                set.add(v);
                DFS_VISIT(set, nodes, v, transposeG);
            }
        }
        u.color = 2;
        tSL.addFirst(u);
        time++;
        u.endT = time;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
        String[] nm = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");
        n = Integer.parseInt(nm[0]);
        int m = Integer.parseInt(nm[1]);
        int[][] req = new int[m][2];
        for (int reqRowItr = 0; reqRowItr < m; reqRowItr++) {
            String[] reqRowItems = scanner.nextLine().split(" ");
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

            for (int reqColumnItr = 0; reqColumnItr < 2; reqColumnItr++) {
                int reqItem = Integer.parseInt(reqRowItems[reqColumnItr]);
                req[reqRowItr][reqColumnItr] = reqItem;
            }
        }
        long result = requirement(req);
        bufferedWriter.write(String.valueOf(result % 1007));
        bufferedWriter.newLine();
        bufferedWriter.close();
        scanner.close();
    }
}

Requirement JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.split('\n');

    main();
});

function readLine() {
    return inputString[currentLine++];
}


function rek(reqMap, hasRequirements, current, index) {
    if (index < 0) {
        return 1;
    }
    const nextIndex = index - 1;
    const req = reqMap.get(index);
    const maximum = req ? req.reduce((minimum, reqIndex) => Math.min(minimum, current[reqIndex]), Number.MAX_SAFE_INTEGER) : 10;

    if (hasRequirements.has(index)) {
        let result = 0;        
        for (let i = 1; i <= maximum; ++i) {
            current[index] = i;
            result += rek(reqMap, hasRequirements, current, nextIndex);
        }
        return result;
    }
    return maximum * rek(reqMap, hasRequirements, current, nextIndex);
}

/*
 * Complete the 'requirement' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. INTEGER n
 *  2. 2D_INTEGER_ARRAY req
 */

function requirement(n, req) {
    const reqMap = new Map();
    const hasRequirements = new Set();
    req.forEach(([x, y]) => {
        if (x === y) {
            return;
        }
        if (!reqMap.has(x)) {
            reqMap.set(x, []);
        }
        reqMap.get(x).push(y);
        hasRequirements.add(y);
    });
    return rek(reqMap, hasRequirements, Array(n), n - 1) % 1007;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const firstMultipleInput = readLine().replace(/\s+$/g, '').split(' ');

    const n = parseInt(firstMultipleInput[0], 10);

    const m = parseInt(firstMultipleInput[1], 10);

    let req = Array(m);

    for (let i = 0; i < m; i++) {
        req[i] = readLine().replace(/\s+$/g, '').split(' ').map(reqTemp => parseInt(reqTemp, 10));
    }

    const result = requirement(n, req);

    ws.write(result + '\n');

    ws.end();
}

Requirement Python Solution

INF = 9999
MOD = 1007

class list:
    def __init__(self, mask):
        self.mask = mask
        self.next = None

def min(x, y):
    return y if x > y else x

def findleft(mask, n):
    for i in range(n):
        if (1 << i) & mask:
            flag = 0
            for j in range(n):
                if ((1 << j) & mask) and i != j:
                    if dp1[j][i][n] < 0:
                        flag = 1
                        break
            if not flag:
                return i
    for i in range(-1, mask, -1):
        mask >>= 1
    return i

def getmask(mask, x, n):
    ans = 1 << x
    for i in range(n):
        if ((1 << i) & mask) and dp1[x][i][n] < 0:
            ans |= 1 << i
    return ans

n, m = map(int, input().split())
table = [[INF for _ in range(13)] for _ in range(13)]
dp1 = [[[0 for _ in range(14)] for _ in range(13)] for _ in range(13)]
dp2 = [None] * 9000
dp3 = [[0 for _ in range(10)] for _ in range(9000)]

for i in range(13):
    for j in range(13):
        table[i][j] = INF

for i in range(m):
    x, y = map(int, input().split())
    if x != y:
        table[x][y] = -1

for i in range(n):
    for j in range(n):
        dp1[i][j][0] = table[i][j]

for k in range(1, n+1):
    for i in range(n):
        for j in range(n):
            dp1[i][j][k] = min(dp1[i][j][k-1], dp1[i][k-1][k-1] + dp1[k-1][j][k-1])

t = list(0)
dp2[0] = t

for i in range(1, 1 << n):
    x = findleft(i, n)
    dp2[i] = dp2[i ^ (1 << x)]
    x = getmask(i, x, n)
    cur = dp2[i ^ x]
    while cur:
        t = list(x | cur.mask)
        t.next = dp2[i]
        dp2[i] = t
        cur = cur.next

for i in range(1 << n):
    dp3[i][0] = 1

for i in range(1, 10):
    for j in range(1 << n):
        dp3[j][i] = 0
        cur = dp2[j]
        while cur:
            dp3[j][i] = (dp3[j][i] + dp3[cur.mask][i-1]) % MOD
            cur = cur.next

print(dp3[(1 << n) - 1][9])

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