Problem D: Journey to Un'Goro

For small sequence lengths (n ≤ 20), iterate through all possible binary strings of length n. For each string, compute the prefix sum of red characters ('r' represented as 1, 'b' as 0). Count the number of subarrays where the sum of reds is odd. Track the maximum count and collect all configurations achieving it.

For larger n, the maximum number of odd-red subarrays is calculated based on parity:

• If n is odd: ((n+1)/2) * ((n+1)/2)
• If n is even: ((n+1)/2) * ((n+1)/2 + 1)

Generate valid binary patterns using bit manipulation to construct sequences that achieve this maximum, limiting output to 100 examples.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int MAXN = 2e5;
int prefix[MAXN];

void solve() {
    int n;
    cin >> n;
    if (n <= 20) {
        int best = 0;
        vector<string> res;
        for (int mask = 0; mask < (1 << n); ++mask) {
            string seq = "";
            int temp = mask;
            for (int bit = 0; bit < n; ++bit) {
                seq += (temp & 1) ? 'r' : 'b';
                temp >>= 1;
            }
            for (int i = 0; i < n; ++i) {
                prefix[i+1] = prefix[i] + (seq[i] == 'r');
            }
            int cnt = 0;
            for (int l = 0; l < n; ++l) {
                for (int r = l; r < n; ++r) {
                    if ((prefix[r+1] - prefix[l]) & 1) cnt++;
                }
            }
            if (cnt > best) {
                best = cnt;
                res.clear();
                res.push_back(seq);
            } else if (cnt == best) {
                res.push_back(seq);
            }
        }
        cout << best << endl;
        sort(res.begin(), res.end());
        for (int i = 0; i < min((int)res.size(), 100); ++i) {
            cout << res[i] << endl;
        }
    } else {
        int best;
        if (n & 1) best = ((n+1)/2) * ((n+1)/2);
        else best = ((n+1)/2) * ((n+1)/2 + 1);
        cout << best << endl;
        vector<bitset<100000>> patterns;
        int half = (n+1)/2;
        bitset<100000> base = 1;
        base <<= (half - 1);
        patterns.push_back(base);
        if (!(n & 1)) {
            patterns.push_back(base << 1);
        }
        int shift = half;
        base = 1;
        base <<= shift;
        for (int i = 0; i < shift && patterns.size() < 100; ++i) {
            if (i == 0 || i == 1) base.set(i);
            else {
                base.set(i);
                base.reset(i-2);
            }
            patterns.push_back(base);
        }
        for (auto &p : patterns) {
            for (int j = n-1; j >= 0; --j) {
                cout << (p[j] ? 'r' : 'b');
            }
            cout << endl;
        }
    }
}

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

Problem F: Kobolds and Catacombs

Given an array a, create a sorted copy b. Compare the frequency of elements in the original order versus the sorted order using a balance counter. When the counter returns to zero, it indicates a valid partition boundary.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

void solve() {
    int n;
    cin >> n;
    vector<int> original(n), sorted(n);
    for (int i = 0; i < n; ++i) {
        cin >> original[i];
        sorted[i] = original[i];
    }
    sort(sorted.begin(), sorted.end());
    vector<int> sorted_counts(n, 0), original_counts(n, 0);
    map<int, int> idx_map;
    vector<int> unique_vals = sorted;
    unique_vals.erase(unique(unique_vals.begin(), unique_vals.end()), unique_vals.end());
    for (int i = 0; i < unique_vals.size(); ++i) {
        idx_map[unique_vals[i]] = i;
    }
    int balance = 0, partitions = 0;
    for (int i = 0; i < n; ++i) {
        int o_idx = idx_map[original[i]];
        int s_idx = idx_map[sorted[i]];
        original_counts[o_idx]++;
        if (original_counts[o_idx] > sorted_counts[o_idx]) balance++;
        else balance--;
        sorted_counts[s_idx]++;
        if (original_counts[s_idx] < sorted_counts[s_idx]) balance++;
        else balance--;
        if (balance == 0) partitions++;
    }
    cout << partitions << endl;
}

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

Problem G: The Witchwood

Sort the array in descending order and sum the first k elements.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) cin >> arr[i];
    sort(arr.begin(), arr.end(), greater<int>());
    int total = 0;
    for (int i = 0; i < k; ++i) total += arr[i];
    cout << total << endl;
}

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

Problem I: Rise of Shadows

Let h be hours and m be minutes. If 2*A + 1 >= h*m, output h*m. Otherwise, compute g = gcd(h-1, h*m). The result is (h*m / (h*m/g)) * (A/g*2 + 1).

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define __int128_t __int128
#define endl '\n'

void solve() {
    int h, m, A;
    cin >> h >> m >> A;
    int total = h * m;
    if (2 * A + 1 >= total) {
        cout << total << endl;
        return;
    }
    int g = __gcd(h - 1, total);
    __int128_t period = total / g;
    __int128_t base = (2 * (A / g) + 1);
    __int128_t res = (total / period) * base;
    cout << (int)res << endl;
}

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

Problem K: Scholomance Academy

Process events sorted by x-coordinate. Track cumulative additions and removals of positive and ngeative markers. For each critical x-coordinate, compute the ratio of remaining negative markers and the ratio of remaining positive markers. Collect these (x_ratio, y_ratio) points, sort them, and compute the area under the step function they form, capped at (1,1).

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define endl '\n'

void solve() {
    int n;
    cin >> n;
    vector<pair<int, char>> events;
    int pos_total = 0, neg_total = 0;
    for (int i = 0; i < n; ++i) {
        char op;
        int x;
        cin >> op >> x;
        events.push_back({x, op});
        if (op == '+') pos_total++;
        else neg_total++;
    }
    sort(events.begin(), events.end());
    map<ld, ld> points;
    int cur_pos = 0, cur_neg = 0;
    int prev_x = -1;
    for (auto &ev : events) {
        int x = ev.first;
        char op = ev.second;
        if (prev_x != x) {
            if (neg_total > 0) {
                ld x_ratio = (ld)(neg_total - cur_neg) / neg_total;
                ld y_ratio = (ld)(pos_total - cur_pos) / pos_total;
                points[x_ratio] = max(points[x_ratio], y_ratio);
            }
            prev_x = x;
        }
        if (op == '+') cur_pos++;
        else cur_neg++;
    }
    if (neg_total > 0) {
        ld x_ratio = (ld)(neg_total - cur_neg) / neg_total;
        ld y_ratio = (ld)(pos_total - cur_pos) / pos_total;
        points[x_ratio] = max(points[x_ratio], y_ratio);
    }
    vector<pair<ld, ld>> coords;
    for (auto &p : points) coords.push_back(p);
    sort(coords.begin(), coords.end());
    coords.push_back({1.0, 1.0});
    ld area = 0.0;
    for (int i = 0; i < coords.size() - 1; ++i) {
        area += coords[i].second * (coords[i+1].first - coords[i].first);
    }
    cout << fixed << setprecision(10) << area << endl;
}

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