Problem D: DiviDuelo

Approach

This problem requires number theory analysis and prime factorization techniques. The solution involves categorizing cases based on the prime factorization of the input number. The implementation uses advanced primality testing and factorization algorithms including Miller-Rabin and Pollard's rho method.

Implementation

#include<bits/stdc++.h>
#define ll long long
#define int long long
const int MOD = 998244353;
#define PII pair<ll,int>
#define PIII pair<int,PII>
#define INF 0x3f3f3f3f
#define double long double
using ull = std::uint64_t;
#define endl '\n'
#pragma GCC optimize(2)
using namespace std;

namespace NumberTheory {
    /* Montgomery Multiplication Template */
    ull modmul(ull a, ull b, ull M) {
        ll result = a * b - M * ull(1.L / M * a * b);
        return result + M * (result < 0) - M * (result >= (ll) M);
    }

    ull modpow(ull base, ull exp, ull mod) {
        ull answer = 1;
        for (; exp; base = modmul(base, base, mod), exp /= 2)
            if (exp & 1) answer = modmul(answer, base, mod);
        return answer;
    }

    bool checkPrime(ull n) {
        if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;
        std::vector<ull> witnesses = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
        ull s = __builtin_ctzll(n - 1), d = n >> s;
        for (ull a: witnesses) {
            ull power = modpow(a % n, d, n), i = s;
            while (power != 1 && power != n - 1 && a % n && i--) power = modmul(power, power, n);
            if (power != n - 1 && i != s) return 0;
        }
        return 1;
    }

    ull pollardRho(ull n) {
        auto func = [n](ull x, ull k) { return modmul(x, x, n) + 1; };
        ull x = 0, y = 0, cycle = 30, product = 2, iteration = 1, quotient;
        while (cycle++ % 40 || std::gcd(product, n) == 1) {
            if (x == y) x = ++iteration, y = func(x, iteration);
            if ((quotient = modmul(product, std::max(x, y) - std::min(x, y), n))) product = quotient;
            x = func(x, iteration), y = func(func(y, iteration), iteration);
        }
        return std::gcd(product, n);
    }

    std::vector<ull> decompose(ull n) {
        if (n == 1) return {};
        if (checkPrime(n)) return {n};
        ull x = pollardRho(n);
        auto left = decompose(x), right = decompose(n / x);
        left.insert(left.end(), right.begin(), right.end());
        return left;
    }
}

int size;
vector<ull>factors;
int counts[1003];
int outcome = 0;
set<int>uniqueSet;
int inputValue;

void process() {
    cin >> inputValue;
    factors = NumberTheory::decompose(inputValue);
    int working = inputValue;
    sort(factors.begin(), factors.end());
    factors.erase(unique(factors.begin(), factors.end()), factors.end());
    size = factors.size();
    for (int i = 0; i < size; ++i) {
        counts[i] = 0;
        while (working % factors[i] == 0) {
            counts[i]++;
            working /= factors[i];
        }
    }
    if(inputValue == 1){
        cout << "N\n";
        return;
    }
    if(factors.size() == 1){
        if(counts[0] % 2 == 1){
            cout << "Y\n";
        }
        else{
            cout << "N\n";
        }
    }
    else if(factors.size() == 2){
        if(counts[0] == counts[1] && counts[0] == 1){
            cout << "Y\n";
        }
        else{
            cout << "N\n";
        }
    }
    else{
        cout << "N\n";
    }
}

int32_t main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    while (T--) {
        process();
    }
    return 0;
}

Problem E: Expanding STACKS!

Problem Statement

Given two stacks and n numbers with their push/pop sequence records, determine which stack each number enters. Output * if ambiguous.

Approach

Since we don't need to output the order of operations, only identify which numbers belong to each stack, we can model this as a graph partitioning problem. When we have a sequence like +1,+2,-1,-2, number 2 enters after 1 but exits before 1, indicating they're in different stacks. This creates exclusion relationships between numbers. We can use either bipartite graph coloring or union-find with multiple sets to handle these constraints.

