Problem A - Sum of Two Smallest Numbers

Statement: Given three integers, output the sum of the two smallest values.

Solution: Subtract the maximum value from the total sum.

int a, b, c; cin >> a >> b >> c;
cout << a + b + c - max({a, b, c}) << endl;

Problem B - Finding the Longest Even Prefix

Statement: A string is considered "even" if it consists of two identical substrings concatenated together. Given a lowercase string S that satisfies this property, find the maximum length of an "even" string obtainable by removing one or more characters from the end of S.

Solution: The desired prefix length must be even. Using the KMP prefix function (nxt array), check positions from n-2 downwards. A valid even prefix of length i exists when nxt[i] equals i/2.

string str; cin >> str;
int len = str.size();
str = " " + str;

vector<int> pi(len + 1);
for (int i = 1, j = 0; i < len; i++) {
    while (j > 1 && str[j + 1] != str[i + 1]) {
        j = pi[j];
    }
    if (str[j + 1] == str[i + 1]) {
        j++;
    }
    pi[i + 1] = j;
}

for (int i = len - 2; i >= 0; i -= 2) {
    if (pi[i] == i / 2) {
        cout << i << endl;
        return;
    }
}

Time complexity: O(n)

Problem C - Alternating Insertions

Statement: Given a sequence a_1 through a_n, perform n operations on an initially empty array b. Each operation i appends a_i to b, then reverses b. Output the final array.

Solution: Analyzing the pattern reveals that elements alternate between front and back insertions. When processing in reverse, a_n always goes to the front, a_{n-1} to the back, a_{n-2} to the front, and so on.

The insertion rule:

• Insert at the front when i ≡ n (mod 2)
• Insert at the back otherwise

Use a deque for efficient front and back operations.

int n; cin >> n;
deque<long long> dq;

for (int i = 1; i <= n; i++) {
    long long val; cin >> val;
    if (i % 2 == n % 2) {
        dq.push_front(val);
    } else {
        dq.push_back(val);
    }
}

vector<long long> result(dq.begin(), dq.end());
for (int i = 0; i < result.size(); i++) {
    cout << result[i] << (i == result.size() - 1 ? '\n' : ' ');
}

Problem D - Counting Distinct Subsequences

Statement: Given a sequence of length n+1 containing all integers from 1 to n exactly once, except one integer x that appears twice, count the number of distinct subsequences of length k for each k from 1 to n+1. Answer modulo 10^9 + 7.

Solution: This resembles counting subsequences from a permutation (which would be C(n, k)), but the duplicate element x introduces complications.

Let A denote the set of elements positioned between the two occurrences of x. Define d = |A| + 2 (the span including both x's).

Classifying subsequences by their relationship to x:

• Contains both x's: unique
• Contains no x's: unique
• Contains one x and atleast one element from A: unique
• Contains one x and no elements from A: counted twice

The overcounted subsequences consist of exactly one x plus any k-1 elements from outside A. There are C(n+1-d, k-1) such pairs choosing the other k-1 elements, but since we counted one x twice, we need to subtract half of that.

Final formula:

answer[k] = C(n+1, k) - C(n+1-d, k-1)

Handle negative values by adding MOD before taking the modulo.

int n; cin >> n;
vector<int> arr(n + 2);
unordered_map<int, int> pos;

int duplicateSpan = 0;

for (int i = 1; i <= n + 1; i++) {
    cin >> arr[i];
    if (pos.find(arr[i]) == pos.end()) {
        pos[arr[i]] = i;
    } else {
        duplicateSpan = i - pos[arr[i]] + 1;
    }
}

for (int k = 1; k <= n + 1; k++) {
    long long res = (nCr(n + 1, k) - nCr(n + 1 - duplicateSpan, k - 1)) % MOD;
    if (res < 0) res += MOD;
    cout << res << endl;
}

Time complexity: O(n) with precomputed factorials for binomial coefficients.