This can be solved by printing the zero-th index of each string in sequence. For example, suppose your strings are $$$a$$$, $$$b$$$, and $$$c$$$. Then in C++, you can use cout << a[0] << b[0] << c[0] << '\n';, and similarly, in Python you can use print(a[0] + b[0] + c[0]). See your preferred language's syntax for how to obtain a given indexed character from a string.

t = int(input())
for _ in range(t):
    inp = input()
    for w in inp.split():
        print(w[0],end="")
    print()

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

What is the condition for $$$l'$$$ and $$$r'$$$ to be valid?

The problem reduces to finding $$$l'$$$ and $$$r'$$$ such that $$$r' - l' = m$$$ and $$$l\leq l' \leq 0 \leq r'\leq r$$$. There are several different approaches; two are outlined below.

One approach which runs in $$$O(1)$$$ time is to case on whether $$$m\leq r$$$. If $$$m\leq r$$$, we can choose $$$l' = 0$$$ and $$$r' = m$$$, and then we see that $$$r' - l' = m - 0 = m$$$ and $$$l \leq 0 \leq 0 \leq m \leq r$$$ as desired. If $$$m \gt r$$$, we can choose $$$l' = r-m$$$ and $$$r' = r$$$, and then we see that $$$r' - l' = r - (r-m) = m$$$ and $$$l \leq r-m \leq 0 \leq r \leq r$$$, where $$$l \leq r-m$$$ holds because $$$r-l = n \geq m$$$.

An alternative approach which runs in $$$O(m)$$$ time is to simply simulate the process; expand in an arbitrary direction which satisfies the desired inequalities until $$$r' - l' = m$$$.

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

void solve() {
    int n, m, l, r; cin >> n >> m >> l >> r;
    int diff = n - m;
    l = abs(l);
    if (l >= diff) {
        l -= diff;
        diff = 0;
    }
    else {
        diff -= l;
        l = 0;
    }
    cout << -l << " " << r - diff << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

How can we find $$$p_i$$$ for $$$2\leq i\leq n$$$? How can we find $$$p_i$$$ for $$$n+1\leq i\leq 2n$$$?

Observe that for all $$$2\leq i\leq n$$$, we can find $$$p_i$$$ by checking $$$G_{1, i-1}$$$. Then for all $$$n+1\leq i\leq 2n$$$, we can find $$$p_i$$$ by checking $$$G_{n, i-n}$$$. Now, we only have to find the value of $$$p_1$$$. However, each value from $$$1$$$ to $$$2n$$$ must appear exactly once in $$$p$$$. Thus, we can simply find the value which has not appeared yet, and choose that as $$$p_1$$$. This can be done by storing which values have been seen in a boolean array, and then finding which one remains false.

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

void solve() {
    int n; cin >> n;
    vector<int> ans(2*n+1, 0);
    vector<bool> used(2*n+1, false);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int x; cin >> x;
            ans[i + j] = x;
            used[x] = true;
        }
    }
    for (int i = 1; i <= 2 * n; i++) {
        if (ans[i] != 0) cout << ans[i] << " ";
        else {
            for (int j = 1; j <= n * 2; j++) {
                if (!used[j]) {
                    used[j] = true;
                    cout << j << " ";
                    break;
                }
            }
        }
    }
    cout << "\n";
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

What would happen if $$$s_1$$$ consists of only $$$L$$$?

First, let us consider a simpler case of the problem: suppose that there is only $$$L$$$ in both $$$s_1$$$ and $$$s_2$$$. Then it is clear that the answer is yes if and only if $$$|s_1| \leq |s_2| \leq 2|s_1|$$$. If this holds (in particular, we also necessitate that $$$s_1$$$ and $$$s_2$$$ consist of only a single character, and the same character), we will call $$$s_2$$$ an extension of $$$s_1$$$.

Now, observe that the problem given is simply the simpler version, repeated several times alternating between $$$L$$$ and $$$R$$$. So we can partition $$$s_1$$$ into "blocks" (where we define a block to be a maximal group of contiguous identical characters). Then the answer is yes if and only if $$$s_2$$$ is the concatenation of extensions of blocks in $$$s_1$$$. For example, consider $$$s_1 = LLLLLRL$$$. We see that this consists of five $$$L$$$s, one $$$R$$$, and one $$$L$$$. So the answer is yes if and only if $$$s_2$$$ consists of between five and ten $$$L$$$s (inclusive), between one and two $$$R$$$s, and between one and two $$$L$$$ 's, concatenated in that order.

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