Union-Find Implementation

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

struct UnionFindSet {
    int sz;
    vector<int> rank, parent;
    UnionFindSet(int n) {
        initialize(n);
    }
    void connect(int x, int y) {
        if (x == y)
            return;
        if (rank[x] > rank[y])
            parent[y] = x;
        else
            parent[x] = y;
        if (rank[x] == rank[y])
            rank[y]++;
    }
    void initialize(int n) {
        sz = n;
        rank.resize(n + 1);
        parent.resize(n + 1);
        for (int i = 0; i <= sz; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }
    int findRoot(int x) {
        return x == parent[x] ? x : (parent[x] = findRoot(parent[x]));
    }
    void merge(int x, int y) {
        connect(findRoot(x), findRoot(y));
    }
    void compress() {
        for (int i = 0; i < sz; i++)
            findRoot(i);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> sequence(2 * n + 1), left(n + 1, 2 * n), right(n + 1);
    for (int i = 1; i <= 2 * n; i ++) {
        cin >> sequence[i];
        left[abs(sequence[i])] = min(left[abs(sequence[i])], i);
        right[abs(sequence[i])] = max(right[abs(sequence[i])], i);
    }

    vector<pair<int, int>> edges;
    for (int i = 1; i <= 2 * n; i ++) {
        if (sequence[i] < 0) continue;
        vector<int> counter(n + 1);
        for (int j = left[sequence[i]] + 1; j < right[sequence[i]]; j ++) {
            if (sequence[j] > 0) counter[sequence[j]] = 1;
            if (sequence[j] < 0 && counter[-sequence[j]]) counter[-sequence[j]] = 0;
        }
        for (int j = 1; j <= n; j ++) {
            if (counter[j]) {
                edges.emplace_back(sequence[i], j);
            }
        }
    }

    UnionFindSet ds(2 * n);
    for (auto [u, v] : edges) {
        if (ds.findRoot(u) == ds.findRoot(v) || ds.findRoot(u + n) == ds.findRoot(v + n)) {
            cout << "*\n";
            return 0;
        }
        ds.merge(u + n, v);
        ds.merge(u, v + n);
    }

    vector<vector<int>> adjacency(2 * n + 1);
    set<int> selected;
    for (auto [u, v] : edges) {
        u = ds.findRoot(u), v = ds.findRoot(v);
        adjacency[u].emplace_back(v);
        adjacency[v].emplace_back(u);
    }

    string result = "", mapping = "SG";
    for (int i = 1; i <= n; i ++) {
        int root = ds.findRoot(i), valid = 1;
        for (auto neighbor : adjacency[root]) {
            if (selected.count(neighbor)) valid = 0;
        }
        result += mapping[valid];
        if (valid) {
            selected.insert(root);
        }
    }

    cout << result << '\n';

    return 0;
}

Bipartite Graph Coloring Implementation

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
const int MAX_N = 1e3 + 3;
#define PII pair<ll,ll>
#define endl '\n'
#define mem(a, b) memset(a, b, sizeof(a))

int color[MAX_N], graph[MAX_N][MAX_N], n;
bool visited[MAX_N];
bool isValid = 1;

void dfs(int node, int currentColor)
{
	visited[node] = true;
	if(!color[node]){
		color[node] = currentColor;
	}else{
		if(color[node] != currentColor){
			isValid = 0;
			return;
		}
	}
	for (int adjacent = 1; adjacent <= n; adjacent++)
	{
		if (graph[node][adjacent])
		{
			if(color[adjacent] && color[adjacent] == color[node]){
				isValid = 0;
				break;
			}
			if(!visited[adjacent]){
				dfs(adjacent, currentColor ^ 3);
			}
		}
	}
}

int sequence[MAX_N*2], start[MAX_N], end[MAX_N];
int temp[MAX_N];

void solve()
{
	int result = 0;
	cin >> n;
	for(int i = 1; i <= 2*n; i++){
		cin >> sequence[i];
		if(sequence[i] > 0) start[sequence[i]] = i;
		else end[-sequence[i]] = i;
	}
	for(int i = 1; i <= n; i++){
		for(int j = start[i] + 1; j <= end[i] - 1; j++){
			if(sequence[j] > 0){
				temp[sequence[j]]++;
			}else{
				temp[-sequence[j]]--;
			}
		}
		for(int j = 1; j <= n; j++){
			if(temp[j] > 0){
				graph[j][i] = 1;
				graph[i][j] = 1;
			}
			temp[j] = 0;
		}
	}
	for(int i = 1; i <= n; i++){
		if(!visited[i]){
			dfs(i, 1);
		}
	}
	if(isValid){
		for(int i = 1; i <= n; i++){
			if(color[i] == 1){
				cout << 'G';
			}else{
				cout << 'S';
			}
		}cout << endl;
	}else{
		cout << '*';
	}
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0);
	int t = 1;
	while(t--){
		solve();
	}
}

Problem F: Fair Distribution

Problem Statement

Given n pairs (G,R), each pair produces a value x = G + k×R (k>0). Divide the pairs into two groups, assign a value x to each pair in both groups such that the sum of x values in both groups are equal.

Approach

Using Bézout's identity: For integers a,b not both zero, gcd(a,b) divides any linear combination ax+by, and there exist integers x,y such that ax+by = gcd(a,b).

For a group S₁, the sum becomes (ΣGᵢ) + k₁×R₁ + k₂×R₂ + ..., which by Bézout's identity equals G_sum + gcd(R₁,R₂,...) × k'. So each group's total equals G_group + gcd_of_Rs × multiplier.

We need: G₁ + g₁×k₁ = G₂ + g₂×k₂, which rearranges to |G₁ - G₂| = g₂×k₂ - g₁×k₁. By Bézout's identity, this is divisible by gcd(g₁,g₂) = gcd(all R values). So we need to partition such that |G₁ - G₂| is divisible by the overall gcd.

With large n but small total G sum, we use binary representation of counts in knapsack DP to achieve O(√W × W × log(√W)) complexity.

Implementation

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;

