Ehab and the Expected GCD Problem

The key insight is that the first element should have the maximum number of prime factors, and subsequent elements should remove at most one prime factor per step for optimality. The smallest prime factors are 2 and 3, and using 3 more than once is suboptimal (e.g., 5 can be replaced by 2² for better results). Let the first element be m = 2ˣ3ʸ. We define dp[i][x][y] as the number of sequences of length i where the gcd is 2ˣ3ʸ. Let v[x][y] = ⌊n / (2ˣ3ʸ)⌋. The transitions are:

• dp[i][x][y] += dp[i-1][x][y] × max(0, v[x][y] - i + 1)
• dp[i][x][y] += dp[i-1][x+1][y] × (v[x][y] - v[x+1][y])
• dp[i][x][y] += dp[i-1][x][y+1] × (v[x][y] - v[x][y+1])

These correspond to maintaining the gcd, removing a factor of 2, or removing a factor of 3.

#include <iostream>
using namespace std;
const int MOD = 1e9+7;
const int MAX_EXP = 20;

int main() {
    int n;
    cin >> n;
    if (n == 1) {
        cout << 1;
        return 0;
    }
    
    int max_power = 0, temp = n;
    while (temp / 2 > 0) {
        temp /= 2;
        max_power++;
    }
    bool use_three = (1 << (max_power-1)) * 3 <= n;
    
    int divisor_count[MAX_EXP+1][2] = {0};
    for (int i = 0; i <= max_power; i++) {
        int base = 1 << i;
        divisor_count[i][0] = n / base;
        if (use_three) divisor_count[i][1] = n / (base * 3);
    }
    
    int dp[n+1][MAX_EXP+1][2] = {0};
    dp[1][max_power][0] = 1;
    if (use_three) dp[1][max_power-1][1] = 1;
    
    for (int i = 2; i <= n; i++) {
        for (int p2 = 0; p2 <= max_power; p2++) {
            for (int p3 = 0; p3 <= (use_three ? 1 : 0); p3++) {
                long long ways = (long long)dp[i-1][p2][p3] * max(0, divisor_count[p2][p3] - i + 1) % MOD;
                if (p2 < max_power) 
                    ways = (ways + (long long)dp[i-1][p2+1][p3] * (divisor_count[p2][p3] - divisor_count[p2+1][p3])) % MOD;
                if (p3 < 1 && use_three) 
                    ways = (ways + (long long)dp[i-1][p2][p3+1] * (divisor_count[p2][p3] - divisor_count[p2][p3+1])) % MOD;
                dp[i][p2][p3] = ways;
            }
        }
    }
    cout << dp[n][0][0];
    return 0;
}

Three Servers Load Balancing

Given items with weights, distribute them into three servers to minimize the maximum difference in total load. Since individual weights are small (≤30), we use dynamic programming with state f[i][j] indicating whether it's possible to achieve loads i and j on the first two servers. The third server's load is total - i - j. To optimize, we cap i and j at 4030, as beyond that redistribution is always beneficial. We track the count of remaining items per weight using an auxiliary array g[i][j].

#include <iostream>
#include <vector>
using namespace std;
const int MAX_LOAD = 4030;

int main() {
    int n, total = 0;
    cin >> n;
    vector<int> items[31];
    for (int i = 1; i <= n; i++) {
        int w;
        cin >> w;
        total += w;
        items[w].push_back(i);
    }
    
    bool possible[MAX_LOAD+1][MAX_LOAD+1] = {false};
    possible[0][0] = true;
    int remaining[MAX_LOAD+1][MAX_LOAD+1] = {0};
    
    for (int w = 1; w <= 30; w++) {
        if (items[w].empty()) continue;
        int count = items[w].size();
        for (int i = 0; i <= MAX_LOAD; i++) {
            for (int j = 0; j <= MAX_LOAD; j++) {
                if (possible[i][j]) remaining[i][j] = count;
                else remaining[i][j] = -1;
            }
        }
        for (int i = 0; i <= MAX_LOAD; i++) {
            for (int j = 0; j <= MAX_LOAD; j++) {
                if (i >= w && remaining[i-w][j] > remaining[i][j]) 
                    remaining[i][j] = remaining[i-w][j] - 1;
                if (j >= w && remaining[i][j-w] > remaining[i][j]) 
                    remaining[i][j] = remaining[i][j-w] - 1;
            }
        }
        for (int i = 0; i <= MAX_LOAD; i++) {
            for (int j = 0; j <= MAX_LOAD; j++) {
                possible[i][j] = remaining[i][j] >= 0;
            }
        }
    }
    
    int best_diff = total, best_i = 0, best_j = 0;
    for (int i = 0; i <= MAX_LOAD; i++) {
        for (int j = 0; j <= MAX_LOAD; j++) {
            if (possible[i][j]) {
                int third = total - i - j;
                int diff = max(i, max(j, third)) - min(i, min(j, third));
                if (diff < best_diff) {
                    best_diff = diff;
                    best_i = i;
                    best_j = j;
                }
            }
        }
    }
    cout << best_diff;
    return 0;
}

Hero Meet Devil: DNA Sequence Matching

Given a string S and length m, count sequences of length m that have a specific longest common prefix (LCP) state with S. The state is represented as a bitmask of length |S|. For each state s and character c, compute the next state after appending c. Then use dynamic programming where dp[i][s] is the number of sequences of length i ending in state s.

#include <iostream>
#include <cstring>
using namespace std;
const int MOD = 1e9+7;
const int MAX_LEN = 15;

int charToInt(char c) {
    if (c == 'A') return 0;
    if (c == 'C') return 1;
    if (c == 'G') return 2;
    return 3;
}

int computeNextState(int state, int c, const string& s) {
    int len = s.length();
    int new_state = 0;
    int prefix[len+1] = {0};
    for (int i = 1; i <= len; i++) {
        prefix[i] = prefix[i-1] + ((state >> (i-1)) & 1);
    }
    for (int i = 1; i <= len; i++) {
        int match = prefix[i-1];
        if (charToInt(s[i-1]) == c) match++;
        new_state |= (match > prefix[i]) ? (1 << (i-1)) : 0;
    }
    return new_state;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        string s;
        int m;
        cin >> s >> m;
        int len = s.length();
        int total_states = 1 << len;
        int transition[total_states][4];
        for (int state = 0; state < total_states; state++) {
            for (int c = 0; c < 4; c++) {
                transition[state][c] = computeNextState(state, c, s);
            }
        }
        
        int dp[m+1][total_states];
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for (int i = 1; i <= m; i++) {
            for (int state = 0; state < total_states; state++) {
                for (int c = 0; c < 4; c++) {
                    int next = transition[state][c];
                    dp[i][next] = (dp[i][next] + dp[i-1][state]) % MOD;
                }
            }
        }
        
        int result[len+1] = {0};
        for (int state = 0; state < total_states; state++) {
            int count = 0;
            for (int i = 0; i < len; i++) {
                if (state & (1 << i)) count++;
            }
            result[count] = (result[count] + dp[m][state]) % MOD;
        }
        for (int i = 0; i <= len; i++) cout << result[i] << "\n";
    }
    return 0;
}