HackerRank Unique Divide And Conquer Problem Solution

In this post, we will solve HackerRank’s Unique Divide And Conquer Problem Solution.

Divide-and-conquer on a tree is a powerful approach to solving tree problems.
Imagine a tree, t, with n vertices. Let’s remove some vertex from treet, splitting t into zero or more connected components, t1, t2,…, tk, with vertices 1, 2,…, nk. We can prove that there is a vertex, v, such that the size of each formed component is at most [].
The Divide-and-Conquer approach can be described as follows:

Initially, there is a tree, t, with n vertices.

Find vertex v such that, if is removed from the tree, the size of each formed component after removing v is at most [n/2].
Remove v from tree t.
Perform this approach recursively for each of the connected components.

We can prove that if we find such a vertex v in linear time (e.g., using DFS), the entire approach works in O(nlogn). Of course, sometimes there are several such vertices that we can choose on some step, we can take and remove any of them. However, right now we are interested in trees such that at each step there is a unique vertex y that we can choose.
Given n. count the number of trees it’s such that the Divide-and-Conquer approach works determinately on them. As this number can be quite large, your answer must be modulo m.

Output Format
Print a single integer denoting the number of tree t’s such that the vertex is unique at each step when applying the Divide-and-Conquer approach, modulo m.

Sample Input 0

1 103

Sample Output 0

Explanation 0
For n = 1. there is only one way to build a tree so we print the value of 1 mod 103 = 1 as our answer.

Sample Input 1

2 103

Sample Output 1

Explanation 1

For, there is only one way to build a tree:

Sample Input 2

3 103

Sample Output 2

Explanation 2

For n = 3, there are 3 valid trees depicted in the diagram below (the unique vertex removed in the first step is shown in red):

Thus, we print the value of 3 mod 103 = 3 as our answer.

Sample Input 3

4 103

Sample Output 3

Explanation 3

For n= 4, there are 4 valid trees depicted in the diagram below (the unique vertex removed in the first step is shown in red)

This tree is not valid because we can choose to remove node 2 or node 3 in the first step. Because we had four valid trees, we printed the value of 4 mod 103 = 4 as our answer.

HackerRank Unique Divide And Conquer Problem Solution

Unique Divide And Conquer C Solution

#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define N 3001
typedef long long ll;
int f[N],g[N],c[N][N],n,p;
int main()
{
    scanf("%d%d",&n,&p);
    g[0]=1;
    f[1]=g[1]=1;
    f[2]=0; g[2]=1;
    fo(i,0,n) c[i][0]=1;
    fo(i,1,n)
        fo(j,1,i) c[i][j]=(c[i-1][j-1]+c[i-1][j])%p;
    f[0]=1;
    fo(i,3,n)
    {
        if (i&1)
        {
            f[i]=g[i-1]; 
            fo(j,i/2+1,i-1) f[i]=(f[i]-(ll)g[i-1-j]*f[j]%p*j%p*c[i-1][j])%p;
            int half=i/2;
            f[i]=(ll)f[i]*i%p; 
        } else
        {
            f[i]=g[i-1];
            fo(j,i/2,i-1)   f[i]=(f[i]-(ll)g[i-1-j]*f[j]%p*j%p*c[i-1][j])%p;
            f[i]=(ll)f[i]*i%p;
        }
        fo(j,1,i)
        g[i]=(g[i]+(ll)g[i-j]*c[i-1][j-1]%p*f[j]%p*j%p)%p;
    }
    printf("%d\n",(f[n]+p)%p);
}

Unique Divide And Conquer C++ Solution

#include <bits/stdc++.h>
using namespace std;

#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

ll mod;
vector<ll> fact, ifact;

vector<int> mem;
vector<vector<int>> mem2;
ll solve2(int left, int max);

ll rsolve(int n) {
	if (n <= 5) return n != 2;
	return solve2(n-1, (n-1)/2);
}

ll solve(int n) {
	assert(n > 0);
	int& out = mem[n];
	if (out != -1) return out;
	return out = (int)(rsolve(n) * n % mod);
}