	int g = 0, total = 0;
	const int MAX_VAL = 2e5 + 10;

	set<int> uniqueValues;
	vector<int> counts(MAX_VAL);
	for (int i = 1; i <= n; i ++) {
		int G, R;
		cin >> G >> R;
		total += G;
		g = gcd(R, g);
		uniqueValues.insert(G);
		counts[G] ++;
	}

	if (n == 1) {
		cout << "N\n";
		return 0;
	}

	vector<int> dp(total + 1);
	dp[0] = 1;
	for (auto &val : uniqueValues) {
		int available = counts[val];
		for (int k = 1; k <= available; k <<= 1) {
			available -= k;
			i64 weight = k * val;
			for (int j = total; j >= weight; j --)
				dp[j] |= dp[j - weight];
		}
		if (available) {
			i64 weight = available * val;
			for (int j = total; j >= weight; j --)
				dp[j] |= dp[j - weight];
		}
	}

	i64 result = 0, hasZero = uniqueValues.count(0);
	hasZero ^= 1;
	for (int i = hasZero; i <= total - hasZero; i ++) {
		if (dp[i]) {
			if (abs(total - 2 * i) % g == 0) {
				cout << "Y\n";
				return 0;
			}
		}
	}

	cout << "N\n";

	return 0;
}

Problem G: Greek Casino

Approach

Dynamic programming aprpoach where states represent game positions. For each position, calculate expected value based on reachable states through divisors. The transition involves calculating probabilities weighted by the sum of all values.

Implementation

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;

	int total = 0;

	vector<int> values(n + 1);
	for (int i = 1; i <= n; i ++) {
		cin >> values[i];
		total += values[i];
	}

	vector<double> probs(n + 1);
	for (int i = 1; i <= n; i ++) {
		probs[i] = values[i] * 1.0 / total;
	}

	vector g(n + 1, vector<int>());
	for (int i = 1; i <= n; i ++) {
		for (int j = i; j <= n; j += i) {
			g[j].emplace_back(i);
		}
	}

	vector<double> dp(n + 1);
	for (int i = n; i >= 1; i --) {
		double sum1 = 0.0, sum2 = 0.0;
		for (auto &divisor : g[i]) {
			sum1 += probs[divisor];
		}

		for (int j = 2 * i, k = 2; j <= n; j += i, k ++) {
			for (auto &divisor : g[i]) {
				i64 x = 1ll * divisor * k;
				if (lcm(x, i) == j) {
					dp[i] += probs[x] * (dp[j] + 1);
					sum2 += probs[x];
				}
			}
		}

		dp[i] += 1.0 - sum2;
		dp[i] /= (1 - sum1);
	}

	cout << fixed << setprecision(10) << dp[1] - 1 << '\n';

	return 0;
}

Problem K: KMOP

Approach

Dynamic programming where dp[i][j] represents the maximum value achievable using the first j characters of the i-th string. Each character is converted to binary (consonant=0, vowel=1) and processed accordingly.

Implementation

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    string vowels = "AEIOUY";
    vector<string> strings(n);
    for (auto &str : strings) {
        cin >> str;
        if (str.size() > 3) str = str.substr(0, 3);
        for (auto &ch : str) {
            if (~vowels.find(ch)) ch = '1';
            else ch = '0';
        }
    }

    const int inf = INT_MAX >> 1;
    vector<array<int, 3>> dp(n, {inf, inf, inf});
    for (int i = 0, cnt = 0; i < strings[0].size(); i ++) {
        if (strings[0][i] == '0') cnt ++;
        else cnt = 0;
        dp[0][cnt] = min(dp[0][cnt], i + 1);
    }

    for (int x = 1; x < n; x ++) {
        auto curr = strings[x];
        int cnt = 0;
        for (int i = 0; i < curr.size(); i ++) {
            if (curr[i] == '0') cnt ++;
            else cnt = 0;
            if (!cnt) {
                int zeros = 0, idx = 0;
                while (idx < i && curr[idx] == '0') idx++, zeros ++;
                for (int j = 0; j < 3 - zeros; j ++) {
                    dp[x][cnt] = min(dp[x - 1][j] + i + 1, dp[x][cnt]);
                }
            } else {
                for (int j = 0; j + cnt < 3; j ++) {
                    dp[x][cnt + j] = min(dp[x - 1][j] + i + 1, dp[x][cnt + j]);
                }
            }
        }
    }

    int ans = inf;
    for (int i = 0; i < 3; i ++) {
        ans = min(ans, dp[n - 1][i]);
    }

    if (ans == inf) cout << "*\n";
    else cout << ans << '\n';

    return 0;
}

Problem L: LED Matrix

Approach

Simulasion problem. Process each row and check for conflicting patterns where both '-' and '*' appear in required positions.

Implementation

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define LL __int128
#define PII pair<int,int>
#define PIII pair<int,PII>
#define endl '\n'
#define ll unsigned long long
#define Pll pair<ll,ll>
const ll P = 131, N = 1e6 + 3, mod1 = 1610612741, mod2 = 1e9 + 7;

int leftStates[N];
int rightStates[N];

void solve() {
	int n, l, r;
	cin >> n >> l >> r;
	
	for(int i = 1; i <= n; i++){
		int hasDash = 0;
		for(int j = 1; j <= l; j++){
			char x;
			cin >> x;
			if(x == '-'){
				hasDash = 1;
			}
		}
		int hasStar = 0;
		for(int j = 1; j <= r; j++){
			char x;
			cin >> x;
			if(x == '*'){
				hasStar = 1;
			}
		}
		leftStates[i] = hasDash;
		rightStates[i] = hasStar;
	}
	
	int result = 1;
	for(int i = 1; i <= n; i++){
		if(leftStates[i] && rightStates[i]){
			result = 0;
		}
	}
	if(result){
		cout << "Y\n";
	}else{
		cout << "N\n";
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	while (t--) {
		solve();
	}

	return 0;
}