Competition Overview

This mock contest featured relatively weak test data, allowing suboptimal solutions to score significantly higher than expected (often 50+ points above theoretical estimates). The official solutions sometimes relied heavily on pattern recognition and handling specific subtasks rather than pure algorithmic elegance. This highlights a crucial competitive programming strategy: securing partial points by implementing special cases or brute-force solutions early on can provide a safety net and offer insights into the problem's structure before attempting a full solution.

Diary and Shortest Path

The problem presents a Directed Acyclic Graph (DAG) where edge weights are strings. The task is to find the shortest path based on specific string comparison rules (lexicographical order or length-prioritized).

A naive approach involves Topological Sorting followed by Dynamic Programming. However, string concatenation and comparison result in a time complexity of approximately $O(N + M \cdot \sum |w_i|)$. Despite this theoretically high cost, the weak test data allowed this approach to score 96 points.

The correct solution involves "node splitting": expanding an edge with a string weight of length $L$ into a chain of $L$ nodes, each connected by edges representing a single character. This transforms the problem into a standard shortest path problem on a larger graph where weights are uniform (single character steps), allowing greedy selection of the lexicographically smallest path.

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 2000005;
struct Graph {
    struct Edge {
        int to, nxt;
        char val;
    } edge[MAXN];
    int head[MAXN], idx;
    
    void add_edge(int u, int v, char c) {
        edge[++idx] = {v, head[u], c};
        head[u] = idx;
    }
    
    int dist[MAXN];
    
    void bfs_shortest(int src) {
        memset(dist, -1, sizeof(dist));
        queue<int> q;
        dist[src] = 0;
        q.push(src);
        while(!q.empty()) {
            int u = q.front(); q.pop();
            for(int i = head[u]; i; i = edge[i].nxt) {
                int v = edge[i].to;
                if(dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.push(v);
                }
            }
        }
    }
} forward, reverse_graph;

int n, m;
char buffer[MAXN];

void solve(bool strict) {
    // Greedy reconstruction of path
    vector<int> curr_layer, next_layer;
    curr_layer.push_back(1);
    string result = "";
    
    while(true) {
        char min_char = '|';
        next_layer.clear();
        bool reached_end = false;
        
        // Find the minimum character leading to a valid shortest path
        for(int u : curr_layer) {
            for(int i = forward.head[u]; i; i = forward.edge[i].nxt) {
                int v = forward.edge[i].to;
                char w = forward.edge[i].val;
                
                // Pruning: ensure we stay on a shortest path
                if(reverse_graph.dist[v] == -1) continue;
                if(strict && forward.dist[u] + 1 + reverse_graph.dist[v] > forward.dist[n]) continue;
                
                if(w < min_char) {
                    min_char = w;
                    next_layer.clear();
                    next_layer.push_back(v);
                    reached_end = (v == n);
                } else if(w == min_char) {
                    next_layer.push_back(v);
                    if(v == n) reached_end = true;
                }
            }
        }
        
        result += min_char;
        if(reached_end) break;
        curr_layer = next_layer;
    }
    printf("%s ", result.c_str());
}

int main() {
    freopen("shortway.in", "r", stdin);
    freopen("shortway.out", "w", stdout);
    
    scanf("%d%d", &n, &m);
    int node_counter = n;
    
    for(int i = 0; i < m; ++i) {
        int u, v;
        scanf("%d%d%s", &u, &v, buffer);
        int len = strlen(buffer);
        if(len == 1) {
            forward.add_edge(u, v, buffer[0]);
            reverse_graph.add_edge(v, u, buffer[0]);
        } else {
            // Node splitting
            int prev = u;
            for(int j = 0; j < len - 1; ++j) {
                int curr = ++node_counter;
                forward.add_edge(prev, curr, buffer[j]);
                reverse_graph.add_edge(curr, prev, buffer[j]);
                prev = curr;
            }
            forward.add_edge(prev, v, buffer[len-1]);
            reverse_graph.add_edge(v, prev, buffer[len-1]);
        }
    }
    
    forward.bfs_shortest(1);
    reverse_graph.bfs_shortest(n);
    
    solve(true);  // Priority 1: Length then Lexicographical
    solve(false); // Priority 2: Lexicographical only
    
    return 0;
}

Diary and Euler's Totient Function

This problem involves queries on the sum of iterated Euler's totient function $\phi^{(k-b)}(i)$ over a range.

