A. Dual Trigger (Thinking Problem)

Problem Statement

We have n lamps numbered 1 to n arranged in a row, all off initially. You can perform any number of operations (including zero):

• Choose two non-adjacent unlit lamps, and turn both on.

Given a target configuration s where s_i = 1 means lamp i is on, determine if it is possible to reach this configuration.

Analysis

• If the total number of on lamps is odd, it is impossible to reach, since every operation turns on exactly 2 lamps.
• If there are exactly 2 on lamps, they must be non-adjacent (we cannnot select adjacent lamps in a single operation), so adjacent 2 on lamps make it impossible.
• All other cases with even number of on lamps are possible.

Solution Code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int test_cases;
    cin >> test_cases;
    while (test_cases--) {
        int n;
        string config;
        cin >> n >> config;
        vector<int> on_positions;
        for (int i = 0; i < n; i++) {
            if (config[i] == '1') {
                on_positions.push_back(i);
            }
        }
        if (on_positions.size() % 2 != 0) {
            cout << "NO\n";
            continue;
        }
        if (on_positions.size() == 2 && on_positions[0] + 1 == on_positions[1]) {
            cout << "NO\n";
        } else {
            cout << "YES\n";
        }
    }
    return 0;
}

B. Battle Cows (Greedy Algorithm)

Problem Statement

n cows participate in a coding competition, each cow i has a unique rating a_i and starts at position i. There are n-1 matches held in order:

1. The first match is between cows at position 1 and 2.
2. Each subsequent match is between the winner of the previous match and the cow at position i+1.
3. The cow with higher rating always wins and advances to the next match.

You own the cow starting at position k, and you want it to win as many matches as possible. You are allowed to swap your cow's position with any other cow at most once (or not swap at all). Find the maximum number of matches your cow can win.

Analysis

We only need to check two candidate scenarios to get the maximum:

1. Swap your cow to the first position, count how many consecutive matches it wins starting from the first match.
2. Find the first cow stronger than your cow that comes before position k. If such a cow exists, swap your cow to that position, then count how many consecutive weaker cows it beats starting from that position until the next stronger cow.

Take the maximum value from all valid candidates.

Solution Code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int test_cases;
    cin >> test_cases;
    while (test_cases--) {
        int n, k;
        cin >> n >> k;
        vector<int> ratings(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> ratings[i];
        }
        int my_rating = ratings[k];
        int first_bigger = 0;
        for (int i = 1; i < k; i++) {
            if (ratings[i] > my_rating) {
                first_bigger = i;
                break;
            }
        }
        int max_wins = 0;
        if (first_bigger != 0) {
            int current = first_bigger > 1 ? 1 : 0;
            for (int i = first_bigger + 1; i <= n; i++) {
                if (my_rating > ratings[i]) current++;
                else break;
            }
            max_wins = current;
        }
        int swap_front_wins = 0;
        if (k != 1) {
            swap(ratings[1], ratings[k]);
            for (int i = 2; i <= n; i++) {
                if (ratings[1] > ratings[i]) swap_front_wins++;
                else break;
            }
        }
        cout << max(max_wins, swap_front_wins) << "\n";
    }
    return 0;
}

C. Ticket Hoarding (Greedy Algorithm)

Problem Statement

You need to buy k tickets for your employees, one per employee. Tickets are sold over n days, and each ticket costs a_i on day i. The organizer has these rules to prevant hoarding:

1. You can buy at most m tickets per day.
2. If you buy x tickets on day i, every ticket bought on any day after i will increase in price by x.

Find the minimal total cost to buy exactly k tickets.

Analysis

An interesting observation: the total final cost only depends on which days you buy tickets from, not the order you buy them in. If you buy t_i tickets from day i, the contribution of day i's tickets to total cost is t_i * (a_i + sum_{j < i} t_j), so we can just greedily buy as many as possible from the cheapest base price days first, which gives the minimal total cost.

Solution Code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int test_cases;
    cin >> test_cases;
    while (test_cases--) {
        int n, m, k;
        cin >> n >> m >> k;
        vector<int> prices(n + 1);
        vector<int> sorted_days(n);
        for (int i = 1; i <= n; i++) {
            cin >> prices[i];
            sorted_days[i - 1] = i;
        }
        sort(sorted_days.begin(), sorted_days.end(), [&](int x, int y) {
            return prices[x] < prices[y];
        });
        ll total_cost = 0;
        int bought = 0;
        int remaining = k;
        for (int day : sorted_days) {
            int buy = min(m, remaining);
            total_cost += (ll)buy * (prices[day] + bought);
            bought += buy;
            remaining -= buy;
            if (remaining == 0) break;
        }
        cout << total_cost << "\n";
    }
    return 0;
}

D. Buying Jewels (Thinking Problem)

