Commvault

01Count Good Strings

There is a string of length 2N containing only character A and B. The string is called good string if the following two conditions are satisfied: The number of A and number of B in that string will be same and that is N, means N numbers of A and N numbers of B will be present in that string. The number of A will be always greater than or equal to the number of B in any prefix string of that string. Now you are given N and you need to count the number of good strings of length 2N, the answer may be very large so return the answer in modulo 10000.

Constraints

o_o

Example 1

Input:

N = 3

Output:

Explanation: Here are the good strings of length 2N when N=3:

"AAABBB" good
"AABABB" good
"AABBAB" good
"ABAABB" good
"ABABAB" good "BABABA" is not a good string because the number of Bs is greater than the number of As in the prefix "BA". Therefore, the count of good strings is 5.

解法

卡特兰数 C_n = C(2n, n) / (n+1) mod 10000。直接用 DP dp[i] = sum dp[j]*dp[i-1-j] 或公式(注意非素数取模需用纯 DP)。时间复杂度 O(N²)。

def countGoodStrings(N: int) -> int:
    MOD = 10000
    dp = [0] * (N + 1)
    dp[0] = 1
    for i in range(1, N + 1):
        for j in range(i):
            dp[i] = (dp[i] + dp[j] * dp[i - 1 - j]) % MOD
    return dp[N]

class Solution {
    int countGoodStrings(int N) {
        int MOD = 10000;
        long[] dp = new long[N + 1];
        dp[0] = 1;
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] = (dp[i] + dp[j] * dp[i - 1 - j]) % MOD;
            }
        }
        return (int) dp[N];
    }
}

class Solution {
public:
    int countGoodStrings(int N) {
        const int MOD = 10000;
        vector<long long> dp(N + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] = (dp[i] + dp[j] * dp[i - 1 - j]) % MOD;
            }
        }
        return (int) dp[N];
    }
};

02Count Ways to Travel Cities

In a country there are different cities and the cities marked with integer number starting from 1. And now you need to travel in the N cities with some following criteria.

You need to travel exactly N cities and you can start travelling from any of the cities
If you visit a city of number n, then the next city number will be more than or equal to 2n
And you are also given a number K and any city number can't more than K. Now you are given N and K, need to find how many ways you can travel the cities by keeping in mind the conditions given. And return the answer in module 1000000007 as the answer will be very large. Function Description Complete the function countWaysToTravelCities in the editor. countWaysToTravelCities has the following parameters: N: an integer, the number of cities to travel K: an integer, the maximum city number allowed Returns int: the number of ways to travel the cities modulo 1000000007

Example 1

Input:

N = 3
K = 10

Output:

TO-DO

Explanation: Some of the valid city paths will be -

1-2-4
1-3-6
1-4-8 There are more ways to travel the cities, but these are just a few examples.

解法