Standard preprocessing using a linear sieve (Euler Sieve) computes $\phi(i)$ in $O(N)$. The iterated function $\phi^{(k)}(i)$ converges to 1 very quickly (typically within $O(\log \log N)$ steps). A basic optimization checking if(current == 1) break reduces the complexity significantly.

The "official" solution for 100 points relies on an observed pattern: for indices $i$ significantly larger than $B$, the value of the iterated totient function becomes constantly 1. This forms an arithmetic progression in the prefix sum array. We only need to compute the values explicitly for a small window near $B$, while values beyond that can be calculated using arithmetic series formulas.

#include <cstdio>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long LL;

const int LIMIT = 50;
int T, B;

map<int, int> phi_cache;
map<pair<int, int>, int> iter_cache;

int compute_phi(int x) {
    if(phi_cache.count(x)) return phi_cache[x];
    int res = x, original = x;
    for(int i = 2; i * i <= x; ++i) {
        if(x % i == 0) {
            while(x % i == 0) x /= i;
            res -= res / i;
        }
    }
    if(x > 1) res -= res / x;
    return phi_cache[original] = res;
}

int iter_phi(int x, int k) {
    if(iter_cache.count({x, k})) return iter_cache[{x, k}];
    int res = x;
    for(int i = 0; i < k; ++i) {
        if(res == 1) break;
        res = compute_phi(res);
    }
    return iter_cache[{x, k}] = res;
}

bool is_prime(int x) {
    if(x < 2) return false;
    for(int i = 2; i * i <= x; ++i) if(x % i == 0) return false;
    return true;
}

LL arithmetic_sum(int n) {
    return 1LL * n * (n + 1) / 2;
}

int prime_below_b;
LL prefix_window_sum;

LL get_sum(int x) {
    if(x <= B) return arithmetic_sum(x);
    
    if(x <= B + LIMIT) {
        LL ans = arithmetic_sum(B);
        int max_phi = prime_below_b - 1;
        for(int i = B + 1; i <= x; ++i) {
            max_phi = max(max_phi, compute_phi(i));
            ans += iter_phi(i, max_phi - B);
        }
        return ans;
    } else {
        LL ans = arithmetic_sum(B) + prefix_window_sum;
        ans += (x - (B + LIMIT)); // Remaining terms are 1
        return ans;
    }
}

int main() {
    freopen("euler.in", "r", stdin);
    freopen("euler.out", "w", stdout);
    
    scanf("%d%d", &T, &B);
    
    // Find largest prime <= B
    for(int i = B; i >= 2; --i) {
        if(is_prime(i)) {
            prime_below_b = i;
            break;
        }
    }
    
    int current_max_phi = prime_below_b - 1;
    for(int i = B + 1; i <= B + LIMIT; ++i) {
        current_max_phi = max(current_max_phi, compute_phi(i));
        prefix_window_sum += iter_phi(i, current_max_phi - B);
    }
    
    while(T--) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%lld\n", get_sum(r) - get_sum(l - 1));
    }
    return 0;
}

Diary and Binary Search Tree

This problem requires calculating the sum of specific LCA (Lowest Common Ancestor) contributions across an optimal BST permutation. The contribution of a node $u$ as an LCA is defined as the product of the number of nodes in its "left" subtree (with smaller values) and its "right" subtree (with larger values).

To maximize the contribusion (or minimize the total cost, depending on problem formulation), the sizes of the left and right partitions should be as close as possible. For each node $u$ with total subtree size $S_u$, we need to select a subset of its children's subtree sizes such that their sum is as close to $S_u/2$ as possible. This is a classic subset sum problem (0/1 Knapsack) solvable in $O(S_u^2)$ per node. With a special check for chain structures, this $O(N^2)$ approach passed the vast majority of test cases due to weak constraints.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 1000005;
int n;
long long total_cost;

struct Edge {
    int to, next;
} edges[MAXN * 2];
int head[MAXN], ecnt;

void add_edge(int u, int v) {
    edges[++ecnt] = {v, head[u]};
    head[u] = ecnt;
}

int subtree_size[MAXN];
vector<int> child_sizes[MAXN];

