Problem A. Is Your School the Kingdom of Construction I

Approach

The official solution provides a clear construction method. We need to generate exactly k coordinate pairs (x, y) where both coordinates are between 1 and n.

First, we construct a base set of edges forming a connected structure. Then, if additional pairs are needed, we fill in the remaining cells systematically.

Reference Implementation

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int,int>
const int MAXN = 1e6 + 3;

void solve() {
    int n, k;
    cin >> n >> k;
    
    vector<PII> result;
    set<PII> visited;
    
    // Build initial connected structure
    result.push_back({1, 1});
    visited.insert({1, 1});
    
    int currentSize = 1;
    int prevCol = 1;
    
    for (int row = 2; row <= n; ++row) {
        result.push_back({row, prevCol});
        visited.insert({row, prevCol});
        ++currentSize;
        
        result.push_back({row, prevCol + 1});
        visited.insert({row, prevCol + 1});
        ++currentSize;
        
        ++prevCol;
    }
    
    result.push_back({1, n});
    visited.insert({1, n});
    ++currentSize;
    
    // If we already have enough pairs, output current result
    if (currentSize >= k) {
        for (auto [x, y] : result) {
            cout << x << ' ' << y << endl;
        }
        return;
    }
    
    // Fill remaining cells to reach exactly k pairs
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (visited.find({i, j}) == visited.end()) {
                result.push_back({i, j});
                if ((int)result.size() == k) {
                    for (auto [x, y] : result) {
                        cout << x << ' ' << y << endl;
                    }
                    return;
                }
            }
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

Problem D. Tea and Coffee

Approach

The solutoin uses segment trees to maintain prefix minimum values efficiently. We track two types of accumulated costs and repetaedly select the minimum cost item within the current search range.

Key observation: We need to maintain two segment trees - one for the current search window and another for the remaining elements.

Reference Implementation

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

#define int long long
#define PII pair<int,int>
#define INF INT_MAX
#define N 200010
#define LEFT_CHILD p << 1
#define RIGHT_CHILD p << 1 | 1

int n;
int weight[N];
int acc[N], suffixAcc[N];

struct SegmentTree {
    int l, r;
    PII minimum;
} seg1[N << 2], seg2[N << 2];

void pushUp1(int p) {
    seg1[p].minimum = min(seg1[LEFT_CHILD].minimum, seg1[RIGHT_CHILD].minimum);
}

void build1(int p, int l, int r) {
    seg1[p] = {l, r, {0, 0}};
    if (l == r) {
        seg1[p].minimum = {weight[l] - suffixAcc[l], l};
        return;
    }
    int mid = (l + r) >> 1;
    build1(LEFT_CHILD, l, mid);
    build1(RIGHT_CHILD, mid + 1, r);
    pushUp1(p);
}

void update1(int p, int x, int delta) {
    if (seg1[p].l == x && seg1[p].r == x) {
        seg1[p].minimum.first += delta;
        return;
    }
    int mid = seg1[p].l + seg1[p].r >> 1;
    if (x <= mid) update1(LEFT_CHILD, x, delta);
    else update1(RIGHT_CHILD, x, delta);
    pushUp1(p);
}

PII query1(int p, int x, int y) {
    if (x <= seg1[p].l && seg1[p].r <= y) {
        return seg1[p].minimum;
    }
    int mid = seg1[p].l + seg1[p].r >> 1;
    PII res = {INF, 0};
    if (x <= mid) res = min(res, query1(LEFT_CHILD, x, y));
    if (y > mid) res = min(res, query1(RIGHT_CHILD, x, y));
    return res;
}

void pushUp2(int p) {
    seg2[p].minimum = min(seg2[LEFT_CHILD].minimum, seg2[RIGHT_CHILD].minimum);
}

void build2(int p, int l, int r) {
    seg2[p] = {l, r, {0, 0}};
    if (l == r) {
        seg2[p].minimum = {weight[l] - suffixAcc[l], l};
        return;
    }
    int mid = (l + r) >> 1;
    build2(LEFT_CHILD, l, mid);
    build2(RIGHT_CHILD, mid + 1, r);
    pushUp2(p);
}

void update2(int p, int x, int delta) {
    if (seg2[p].l == x && seg2[p].r == x) {
        seg2[p].minimum.first += delta;
        return;
    }
    int mid = seg2[p].l + seg2[p].r >> 1;
    if (x <= mid) update2(LEFT_CHILD, x, delta);
    else update2(RIGHT_CHILD, x, delta);
    pushUp2(p);
}

PII query2(int p, int x, int y) {
    if (y == 0) return {INF, 0};
    if (x <= seg2[p].l && seg2[p].r <= y) {
        return seg2[p].minimum;
    }
    int mid = seg2[p].l + seg2[p].r >> 1;
    PII res = {INT_MAX, 0};
    if (x <= mid) res = min(res, query2(LEFT_CHILD, x, y));
    if (y > mid) res = min(res, query2(RIGHT_CHILD, x, y));
    return res;
}

void solve() {
    int q;
    cin >> n >> q;
    
    for (int i = 1; i <= n; ++i) {
        cin >> weight[i];
        acc[i] = suffixAcc[i] = 0;
    }
    
    build1(1, 1, n);
    
    for (int i = 0; i < q; ++i) {
        int pos, val;
        cin >> pos >> val;
        acc[pos] += val;
    }
    
    suffixAcc[n + 1] = 0;
    for (int i = n; i >= 1; --i) {
        suffixAcc[i] = acc[i] + suffixAcc[i + 1];
    }
    
    build2(1, 1, n);
    
    int boundary = n;
    int currentAcc = 0;
    int totalCost = 0;
    
    for (int i = 1; i <= n; ++i) {
        auto [minVal, pos] = query2(1, 1, boundary);
        minVal += currentAcc;
        
        if (boundary < n) {
            auto [altVal, altPos] = query1(1, boundary + 1, n);
            if (altVal < minVal) {
                minVal = altVal;
                pos = altPos;
            }
        }
        
        if (pos <= boundary) {
            boundary = pos - 1;
            currentAcc = suffixAcc[pos];
        }
        
        update1(1, pos, INF);
        update2(1, pos, INF);
        totalCost += minVal;
        cout << totalCost << ' ';
    }
    cout << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

Problem G. Maximum Path

Approach

The problem asks for the maximum total cost along a path visiting all required points. After analyzing the structure, the answer can be computed directly as the sum of absolute differences between consecutive elements in both arrays.

For aray a of size n and array b of size m: [ \text{Answer} = \sum_{i=1}^{n-1} |a_i - a_{i+1}| + \sum_{j=1}^{m-1} |b_j - b_{j+1}| ]

Reference Implementation

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

#define int long long
#define endl '\n'

void solve() {
    int n, m;
    cin >> n >> m;
    
    vector<int> firstArr(n), secondArr(m);
    
    for (int i = 0; i < n; ++i) {
        cin >> firstArr[i];
    }
    for (int i = 0; i < m; ++i) {
        cin >> secondArr[i];
    }
    
    int result = 0;
    
    for (int i = 1; i < n; ++i) {
        result += llabs(firstArr[i - 1] - firstArr[i]);
    }
    for (int i = 1; i < m; ++i) {
        result += llabs(secondArr[i - 1] - secondArr[i]);
    }
    
    cout << result << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

Problem J. Victor's Dictionary

Approach

This is a subset DP problem. Since word lengths are small, we can use bitmask DP to compute the minimum number of days needed to learn all words.

Define dp[S] as the minimum days required to learn all words in set S, where each state stores:

• First element: number of days used
• Second element: current accumulated word length in the ongoing day

When transitioning, for each word not yet included, we check if it fits in the current day. If not, we start a new day.

Reference Implementation

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

#define int long long
#define PII pair<double, double>

const int MAXN = 1e4 + 10;

int frequency[100];
vector<int> uniqueWords;
PII dpState[1 << 20];
vector<int> groups[20];

void solve() {
    int n, capacity;
    cin >> n >> capacity;
    
    int distinctCount = 0;
    
    for (int i = 0; i < n; ++i) {
        int length;
        cin >> length;
        if (!frequency[length]) {
            ++distinctCount;
            uniqueWords.push_back(length);
        }
        frequency[length]++;
    }
    
    // Group states by number of bits set
    int maxMask = 1 << distinctCount;
    for (int mask = 0; mask < maxMask; ++mask) {
        dpState[mask] = {1e9, 1e9};
        groups[__builtin_popcount(mask)].push_back(mask);
    }
    
    dpState[0] = {0, 0};
    
    // Subset DP
    for (int bitCount = 0; bitCount < distinctCount; ++bitCount) {
        for (int mask : groups[bitCount]) {
            for (int k = 0; k < distinctCount; ++k) {
                if ((mask >> k & 1) == 0) {
                    PII candidate = dpState[mask];
                    
                    if (frequency[uniqueWords[k]] + candidate.second <= capacity) {
                        candidate.second += frequency[uniqueWords[k]];
                    } else {
                        candidate.first++;
                        candidate.second = frequency[uniqueWords[k]];
                    }
                    
                    int newMask = mask ^ (1 << k);
                    dpState[newMask] = min(dpState[newMask], candidate);
                }
            }
        }
    }
    
    int finalMask = maxMask - 1;
    cout << dpState[finalMask].first + (dpState[finalMask].second > 0) << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}