Problem A

Given n strings each of length m, determine whether there exist four columns satisfying 1 ≤ i < j < k < l ≤ m such that these four columns contain characters 'v', 'i', 'k', 'a' respectively.

Approach: Iterate through columns left to right, searching for each required character sequentially. For each column, scan all strings to find if any contains the current target character. If found, move to the next target character. After processing all columns, check if all four characters were found.

Complexity: O(n²) time, O(1) space.

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T; cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<vector<char>> grid(n, vector<char>(m));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                cin >> grid[i][j];
            }
        }
        
        string target = "vika";
        int idx = 0;
        for (int col = 0; col < m && idx < 4; ++col) {
            for (int row = 0; row < n; ++row) {
                if (grid[row][col] == target[idx]) {
                    idx++;
                    break;
                }
            }
        }
        cout << (idx == 4 ? "YES" : "NO") << '\n';
    }
    return 0;
}

Problem B

Given an array b generated from array a by the rules: b₁ = a₁, and for each i > 1, if a_{i-1} ≤ a_i then push a_i to b, otherwise push a_i twice. Reconstruct a possible a from given b.

Approach: Start with a = {b[1]}. For each subsequent element b[i]:

• If b[i] ≥ b[i-1], append one b[i]
• Otherwise, append two copies of b[i]

This construction guarantees the reverse process yields the original b.

Cmoplexity: O(n) time, O(n) space.

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        vector<int> b(n);
        for (int i = 0; i < n; ++i) cin >> b[i];
        
        vector<int> result;
        result.push_back(b[0]);
        for (int i = 1; i < n; ++i) {
            if (b[i] >= b[i-1]) {
                result.push_back(b[i]);
            } else {
                result.push_back(b[i]);
                result.push_back(b[i]);
            }
        }
        
        cout << result.size() << '\n';
        for (int i = 0; i < (int)result.size(); ++i) {
            cout << result[i] << " \n"[i + 1 == result.size()];
        }
    }
    return 0;
}

Problem C

Given a non-decreasing array a of length n, verify whether the histogram formed by heights a₁, a₂, ..., a_n remains invariant after reflection across y = x.

Approach: For reflection symmetry, the horizontal contribution at each height must match. Use difference array: for each a[i], add 1 to range [1, a[i]]. After processing, the contribution array b should equal a for symmetry to hold. Additionally, ensure all a[i] ≤ n.

Complexity: O(n) time, O(n) space.

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        vector<long long> a(n + 1);
        vector<long long> diff(n + 3, 0);
        bool valid = true;
        
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            if (a[i] > n) {
                valid = false;
            } else {
                diff[1]++;
                diff[a[i] + 1]--;
            }
        }
        
        for (int i = 1; i <= n; ++i) {
            diff[i] += diff[i - 1];
        }
        
        for (int i = 1; i <= n && valid; ++i) {
            if (diff[i] != a[i]) {
                valid = false;
                break;
            }
        }
        
        cout << (valid ? "YES" : "NO") << '\n';
    }
    return 0;
}

Problem D

From a multiset of size n, choosing any two elements yields C(n, 2) distinct combinations. Given m combinations, find the minimum possible multiset size.

Approach: The maximum combinations occur when all elements are distinct: f(x) = C(x, 2). Binary search for the largest x where f(x) ≤ m. If f(x) = m, answer is x. Otherwise, add m - f(x) duplicates to reach exactly m combinations. Each added duplicate increases combinations by 1.

Complexity: O(log M) time, O(1) space.

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T; cin >> T;
    while (T--) {
        long long target; cin >> target;
        long long lo = -1, hi = 2e9 + 1;
        
        while (hi - lo > 1) {
            long long mid = (lo + hi) >> 1;
            long long combos = mid * (mid - 1) / 2;
            if (combos > target) hi = mid;
            else lo = mid;
        }
        
        long long x = lo;
        long long f_x = x * (x - 1) / 2;
        long long answer = x + (target - f_x);
        cout << answer << '\n';
    }
    return 0;
}

Problem E

Given array a of length n, selecting position i yields a_i - d * cnt where cnt is distance from last selection (first selection has cnt = 1). Select at most m positions to maximize total contribution.

Approach: Transform the cost formula. For selections at positions p₁, p₂, ..., p_k:

cost = Σ(a[p_j] - d * (p_j - p_{j-1})) = Σa[p_j] - d * p_k

For each position i as a potential last selection, maintain the sum of largest j positive values (j ≤ m). Use a min-heap to keep track of top values. The answer is max(max_sum - d * i).