void dfs(int u, int parent) {
    subtree_size[u] = 1;
    for(int i = head[u]; i; i = edges[i].next) {
        int v = edges[i].to;
        if(v == parent) continue;
        dfs(v, u);
        subtree_size[u] += subtree_size[v];
        child_sizes[u].push_back(subtree_size[v]);
    }
    
    int capacity = (subtree_size[u] - 1) / 2;
    vector<bool> dp(capacity + 1, false);
    dp[0] = true;
    
    for(int sz : child_sizes[u]) {
        for(int j = capacity; j >= sz; --j) {
            if(dp[j - sz]) dp[j] = true;
        }
    }
    
    int best_split = 0;
    for(int j = capacity; j >= 0; --j) {
        if(dp[j]) {
            best_split = j;
            break;
        }
    }
    
    total_cost += 1LL * best_split * (subtree_size[u] - 1 - best_split);
}

int degree[MAXN];

int main() {
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    
    scanf("%d", &n);
    bool is_chain = true;
    
    for(int i = 1; i < n; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        add_edge(u, v);
        add_edge(v, u);
        degree[u]++, degree[v]++;
        if(degree[u] > 2 || degree[v] > 2) is_chain = false;
    }
    
    if(is_chain) {
        // Special case: Chain structure yields 0 contribution
        printf("0\n");
        return 0;
    }
    
    dfs(1, 0);
    printf("%lld\n", total_cost);
    
    return 0;
}

Diary and Text Editor

This problem implements a text editor with Insert, Delete, Replace, Count, and Search operations. The constraints are small enough that a brute-force array implemantation combined with KMP for the Search operation yields a passing score (around 60%). While a Splay Tree or Rope data structure is required for the full solution, the naive approach handles the operations by shifting array elements and iterating through ranges.

#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
using namespace std;

const int MAXLEN = 1000005;
char text[MAXLEN];
int text_len = 0;

char pattern[MAXLEN];
int p_len, fail[MAXLEN];

void build_kmp() {
    fail[0] = -1;
    int j = -1;
    for(int i = 1; i < p_len; ++i) {
        while(j != -1 && pattern[i] != pattern[j+1]) j = fail[j];
        if(pattern[i] == pattern[j+1]) j++;
        fail[i] = j;
    }
}

int kmp_search(int l, int r) {
    int count = 0;
    int j = -1;
    // Text indices in problem are 1-based
    for(int i = l; i <= r; ++i) {
        while(j != -1 && text[i] != pattern[j+1]) j = fail[j];
        if(text[i] == pattern[j+1]) j++;
        if(j == p_len - 1) {
            count++;
            j = fail[j];
        }
    }
    return count;
}

int main() {
    freopen("edit.in", "r", stdin);
    freopen("edit.out", "w", stdout);
    
    int n;
    scanf("%d%s", &n, pattern);
    p_len = strlen(pattern);
    build_kmp();
    
    for(int i = 0; i < n; ++i) {
        char op[10];
        scanf("%s", op);
        
        if(op[0] == 'I') { // Insert
            int pos;
            char str[MAXLEN];
            scanf("%d%s", &pos, str);
            int s_len = strlen(str);
            // Shift text to the right
            for(int k = text_len; k > pos; --k) text[k + s_len - 1] = text[k - 1];
            // Insert string
            for(int k = 0; k < s_len; ++k) text[pos + k] = str[k];
            text_len += s_len;
        } 
        else if(op[0] == 'D') { // Delete
            int l, r;
            scanf("%d%d", &l, &r);
            int sub_len = r - l + 1;
            // Shift text to the left
            for(int k = l; k <= text_len - sub_len; ++k) text[k] = text[k + sub_len];
            text_len -= sub_len;
        }
        else if(op[0] == 'R') { // Replace
            int l, r;
            char str[MAXLEN];
            scanf("%d%d%s", &l, &r, str);
            int sub_len = r - l + 1;
            int s_len = strlen(str);
            
            if(s_len != sub_len) {
                // Adjust size if replacement length differs
                int diff = s_len - sub_len;
                for(int k = text_len; k > r; --k) text[k + diff] = text[k];
                text_len += diff;
            }
            for(int k = 0; k < s_len; ++k) text[l + k] = str[k];
        }
        else if(op[0] == 'C') { // Count char
            int l, r;
            char c[5];
            scanf("%d%d%s", &l, &r, c);
            int cnt = 0;
            for(int k = l; k <= r; ++k) if(text[k] == c[0]) cnt++;
            printf("%d\n", cnt);
        }
        else if(op[0] == 'S') { // Search pattern
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%d\n", kmp_search(l, r));
        }
    }
    return 0;
}