ll solve2(int left, int max) {
	if (left == 0) return 1;
	if (!max) return 0;
	int& out = mem2[left][max];
	if (out != -1) return out;
	ll res = solve2(left, max-1);
	if (max > left) return out = (int)res;
	int lim = left / max;
	ll one = solve(max) * max % mod * ifact[max] % mod;
	ll mult = one * fact[left] % mod;
	for (int i = 1;; i++) {
		ll bin = ifact[i] * ifact[left - i * max] % mod;
		res += solve2(left - i * max, max-1) * mult % mod * bin;
		if (i == lim) break;
		if (i % 4 == 0) res %= mod;
		mult = mult * one % mod;
	}
	res %= mod;
	return out = (int)res;
}

int main() {
	cin.sync_with_stdio(false);
	cin.exceptions(cin.failbit);
	int N;
	cin >> N >> mod;
	mem.assign(N+1, -1);
	mem2.assign(N+1, vector<int>(N+1, -1));
	int LIM = N+1;
	ll* inv = new ll[LIM] - 1; inv[1] = 1;
	rep(i,2,LIM) inv[i] = mod - (mod / i) * inv[mod % i] % mod;
	fact.resize(N+1);
	ifact.resize(N+1);
	fact[0] = ifact[0] = 1;
	rep(i,1,N+1) {
		fact[i] = fact[i-1] * i % mod;
		ifact[i] = ifact[i-1] * inv[i] % mod;
	}
	cout << solve(N) << endl;
	exit(0);
}

Unique Divide And Conquer C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Text;
using System.Linq;
class Solution {
    static int N, MOD, n, no, y, CN;
    static long[,] CNK,map;
    static long[] fac;
    static List<long> w;
    static void pre() {
        CN = N + 1;
        CNK = new long[CN, CN];
        map = new long[CN, CN];
        CNK[0, 0] = 1; map[0, 0] = -1;
        for (int i = 1; i < CN; i++) {
            CNK[i, 0] = CNK[i, i] = 1; map[i, 0] = map[0, i] = map[i, i] = -1;
            for (int j = 1; j <= i; j++) {
                map[j, i] = map[i, j] = -1;
                CNK[i, j] = (CNK[i - 1, j] + CNK[i - 1, j - 1]) % MOD;
            }
        }

        fac = new long[CN];
        fac[0] = fac[1] = 1;
        for (int i = 2; i < CN; i++) {
            fac[i] = (i * fac[i - 1]) % MOD;
            fac[i - 1] = (fac[i - 1] * modInverse((int)fac[i], MOD)) % MOD;
        }

        w = new List<long> { 0, 1, 0, 9, 16, 25};
    }
    static void Main(String[] args) {
        var tmp = Console.ReadLine().Split(' ');
        N = int.Parse(tmp[0]);
        MOD = int.Parse(tmp[1]);

        if (N == 1) { Console.WriteLine(1); return; }
        if (N == 2) { Console.WriteLine(0); return; }
        pre();


        for (int i = 6; i <= N / 2; i++) {
            w.Add((solve(i) * i) % MOD);
        }

        Console.WriteLine(solve(N));
    }

    static long solve(int a) {
        n = a;
        no = n / 2;
        y = n - no - 1;
        no = n - no;
        return go(n - 1, n / 2, 0);
    }

    static long go(int p, int i, int f) {
        if (i >= no) i = y;

        long kk = 0;
        if (i == p) {
            kk = ((p + 1) * ((w[i] * fac[f]) % MOD)) % MOD;
        } else if ((i << 1) <= p) {
            kk = go(p - i, i, f + 1) * (CNK[p + 1, i] * (w[i] * fac[f] % MOD) % MOD) % MOD;
        } else {
            kk = go(p - i, p - i, 0) * (CNK[p + 1, i] * (w[i] * fac[f] % MOD) % MOD) % MOD;
        }
        i--;




        if (map[i, p] == -1) map[i, p] = gogo(p, i);

        return (kk + map[i, p]) % MOD;
    }

    static long gogo(int p, int i) {
        if (i == 0) return 0;
        if (map[i - 1, p] == -1) {
            map[i - 1, p] = gogo(p, i - 1);
        }

        if ((i << 1) <= p) {
            return (map[i - 1, p] + (go(p - i, i, 1) * (CNK[p + 1, i] * w[i] % MOD) % MOD) % MOD) % MOD;
        } else {
            return (map[i - 1, p] + (go(p - i, p - i, 0) * (CNK[p + 1, i] * w[i] % MOD) % MOD) % MOD) % MOD;
        }
    }
    static int modInverse(int a, int m) {
        int t, q;
        int x0 = 0, x1 = 1;

        while (a > 1) {
            q = a / m; t = m;
            m = a % m; a = t; t = x0;
            x0 = x1 - q * x0; x1 = t;
        }

        x1 %= MOD;
        if (x1 < 0) return x1 + MOD;
        return x1;
    }
}