Complexity: O(n log n) time, O(n) space.

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T; cin >> T;
    while (T--) {
        int n, m, d;
        cin >> n >> m >> d;
        vector<int> arr(n + 1);
        for (int i = 1; i <= n; ++i) cin >> arr[i];
        
        priority_queue<int, vector<int>, greater<int>> heap;
        long long currentSum = 0, answer = 0;
        
        for (int i = 1; i <= n; ++i) {
            if (arr[i] > 0) {
                heap.push(arr[i]);
                currentSum += arr[i];
            }
            if (heap.size() > m) {
                currentSum -= heap.top();
                heap.pop();
            }
            answer = max(answer, currentSum - 1LL * d * i);
        }
        cout << answer << '\n';
    }
    return 0;
}

Problem F

Two magic types: type W with power w per second, type F with power f per second. In one second, multiple spells of the same type can be cast simultaneously to destroy items if total power exceeds total weight. Given n items with weights, find minimum time to destroy all.

Approach: Split items between the two magic types. For any subset with total weight v assigned to F-magic, time needed is ceil(v / f), while remaining (sum - v) needs ceil((sum - v) / w). Total time is the maximum of these two values. Use 0/1 knapsack to determine which total weights are achievable, then find minimum time across all achievable v.

Complexity: O(n * sum) time, O(sum) space where sum is total weight.

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T; cin >> T;
    while (T--) {
        int w, f, n;
        cin >> w >> f >> n;
        vector<int> weights(n + 1);
        int total = 0;
        for (int i = 1; i <= n; ++i) {
            cin >> weights[i];
            total += weights[i];
        }
        
        vector<char> dp(total + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = total; j >= weights[i]; --j) {
                if (dp[j - weights[i]]) dp[j] = 1;
            }
        }
        
        int bestTime = INT_MAX;
        for (int weight = 0; weight <= total; ++weight) {
            if (dp[weight]) {
                int t1 = (weight + w - 1) / w;
                int t2 = (total - weight + f - 1) / f;
                bestTime = min(bestTime, max(t1, t2));
            }
        }
        cout << bestTime << '\n';
    }
    return 0;
}

Problem G

An array undergoes repeated operations: sort ascending and remove duplicates, then add values [n, n-1, ..., 1] to positions (1-indexed), repeat until one element remains. Process q queries, each modifying one element and returning the final output.

Key Observations:

1. Adding [n, n-1, ..., 1] to a sorted array decreases all adjacent differences by 1.
2. When a differecne becomes 0, that element gets removed in the dedup step.
3. The process iterates exactly max_gap times, where max_gap is the initial maximum difference.
4. The largest element always increases by 1 each iteration and survives to the end.
5. Final answer equals max_element + max_gap.

Data Structure: Maintain two multisets:

• setA: all elements in sorted order
• setB: all adjacent differences (0 initially)

Update Operation: To change a[i] to x:

• Remove old value from setA, update setB accordingly
• Insert new value x into setA, update setB accordingly

Deletion from setA at position it:

• If not first: remove *it - *prev(it) from setB
• If not last: remove *next(it) - *it from setB
• If not first and not last: add *next(it) - *prev(it) to setB

Insertion into setA at position it:

• If not first: add *it - *prev(it) to setB
• If not last: add *next(it) - *it to setB
• If not first and not last: remove *next(it) - *prev(it) from setB

Complexity: O(log n) per update, O(1) to query answer.

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        vector<int> arr(n + 1);
        for (int i = 1; i <= n; ++i) cin >> arr[i];
        
        multiset<int> elements, gaps;
        
        auto insertValue = [&](int val) {
            auto it = elements.insert(val);
            if (it != elements.begin()) {
                gaps.insert(val - *prev(it));
            }
            if (next(it) != elements.end()) {
                gaps.insert(*next(it) - val);
            }
            if (it != elements.begin() && next(it) != elements.end()) {
                gaps.erase(gaps.find(*next(it) - *prev(it)));
            }
        };
        
        auto removeValue = [&](int val) {
            auto it = elements.find(val);
            if (it != elements.begin()) {
                gaps.erase(gaps.find(val - *prev(it)));
            }
            if (next(it) != elements.end()) {
                gaps.erase(gaps.find(*next(it) - val));
            }
            if (it != elements.begin() && next(it) != elements.end()) {
                gaps.insert(*next(it) - *prev(it));
            }
            elements.erase(it);
        };
        
        for (int i = 1; i <= n; ++i) {
            insertValue(arr[i]);
        }
        
        int q; cin >> q;
        vector<int> answers(q + 1);
        for (int i = 1; i <= q; ++i) {
            int idx, x;
            cin >> idx >> x;
            removeValue(arr[idx]);
            arr[idx] = x;
            insertValue(x);
            answers[i] = *elements.rbegin() + *gaps.rbegin();
        }
        
        for (int i = 1; i <= q; ++i) {
            cout << answers[i] << " \n"[i == q];
        }
    }
    return 0;
}