In this HackerRank Requirement problem solution, There are N variables and M requirements. Requirements are represented as (x <= y), meaning that the Xth 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 10 to power 3 plus 7.
Problem solution in Java.
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();
}
}
Problem solution in C++.
#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);
}
Problem solution in C.
#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;
}
0 Comments