DP：f[n][c] = 已访问 n 个城市，当前最后一个城市编号为 c 的方案数。转移：f[n+1][c'] += f[n][c] for c' in [2c, K]。最终答案 = sum f[N][c]。优化：用前缀和把内层 O(K) 转移压到 O(1)。时间复杂度 O(N·K)，对超大 K 可推断 N ≤ log₂K。

MOD = 10 ** 9 + 7

def countWaysToTravelCities(N: int, K: int) -> int:
    # f[c] = ways to end at city c with current "step count"
    f = [0] * (K + 2)
    for c in range(1, K + 1):
        f[c] = 1
    for _ in range(N - 1):
        # prefix sum
        pref = [0] * (K + 2)
        for c in range(1, K + 1):
            pref[c] = (pref[c - 1] + f[c]) % MOD
        new_f = [0] * (K + 2)
        for c2 in range(2, K + 1):
            new_f[c2] = pref[c2 // 2]
        f = new_f
    return sum(f) % MOD

class Solution {
    static final int MOD = 1_000_000_007;

    int countWaysToTravelCities(int N, int K) {
        long[] f = new long[K + 2];
        for (int c = 1; c <= K; c++) f[c] = 1;
        for (int step = 1; step < N; step++) {
            long[] pref = new long[K + 2];
            for (int c = 1; c <= K; c++) pref[c] = (pref[c - 1] + f[c]) % MOD;
            long[] nf = new long[K + 2];
            for (int c2 = 2; c2 <= K; c2++) nf[c2] = pref[c2 / 2];
            f = nf;
        }
        long ans = 0;
        for (long v : f) ans = (ans + v) % MOD;
        return (int) ans;
    }
}

class Solution {
public:
    static const int MOD = 1000000007;

    int countWaysToTravelCities(int N, int K) {
        vector<long long> f(K + 2, 0);
        for (int c = 1; c <= K; c++) f[c] = 1;
        for (int step = 1; step < N; step++) {
            vector<long long> pref(K + 2, 0);
            for (int c = 1; c <= K; c++) pref[c] = (pref[c - 1] + f[c]) % MOD;
            vector<long long> nf(K + 2, 0);
            for (int c2 = 2; c2 <= K; c2++) nf[c2] = pref[c2 / 2];
            f = nf;
        }
        long long ans = 0;
        for (long long v : f) ans = (ans + v) % MOD;
        return (int) ans;
    }
};

03Number of Good Pairs

There is a graph and the number of Nodes on that graph is N and also given K edges, now you need to find the number of good pairs in that graph, The definition of the good pairs in that graph is:

On those pairs, two nodes not present in the same components of that graph, means both the nodes present in different connected components and there are no connected paths in between them. Now, you are given N the number of nodes and K the number of edges and the connected edges in the form of array V and array U. Function Description Complete the function numberOfGoodPairs in the editor. numberOfGoodPairs has the following parameters:
1. N: the number of nodes
1. K: the number of edges
1. int V[]: an array of integers representing one end of the edge
1. int U[]: an array of integers representing the other end of the edge Returns int: the number of good pairs

解法

并查集求各连通块大小 s_i。好对总数 = C(N, 2) - sum(C(s_i, 2))，即不在同块的所有无序对。时间复杂度 O((N+K)·α(N))。

from typing import List

def numberOfGoodPairs(N: int, K: int, V: List[int], U: List[int]) -> int:
    parent = list(range(N + 1))
    size = [1] * (N + 1)
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    def union(a, b):
        ra, rb = find(a), find(b)
        if ra == rb: return
        if size[ra] < size[rb]: ra, rb = rb, ra
        parent[rb] = ra
        size[ra] += size[rb]
    for v, u in zip(V, U):
        union(v, u)
    total = N * (N - 1) // 2
    same = 0
    counted = set()
    for i in range(1, N + 1):
        r = find(i)
        if r in counted: continue
        counted.add(r)
        s = size[r]
        same += s * (s - 1) // 2
    return total - same

class Solution {
    int[] parent, size;

    int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }

    void union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return;
        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
        parent[rb] = ra;
        size[ra] += size[rb];
    }

    long numberOfGoodPairs(int N, int K, int[] V, int[] U) {
        parent = new int[N + 1];
        size = new int[N + 1];
        for (int i = 0; i <= N; i++) { parent[i] = i; size[i] = 1; }
        for (int i = 0; i < V.length; i++) union(V[i], U[i]);
        long total = (long) N * (N - 1) / 2;
        long same = 0;
        Set<Integer> counted = new HashSet<>();
        for (int i = 1; i <= N; i++) {
            int r = find(i);
            if (!counted.add(r)) continue;
            long s = size[r];
            same += s * (s - 1) / 2;
        }
        return total - same;
    }
}

class Solution {
public:
    vector<int> parent, sz;

    int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }

    void unite(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return;
        if (sz[ra] < sz[rb]) swap(ra, rb);
        parent[rb] = ra;
        sz[ra] += sz[rb];
    }

    long long numberOfGoodPairs(int N, int K, vector<int>& V, vector<int>& U) {
        parent.assign(N + 1, 0); sz.assign(N + 1, 1);
        for (int i = 0; i <= N; i++) parent[i] = i;
        for (int i = 0; i < (int)V.size(); i++) unite(V[i], U[i]);
        long long total = (long long) N * (N - 1) / 2;
        long long same = 0;
        set<int> counted;
        for (int i = 1; i <= N; i++) {
            int r = find(i);
            if (!counted.insert(r).second) continue;
            long long s = sz[r];
            same += s * (s - 1) / 2;
        }
        return total - same;
    }
};