Unique Divide And Conquer Java Solution

import java.io.*;
import java.util.*;

public class Solution {
    FastScanner in;
    PrintWriter out;

    void solve() {
        int n = in.nextInt();
        int p = in.nextInt();
        int[][] c = new int[n + 1][n + 1];
        c[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            c[i][0] = 1;
            for (int j = 1; j <= n; j++) {
                c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
                if (c[i][j] >= p) {
                    c[i][j] -= p;
                }
            }
        }
        long[] dpSum = new long[n + 1];
        long[] ans = new long[n + 1];
        long[] dpBad = new long[n + 1];
        dpSum[0] = 1;
        for (int sz = 1; sz <= n; sz++) {
            for (int big = (1 + sz) / 2; big < sz; big++) {
                dpBad[sz] += dpSum[sz - 1 - big] * ans[big] % p * big % p
                        * c[sz - 1][big] % p;
            }
            dpBad[sz] %= p;
            ans[sz] = (dpSum[sz - 1] - dpBad[sz] + p) * sz % p;
            for (int size1 = 1; size1 <= sz; size1++) {
                dpSum[sz] += ans[size1] * size1 % p * c[sz - 1][size1 - 1] % p
                        * dpSum[sz - size1] % p;
            }
            dpSum[sz] %= p;
        }
        out.println(ans[n]);
    }

    void run() {
        try {
            in = new FastScanner(new File("object.in"));
            out = new PrintWriter(new File("object.out"));

            solve();

            out.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    void runIO() {

        in = new FastScanner(System.in);
        out = new PrintWriter(System.out);

        solve();

        out.close();
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(File f) {
            try {
                br = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        public FastScanner(InputStream f) {
            br = new BufferedReader(new InputStreamReader(f));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return null;
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

        boolean hasMoreTokens() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return false;
                st = new StringTokenizer(s);
            }
            return true;
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    public static void main(String[] args) {
        new Solution().runIO();
    }
}

Unique Divide And Conquer Python Solution

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'uniqueDivideAndConquer' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. INTEGER n
#  2. INTEGER m
#

def powerrr(a, b, M):
    fin = 1
    while b:
        if b & 1:
            fin = (fin * a) % M
        a = (a * a) % M
        b >>= 1
    return fin

def inv(x, M):
    return powerrr(x, M - 2, M)

def calculatiosn(n, M):
    ans1 = [0] * (n + 1)
    ans2 = [0] * (n + 1)
    ans1[0] = ans2[0] = 1
    for i in range(1, n + 1):
        ans1[i] = (ans1[i - 1] * i) % M
        ans2[i] = (ans2[i - 1] * inv(i, M)) % M
    return ans1, ans2
def uniqueDivideAndConquer(n, m):
    ans1, ans2 = calculatiosn(n, m)
    f = [0] * (n + 1)
    dp = [0] * (n + 1)
    f[1] = 1
    dp[0] = dp[1] = 1
    for i in range(2, n + 1):
        f[i] = dp[i - 1]
        for j in range((i + 1) // 2, i):
            cur1 = (f[j] * ans1[i - 1]) % m # cnk(i - 1, j)
            cur2 = (cur1 * ans2[j]) % m
            cur3 = (cur2 * ans2[i - 1 - j]) % m
            cur4 = (cur3 * j) % m
            f[i] -= (cur4 * dp[i - j - 1]) % m
            if f[i] < 0:
                f[i] += m
        f[i] = (f[i] * i) % m
        for j in range(1, i + 1):
            cur1 = (f[j] * ans1[i - 1]) % m # cnk(i - 1, j - 1)
            cur2 = (cur1 * ans2[j - 1]) % m
            cur3 = (cur2 * ans2[i - j]) % m
            cur4 = (cur3 * j) % m
            dp[i] = (dp[i] + cur4 * dp[i - j]) % m
    return f[n]
    


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    first_multiple_input = input().rstrip().split()

    n = int(first_multiple_input[0])

    m = int(first_multiple_input[1])

    result = uniqueDivideAndConquer(n, m)

    fptr.write(str(result) + '\n')

    fptr.close()

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