Problem Statement

Alice has n coins, and Bob wants to set up his shop such that Alice ends up buying exactly k jewels. Bob can open at most 60 stalls, each with unlimited jewels, each stall's price can be any integer between 1 and 1e18.

Alice shops greedily: she visits stalls from 1 to last, buys as many jewels as possible at each stall with her remaining coins, then moves to the next. Help Bob set the prices, or determine it is impossible.

Analysis

We can split into edge cases:

1. If n = k: just open 1 stall with price 1, Alice buys exactly n = k jewels.
2. If k = 1: just open 1 stall with price n, Alice buys exactly 1 jewel.
3. If 2*k <= n + 1: open two stalls with prices (n - k + 1, 1). Alice buys 1 jewel from the first stall, then k - 1 from the second, total exactly k.
4. All other cases are impossible.

Solution Code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int test_cases;
    cin >> test_cases;
    while (test_cases--) {
        ll n, k;
        cin >> n >> k;
        if (n == k) {
            cout << "YES\n1\n1\n";
            continue;
        }
        if (k == 1) {
            cout << "YES\n1\n" << n << "\n";
            continue;
        }
        if (2 * k <= n + 1) {
            cout << "YES\n2\n" << (n - k + 1) << " 1\n";
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}

E. No Palindromes (String Processing)

Problem Statement

Given a string s of lowercase Latin characters, split it into one or more substrings such that none of the substrings is a palindrome. Output whether it is possible, and if yes output the split.

Analysis

• If the entire string is already not a palindrome, we can just output it as a single split, which is valid.
• If the entire string is a palindrome, only the following cases are impossible:
  1. Length of string is less than 4.
  2. All characters are the same, or n-1 characters are the same.
  3. The string is an alternating repetition of two different characters (like ababababa) with odd length.

For all other cases, we can always split into two non-palindromic substrings. We use double hashing to check if a substring is a palindrome efficiently.

Solution Code

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

struct DoubleHash {
    const ll base[2] = {29, 31};
    const ll mod[2] = {(ll)1e9 + 9, 998244353};
    array<vector<ll>, 2> forward_hash;
    array<vector<ll>, 2> power;

    void init(string s) {
        int n = s.size();
        s = " " + s;
        forward_hash[0].resize(n + 1); forward_hash[1].resize(n + 1);
        power[0].resize(n + 1); power[1].resize(n + 1);
        for (int i = 0; i < 2; i++) {
            power[i][0] = 1;
            for (int j = 1; j <= n; j++) {
                power[i][j] = power[i][j - 1] * base[i] % mod[i];
                forward_hash[i][j] = (forward_hash[i][j - 1] * base[i] + s[j]) % mod[i];
            }
        }
    }

    pair<ll, ll> get_hash(int l, int r) {
        pair<ll, ll> res;
        res.first = (forward_hash[0][r] - forward_hash[0][l - 1] * power[0][r - l + 1]) % mod[0];
        res.second = (forward_hash[1][r] - forward_hash[1][l - 1] * power[1][r - l + 1]) % mod[1];
        res.first = (res.first + mod[0]) % mod[0];
        res.second = (res.second + mod[1]) % mod[1];
        return res;
    }
};

bool is_equal(DoubleHash &h1, int l1, int r1, DoubleHash &h2, int l2, int r2) {
    return h1.get_hash(l1, r1) == h2.get_hash(l2, r2);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int test_cases;
    cin >> test_cases;
    while (test_cases--) {
        string s;
        cin >> s;
        int n = s.size();
        string rev_s = s;
        reverse(rev_s.begin(), rev_s.end());
        DoubleHash forward, reverse;
        forward.init(s); reverse.init(rev_s);

        if (!is_equal(forward, 1, n, reverse, 1, n)) {
            cout << "YES\n1\n" << s << "\n";
            continue;
        }

        int same_count = count(s.begin(), s.end(), s[0]);
        if (same_count >= n - 1) {
            cout << "NO\n";
            continue;
        }

        bool alternating = true;
        for (int i = 2; i < n; i++) {
            if (s[i] != s[i - 2]) {
                alternating = false;
                break;
            }
        }
        if (n < 4 || (alternating && (n % 2 == 1))) {
            cout << "NO\n";
            continue;
        }

        bool found = false;
        for (int i = 1; i < n; i++) {
            bool first_not_pal = !is_equal(forward, 1, i, reverse, n - i + 1, n);
            bool second_not_pal = !is_equal(forward, i + 1, n, reverse, 1, n - i);
            if (first_not_pal && second_not_pal) {
                cout << "YES\n2\n" << s.substr(0, i) << " " << s.substr(i, n - i) << "\n";
                found = true;
                break;
            }
        }
    }
    return 0;
}