HackerRank Kingdom Division Problem Solution
In this post, we will solve HackerRank Kingdom Division Problem Solution.
King Arthur has a large kingdom that can be represented as a tree, where nodes correspond to cities and edges correspond to the roads between cities. The kingdom has a total of n cities numbered from 1 to n.
The King wants to divide his kingdom between his two children, Reggie and Betty, by giving each of them 0 or more cities; however, they don’t get along so he must divide the kingdom in such a way that they will not invade each other’s cities. The first sibling will invade the second sibling’s city if the second sibling has no other cities directly connected to it. For example, consider the kingdom configurations below:
Given a map of the kingdom’s n cities, find and print the number of ways King Arthur can divide it between his two children such that they will not invade each other. As this answer can be quite large, it must be modulo 10 power 9 +7.
Input Format
The first line contains a single integer denoting n (the number of cities in the kingdom). Each of the n – 1 subsequent lines contains two space-separated integers, u and v. describing a road connecting cities u and v.
Output Format
Print the number of ways to divide the kingdom such that the siblings will not invade each other, modulo 10 power 9 +7.
Sample Input
5
1 2
1 3
3 4
3 5
Sample Output
4
Explanation
In the diagrams below, red cities are ruled by Betty and blue cities are ruled by Reggie. The diagram below shows a division of the kingdom that results in war between the siblings.
Because cities 5 and 4 are not connected to any other red cities, blue city will cut off their supplies and declare war on them. That said, there are four valid ways to divide the kingdom peacefully.
Kingdom Division C Solution
#include <stdio.h>
#include <stdlib.h>
#define MOD 1000000007
typedef struct _lnode
{
int x;
int w;
struct _lnode *next;
}
lnode;
void insert_edge(int x,int y,int w);
void dfs(int x,int y);
long long not_care[100000],safe[100000];
lnode *table[100000]={0};
int main()
{
int n,x,y,i;
scanf("%d",&n);
for(i=0;i<n-1;i++)
{
scanf("%d%d",&x,&y);
insert_edge(x-1,y-1,0);
}
dfs(0,-1);
printf("%lld",safe[0]*2%MOD);
return 0;
}
void insert_edge(int x,int y,int w)
{
lnode *t=(lnode*)malloc(sizeof(lnode));
t->x=y;
t->w=w;
t->next=table[x];
table[x]=t;
t=(lnode*)malloc(sizeof(lnode));
t->x=x;
t->w=w;
t->next=table[y];
table[y]=t;
return;
}
void dfs(int x,int y)
{
int f=0;
long long not_safe=1;
lnode *p;
not_care[x]=1;
for(p=table[x];p;p=p->next)
if(p->x!=y){
dfs(p->x,x);
f=1;
not_care[x]=(not_care[p->x]+safe[p->x])%MOD*not_care[x]%MOD;
not_safe=not_safe*safe[p->x]%MOD;
}
if(!f)
safe[x]=0;
else
safe[x]=(not_care[x]-not_safe+MOD)%MOD;
return;
}
Kingdom Division C++ Solution
#pragma region H
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <iostream>
#include <unordered_map>
#include <cmath>
#include <map>
#include <ctime>
#include <set>
#include <stack>
#include <stdio.h>
#include <iomanip>
#include <functional>
#include <cmath>
#include <sstream>
#include <cstdlib>
#define X first
#define Y second
#define fid(n) for (int i = (n)-1;i>=0;i--)
#define fjd(n) for (int j = (n)-1;j>=0;j--)
#define fkd(n) for (int k = (n)-1;k>=0;k--)
#define fid1(n) for (int i = (n)-1;i>=1;i--)
#define fjd1(n) for (int j = (n)-1;j>=1;j--)
#define fkd1(n) for (int k = (n)-1;k>=1;k--)
#define fi(n) for (int i = 0;i<(n);i++)
#define fj(n) for (int j = 0;j<(n);j++)
#define fk(n) for (int k = 0;k<(n);k++)
#define fi1(n) for (int i = 1;i<(n);i++)
#define All(x) (x).begin(),(x).end()
#define rAll(x) (x).rbegin(),(x).rend()
typedef long long ll;
using namespace std;
template<class T>inline const T sqr(const T & x) { return x*x; }
ll gcd(ll a, ll b) { while (b) { a %= b; swap(a, b); }return a; }
ll lcm(ll a, ll b) { return a*b / gcd(a, b); }
ll popcnt(ll mask) { ll cnt = 0; while (mask) cnt += mask % 2, mask /= 2; return cnt; }
void pause()
{
#ifdef _DEBUG
system("PAUSE");
#endif
}
ll powi(ll a, ll b, ll mod = 1000000007)
{
if (b < 2) return b ? a : 1;
return (powi((a*a) % mod, b / 2, mod)*(b % 2 ? a : 1LL)) % mod;
}
ll mod7 = 1000000007; ll mod9 = 1000000009;
#pragma endregion
const ll N = 100000 + 11;
vector<ll> g[N];
ll dp[N][2][2];
//vertex,parrent,self
void dfs(int v, int p)
{
fi(2)fj(2) dp[v][i][j] = (i == j);
ll o[2] = { 1,1 };
for (auto to : g[v])if (to != p)
{
dfs(to, v);
}
for (auto to : g[v])if (to != p)
{
fi(2)
{
dp[v][i][i] *= (dp[to][i][0]+dp[to][i][1])%mod7;
dp[v][i][i] %= mod7;
o[i] *= dp[to][i][i ^ 1];
o[i] %= mod7;
}
}
fi(2)
{
dp[v][i ^ 1][i] = (dp[v][i][i]-o[i]+mod7)%mod7;
}
}
int main(int argc, char* argv[]) {
ios::sync_with_stdio(false);
#ifdef _DEBUG
ifstream cin; cin.open("test.txt");
#endif
ll n; cin >> n;
fi(n - 1)
{
ll a, b; cin >> a >> b;
a--; b--;
g[a].push_back(b);
g[b].push_back(a);
}
dfs(0, -1);
cout << (dp[0][0][1] + dp[0][1][0])%mod7 << endl;
pause(); return 0;
}Kingdom Division C Sharp Solution
using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;
using System.Numerics;
class Result
{
/*
* Complete the 'kingdomDivision' function below.
*
* The function is expected to return an INTEGER.
* The function accepts following parameters:
* 1. INTEGER n
* 2. 2D_INTEGER_ARRAY roads
*/
private static List<List<int>> list;
private static int[][][] mem;
private static long mod;
public static long kingdomDivision(int n, List<List<int>> roads)
{
mod = 1000000007;
mem = new int[100005][][];
for (int i = 0; i < 100005; i++)
{
mem[i] = new int[2][];
for (int j = 0; j < 2; j++)
{
mem[i][j] = new int[2];
}
}
list = new List<List<int>>();
for (int i = 0; i < n + 1; i++)
{
list.Add(new List<int>());
}
for (int i = 0; i < roads.Count; i++)
{
int a = roads[i][0];
int b = roads[i][1];
list[a].Add(b);
list[b].Add(a);
}
return 2 * g(1, 0, 0, 0, 0) % mod;
}
private static long g(int node, int parent, int index, int color, int ally)
{
if (index == list[node].Count)
{
return ally;
}
int child = list[node][index];
if (child == parent)
{
return g(node, parent, index + 1, color, ally);
}
if (mem[child][color][ally] != 0)
{
return mem[child][color][ally];
}
long res;
res = g(child, node, 0, color, 1) * g(node, parent, index + 1, color, 1) % mod;
res = res + g(child, node, 0, 1 - color, 0) * g(node, parent, index + 1, color, ally) % mod;
mem[child][color][ally] = (int)res;
return res;
}
}
class Solution
{
public static void Main(string[] args)
{
TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);
int n = Convert.ToInt32(Console.ReadLine().Trim());
List<List<int>> roads = new List<List<int>>();
for (int i = 0; i < n - 1; i++)
{
roads.Add(Console.ReadLine().TrimEnd().Split(' ').ToList().Select(roadsTemp => Convert.ToInt32(roadsTemp)).ToList());
}
long result = Result.kingdomDivision(n, roads);
textWriter.WriteLine(result);
textWriter.Flush();
textWriter.Close();
}
}Kingdom Division Java Solution
import java.util.*;
import java.io.*;
public class Solution{
static final int MOD = 1_000_000_007;
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
public static void main(String args[]) throws IOException{
int n = Integer.parseInt(reader.readLine());
Node[] nodes = new Node[n];
for(int e = 1; e < n; e++){
int[] edge = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int u = edge[0];
int v = edge[1];
if(nodes[u - 1] == null){
nodes[u - 1] = new Node(u);
}
if(nodes[v - 1] == null){
nodes[v - 1] = new Node(v);
}
nodes[u - 1].add(nodes[v - 1]);
nodes[v - 1].add(nodes[u - 1]);
}
System.out.println(Solution.solve(nodes[0]));
}
static long solve(Node root){
LinkedList<Node> stack = new LinkedList<>();
stack.add(0, root);
while(!stack.isEmpty()){
stack.peek().checkChild();
if(stack.peek().isLeaf() || stack.peek().peekChild().hasWeight()){
stack.poll().computeWeight();
continue;
}
stack.add(0, stack.peek().nextChild());
}
return root.getWeight();
}
static class Node{
Queue<Node> children;
long color;
long label;
Node parent;
public Node(int label){
this.label = label;
this.parent = null;
this.children = new LinkedList<>();
this.color = -1;
}
private long colorCombos(){
if(this.isLeaf()){
return 1;
}
long colorCombos = 1;
for(Node child : this.children){
long childCombos = (child.isLeaf()) ? child.color : child.getWeight();
childCombos = (childCombos + child.negCombos()) % Solution.MOD;
colorCombos = (colorCombos * childCombos) % Solution.MOD;
}
return colorCombos;
}
private long negCombos(){
if(this.isLeaf()){
return 0;
}
long negCombos = 1;
for(Node child : this.children){
if(child.isLeaf()){
return 0;
}
negCombos = (negCombos * child.color) % Solution.MOD;
}
return negCombos;
}
public void add(Node child){
this.children.add(child);
}
public void checkChild(){
if(!this.isLeaf() && this.children.peek() == this.parent){
this.children.poll();
}
if(!this.isLeaf()){
this.children.peek().parent = this;
}
}
public void computeWeight(){
long colorCombos = this.colorCombos();
long negCombos = this.negCombos();
this.color = (colorCombos >= negCombos) ? colorCombos - negCombos : colorCombos + Solution.MOD - negCombos;
}
public long getWeight(){
return (2 * this.color) % Solution.MOD;
}
public boolean hasWeight(){
return this.color != -1;
}
public boolean isLeaf(){
return this.children.isEmpty();
}
public Node nextChild(){
this.checkChild();
if(this.isLeaf()){
return null;
}
Node child = this.children.poll();
this.children.add(child);
return child;
}
public Node peekChild(){
this.checkChild();
return (this.isLeaf()) ? null : this.children.peek();
}
}
}Kingdom Division 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', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.replace(/\s*$/, '')
.split('\n')
.map(str => str.replace(/\s*$/, ''));
main();
});
function readLine() {
return inputString[currentLine++];
}
let nodes = {};
function getNode(n) {
if ( n in nodes ) {
return nodes[n];
} else {
let node = {
id: n,
parent: null,
children: [],
sibling: null,
peacecount: -1n,
quasicount: -1n
};
nodes[n]=node;
return node;
}
}
function family(root) {
let queue = [ root ];
while ( queue.length>0 ) {
let c=queue.shift();
let prevchild = null;
for ( let i=0; i<c.children.length; i++ ) {
let child = c.children[i];
child.parent = c;
const index = child.children.indexOf(c);
if (index > -1) {
child.children.splice(index, 1);
}
if ( prevchild!=null ) {
prevchild.sibling = child;
}
prevchild = child;
queue.push(child);
}
}
}
function mktree(roads) {
for (let i=0; i<roads.length; i++) {
let [n0,n1] = roads[i].map(getNode);
n0.children.push(n1);
n1.children.push(n0);
}
let root = nodes[roads[0][0]];
family(root);
return root;
}
const M=1000000007n;
function devide(root) { //non recursive
let c=root;
while ( root.peacecount<0n ) {
while (c.children.length>0) {
c=c.children[0];
}
c.peacecount=0n;
c.quasicount=1n;
while ( c.sibling==null && c.parent!=null ) {
c=c.parent;
c.peacecount=1n;
c.quasicount=1n;
for (let i=0; i<c.children.length; i++ ) {
let child = c.children[i];
let [pc,qc] = [child.peacecount,child.quasicount];
c.peacecount = (c.peacecount*(pc*2n+qc))%M;
c.quasicount = (c.quasicount*pc)%M;
}
c.peacecount=(c.peacecount-c.quasicount+M)%M;
// console.error(c.id,"=>",c.peacecount,c.quasicount);
}
c=c.sibling;
}
return (root.peacecount*2n)%M;
}
// Complete the kingdomDivision function below.
function kingdomDivision(n, roads) {
return devide(mktree(roads));
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const n = parseInt(readLine(), 10);
let roads = Array(n-1);
for (let i = 0; i < n-1; i++) {
roads[i] = readLine().split(' ').map(roadsTemp => parseInt(roadsTemp, 10));
}
let result = kingdomDivision(n, roads);
ws.write(result + "\n");
ws.end();
}Kingdom Division Python Solution
#!/bin/python3
import sys
from collections import defaultdict, Counter, deque
# read the input, assembling graph
n = int(input())
edges = defaultdict(set) # adjacency list
degree = Counter() # node degree
for _ in range(n-1):
u, v = map(int, input().split())
edges[u].add(v)
edges[v].add(u)
degree[u] += 1
degree[v] += 1
# The possible divisions for a sub-tree rooted @ node is
# count[node][parent]
# where parent = True if the node shares its parent's color
count = {u: {True: 1, False: 1} for u in degree}
# We accumulate counts by iteratively stripping leaves from the tree
leaves = deque([u for u in degree if degree[u] == 1])
while True:
node = leaves.popleft()
# If parent differs, exclude case where ALL children differ
count[node][False] = count[node][True] - count[node][False]
# If no edges left, we have reached root and are done
if not degree[node]:
root = node
break
else:
# Otherwise update parent:
parent = edges[node].pop()
# update topology
edges[parent].discard(node)
degree[parent] -= 1
if degree[parent] == 1:
leaves.append(parent)
# update counts
count[parent][True] *= count[node][True] + count[node][False]
count[parent][False] *= count[node][False]
# Note each division has a corresponding one with colors switched
total = 2 * count[root][0]
print(total % (10**9 + 7))