void solve() {
    string a, b; cin >> a >> b;
    int n = a.size();
    int m = b.size();
    if (m < n || m > 2 * n || a[0] != b[0]) {
        cout << "NO\n";
        return;
    }
    vector<int> aa, bb;
    int cnt = 1;
    for (int i = 1; i < n; i++) {
        if (a[i] != a[i-1]) {
            aa.push_back(cnt);
            cnt = 1;
        }
        else cnt++;
    }
    aa.push_back(cnt);
    cnt = 1;
    for (int i = 1; i < m; i++) {
        if (b[i] != b[i-1]) {
            bb.push_back(cnt);
            cnt = 1;
        }
        else cnt++;
    }
    bb.push_back(cnt);
    if (aa.size() != bb.size()) {
        cout << "NO\n";
        return;
    }
    n = aa.size();
    for (int i = 0; i < n; i++) {
        if (aa[i] > bb[i] || aa[i] * 2 < bb[i]) {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Consider each bit independently.

Suppose we fix $$$k$$$. How can we compute the desired sum quickly? Note that this may require preprocessing.

Here, it suffices to consider each bit independently, because addition is both commutative and associative. For $$$0\leq i \lt 30$$$, let $$$cnt_i$$$ denote the number of elements of $$$a$$$ which have the $$$i$$$-th bit set (where bits are indexed from the least significant bit being the $$$0$$$-th bit); note that these can be found in $$$O(30n)$$$ time (more generally, we need $$$O(\log\max{a_i})$$$ operations per element).

Now, suppose we choose a particular $$$k$$$. Then we can find the sum $$$(a_k\oplus a_1) + (a_k\oplus a_2) \dots + (a_k\oplus a_n)$$$ as follows: for a given bit position $$$i$$$, the number of elements $$$a_j$$$ such that $$$a_k \oplus a_j$$$ has the $$$i$$$-th bit set will be $$$cnt_i$$$ if the $$$i$$$-th bit of $$$a_k$$$ is not set, and $$$n-cnt_i$$$ if the $$$i$$$-th bit of $$$a_k$$$ is set. So we can simply add $$$cnt_i \cdot 2^i$$$ to our sum if the $$$i$$$-th bit of $$$a_k$$$ is not set, and add $$$(n-cnt_i) \cdot 2^i$$$ to our sum if the $$$i$$$-th bit of $$$a_k$$$ is set.

This allows us to compute $$$(a_k\oplus a_1) + (a_k\oplus a_2) \dots + (a_k\oplus a_n)$$$ for any $$$k$$$ in $$$O(30)$$$ time, so we can now compute this sum for all $$$k$$$ in $$$O(30n)$$$ time and output the maximum.

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

void solve() {
    int n; cin >> n;
    int arr[n+1];
    vector<int> cnt(30, 0);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        for (int j = 0; j < 30; j++) {
            cnt[j] += ((arr[i] >> j) & 1);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int tot = 0;
        for (int j = 0; j < 30; j++) {
            bool f = ((arr[i] >> j) & 1);
            if (f) tot += (1 << j) * (n - cnt[j]);
            else tot += (1 << j) * cnt[j];
        }
        ans = max(ans, tot);
    }
    cout << ans << "\n";
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

What would happen if we tried outputting the numbers $$$1, \dots, k, 1, \dots, k, \dots$$$ in the natural reading order? For example, for $$$n=3$$$, $$$m=4$$$, and $$$k=6$$$, we would output the following:

In which cases does this fail?

There are many working constructions for this problem; one of them is to case on whether or not $$$m$$$ is a multiple of $$$k$$$.

Suppose $$$m$$$ is not a multiple of $$$k$$$. For example, consider the second sample, where $$$n=3$$$, $$$m=4$$$, and $$$k=6$$$. Then we can output the numbers $$$1, \dots, k, 1, \dots, k, \dots$$$ in the natural reading order, as follows:

and we see that any two horizontally adjacent elements differ by $$$1\pmod k$$$, whereas any two vertically adjacent elements differ by $$$m\pmod k$$$, so no two adjacent elements are the same, as desired.

Now, suppose $$$m$$$ is a multiple of $$$k$$$. For example, consider the case $$$n=4$$$, $$$m=6$$$, and $$$k=3$$$. Suppose we were to try the above strategy, then we get:

which doesn't work, since vertically adjacent elements are the same. We can fix this by cyclically shifting every other row as follows:

and we see that any two horizontally adjacent elements differ by $$$1\pmod k$$$ as before, whereas any two vertically adjacent elements also differ by $$$1\pmod k$$$, so no two adjacent elements are the same, as desired.

import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n,m,k = map(int,input().split())
    LAST = [-1 for _ in range(m)]
    for i in range(n):
        shift = False
        CUR = [0 for _ in range(m)]
        for j in range(m):
            elm = ((i * m + j) % k) + 1
            if elm == LAST[j]:
                shift = True
            CUR[j] = elm
        if shift:
            CUR = [CUR[(j+1)%m] for j in range(m)]
        print(*CUR)
        LAST = CUR

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Note that reversing an array then pushing an element to the back is similar to simply pushing an element to the front. Thus, we would like to push elements to both ends of the array. What data structure supports this?

What other values do we need to maintain in order to keep track of score?

We can solve this using a deque. Let $$$score$$$ denote the current score, and $$$rscore$$$ denote the score of the array if it were backwards. Let $$$size$$$ denote the size of the array, and $$$sum$$$ denote the sum of the array. Then we consider how these three values change as each operation is performed.

Suppose operation 1 is performed. This is equivalent to popping the back element of the array and pushing it in the front. When you pop the back element of the array, $$$score$$$ decreases by $$$a_n \cdot size$$$. Then when you push it to the front, $$$score$$$ increases by $$$sum$$$ because $$$a_n$$$ is pushed to the first spot and every element from $$$a_1$$$ to $$$a_{n-1}$$$ moves forward one spot. Notice that $$$rscore$$$ changes in the reverse way; this is equivalent to popping the front element of the array and pushing it to the back. When you pop the front element of the array, $$$rscore$$$ decreases by $$$sum$$$, and when you push it to the back, $$$rscore$$$ increases by $$$a_n \cdot size$$$. Note that $$$size$$$ and $$$sum$$$ remain unchanged.

Suppose operation 2 is performed. Then we swap $$$score$$$ and $$$rscore$$$, and we also want to "reverse" the array. However, it is costly to entirely reverse the deque. Instead, we will set a flag to indicate that the array has been reversed (and similarly, if the flag is already set, we will unset it). If the flag is set, we simply switch the front and back ends whenever we access or modify the deque while performing operations 1 or 3.

Suppose operation 3 is performed. Then we see that $$$size$$$ increases by $$$1$$$ and $$$sum$$$ increases by $$$k$$$. Then $$$score$$$ increases by $$$k \cdot size$$$ and $$$rscore$$$ increases by $$$sum$$$ (using the new value of $$$sum$$$), by identical reasoning to that in operation 1.

Additional optimization: we don't actually have to maintain $$$rscore$$$; we can obtain it with the expression: $$$(n+1)\sum_{i=1}^na_i-score$$$. This is because $$$score + rscore = (n+1)\sum_{i=1}^na_i$$$ since the $$$i$$$-th term is counted $$$i$$$ times in $$$score$$$ and $$$n+1-i$$$ times in $$$rscore$$$.

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

void solve() {
    int norm = 0, rev = 0;
    int q; cin >> q;
    int tot = 0;
    int n = 0;
    deque<int> qNorm, qRev;
    int p = 0;
    while (q--) {
        int s; cin >> s;
        if (s == 1) {
            int last = qNorm.back();
            qNorm.pop_back();
            qNorm.push_front(last);
            norm += (tot - last);
            norm -= last * n;
            norm += last;

            last = qRev.front();
            qRev.pop_front();
            qRev.push_back(last);
            rev -= (tot - last);
            rev += last * n;
            rev -= last;
        }
        else if (s == 2) {
            swap(rev, norm);
            swap(qNorm, qRev);
        }
        else if (s == 3) {
            n++;
            int k; cin >> k;
            qNorm.push_back(k);
            qRev.push_front(k);
            norm += k * n;
            rev += tot;
            rev += k;
            tot += k;
        }
        cout << norm << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

What must the value of $$$a[i]$$$ be in order for $$$k$$$ to change?

Can we use this to bound the number of times $$$k$$$ changes?

Consider a particular query. We make the following two observations: first, the value of $$$k$$$ only changes if $$$a[i]$$$ is a divisor of $$$k$$$, and second, if there exists $$$a[i_1] = a[i_2]$$$ with $$$l\leq i_1 \lt i_2 \leq r$$$, then the value of $$$k$$$ will not change at $$$i=i_2$$$ (because after the iteration $$$i=i_1$$$, we have that $$$k$$$ is no longer divisible by $$$a[i_2]$$$).

This allows us to bound the number of times $$$k$$$ changes by $$$d(k)$$$, where $$$d(k)$$$ is the number of divisors of $$$k$$$. Note that the divisors of $$$d(k)$$$ can be found in $$$O(\sqrt{k})$$$ time by checking if $$$a$$$ divides $$$k$$$ for every $$$a$$$ from $$$2$$$ to $$$\sqrt{k}$$$, and if so, $$$a$$$ and $$$\frac{k}{a}$$$ are both divisors of $$$k$$$. Furthermore, at the scale constrained by the problem bounds, $$$d(k)$$$ is around $$$O(\sqrt[3]{k})$$$, so we only have to update $$$k$$$ at most $$$O(\sqrt[3]{k})$$$ times.

Now, we would like to find the first time each divisor of $$$k$$$ appears in $$$a[l], \dots, a[r]$$$. This can be done by storing the array $$$a$$$ in a map, where each value is mapped to a vector of indices where that values appears. Then for a given divisor of $$$k$$$, we can use lower_bound() (or generally, binary search) to find the smallest index at or after $$$l$$$ where this divisor appears, and we can check if it is no greater than $$$r$$$.

Now, we have a list of indices at which $$$k$$$ might change. So, suppose that $$$k$$$ changes to $$$k'$$$ at index $$$i_1$$$, and then changes to $$$k' '$$$ at index $$$i_2$$$ (and these are adjacent changes). Then we know that we have a value of $$$k'$$$ from $$$i=i_1$$$ to $$$i_2-1$$$, so we can add $$$k' \cdot (i_2 - i_1)$$$ to $$$ans$$$. We can then do this for all changes. This allows us to solve the problem in $$$O(n\log{n})$$$ preprocessing time and $$$O(\sqrt{k} + d(k)\log{n})$$$ time per query.

There are a few ways to optimize the runtime further, if your implementation is too slow. We can use a vector (of vectors) instead of a map, since $$$A = \max a_i = 10^5$$$ is reasonably small. Note that instantiating a vector of this size in every test case is too slow, so you may have to instantiate it globally and clear the vectors that were used after each test case.

Another optimization is to preprocess divisors instead of computing them on the spot. We can compute and store the divisors of all integers $$$2\leq a_i\leq 10^5$$$ in $$$O(A\log A)$$$ time in a vector of vectors where $$$divisor[a_i]$$$ contains all divisors of $$$a_i$$$ as follows: for all $$$2\leq i\leq A$$$, we push $$$i$$$ into $$$divisors[j]$$$ for all multiples $$$j$$$ of $$$i$$$. (The runtime follows from the fact that there are $$$\lfloor\frac{A}{i}\rfloor$$$ multiples of $$$i$$$ which are at most $$$A$$$, so across all $$$i$$$, we have at most $$$\frac{A}{1} + \frac{A}{2} + \cdots + \frac{A}{A} = A(\frac{1}{1} + \cdots + \frac{1}{A}) = AH(A) = O(A\log A)$$$ computations). This allows us to remove the $$$\sqrt{k}$$$ term in the runtime of each query.

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

void solve() {
    map<int, vector<int>> pos;
    map<int, int> ptr;
    int n, q; cin >> n >> q;
    int arr[n+1];
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        pos[arr[i]].push_back(i);
        ptr[arr[i]] = 0;
    }
    vector<tuple<int, int, int, int>> qr(q);
    int c = 0;
    for (auto &[l, r, v, i]: qr) {
        cin >> v >> l >> r;
        i = c++;
    }
    vector<int> anss(q);
    sort(qr.begin(), qr.end());
    int prevL = 1;
    for (auto [l, r, v, idd]: qr) {
        for (int j = prevL; j < l; j++) {
            ptr[arr[j]]++;
        }
        prevL = l;
        vector<pair<int, int>> facts;
        for (int i = 1; i * i <= v; i++) {
            if (v % i == 0) {
                int fact1 = v / i;
                if (!(pos[fact1].size() == 0 || ptr[fact1] >= pos[fact1].size() || pos[fact1][ptr[fact1]] > r || fact1 == 1)) {
                    facts.push_back({pos[fact1][ptr[fact1]], fact1});
                }
                int fact2 = i;
                if (fact2 == fact1) continue;
                if (!(pos[fact2].size() == 0 || ptr[fact2] >= pos[fact2].size() || pos[fact2][ptr[fact2]] > r || fact2 == 1)) {
                    facts.push_back({pos[fact2][ptr[fact2]], fact2});
                }
            }
        }
        sort(facts.begin(), facts.end());
        int pr = l;
        int ans = 0;
        for (auto [idx, val]: facts) {
            int rr = idx - pr;
            ans += v * rr;
            while (v % val == 0) v /= val;
            pr = idx;
        }
        if (facts.empty()) ans = v * (r - l + 1);
        else ans += (r - pr + 1) * v;
        anss[idd] = ans;
    }
    for (int i = 0; i < q; i++) cout << anss[i] << "\n";
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve