Note that $$$(a_i \bmod a_{i + 1}) \lt a_{i + 1}$$$.

$$$a_{i + 2} = (a_i \bmod a_{i + 1}) \lt a_{i + 1}$$$ and $$$a_2 \le a_1$$$ mean that the sequence $$$a$$$ must be non-increasing. On the other hand, there is only one permutation of the sequence $$$b$$$ that can be non-increasing.

t = int(input())
for tt in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    a = a[::-1]
    valid = True
    for i in range(2, n):
        if a[i] != a[i - 2] % a[i - 1]:
            print(-1)
            valid = False
            break
    if valid:
        print(a[0], a[1])

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> b(n);
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    sort(b.rbegin(), b.rend());
    bool ok = true;
    for (int i = 0; i < n - 2; i++) {
        if (b[i + 2] != b[i] % b[i + 1]) {
            ok = false;
            break;
        }
    }
    if (ok) {
        cout << b[0] << " " << b[1] << "\n";
    } else {
        cout << -1 << "\n";
    }
}

int main() {
    int t;
    cin >> t;
    
    while (t--) {
        solve();
    }
}

Amazing

Good

Ok

Bad

Terrible

tt = int(input())
for tc in range(tt):
    n = int(input())
    if n == 10:
        print(-1)
    elif n % 12 == 10:
        print(22, n - 22)
    else:
        print(n % 12, n - (n % 12))

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
    long long n;
    cin >> n;
    if (n == 10) {
        cout << "-1\n";
    } else if (n % 12 == 10) {
        cout << "22 " << n - 22 << "\n";
    } else {
        cout << n % 12 << " " << n - (n % 12) << "\n";
    }
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
 
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

Amazing

Good

Ok

Bad

Terrible

Intuitively, the farther a vessel from the empty one, the more water there can be. Fix the empty vessel and try to explicitly find the formula for the maximum possible water height in each of the other vessels.

t = int(input())
for tc in range(t):
    n = int(input())
    h = list(map(int, input().split()))
    ans = []
    for s in range(n):
        w1 = [0] * n
        w2 = [0] * n
        for i in range(1, n):
            w1[(s + i) % n] = max(w1[(s + i - 1) % n], h[(s + i - 1) % n])
        for i in range(1, n):
            w2[(s + n - i) % n] = max(w2[(s + n - i + 1) % n], h[(s + n - i) % n])
        w = [min(w1[i], w2[i]) for i in range(n)]
        ans.append(sum(w))
    print(*ans)

#include <bits/stdc++.h>

using namespace std;
 
void solve() {
    int n;
    cin >> n;
    vector<int> h(n);
    for (int i = 0; i < n; i++) cin >> h[i];
    
    for (int s = 0; s < n; s++) {
        vector<int> w1(n), w2(n), w(n);
        for (int i = 1; i < n; i++) {
            w1[(s + i) % n] = max(w1[(s + i - 1) % n], h[(s + i - 1) % n]);
        }
        for (int i = 1; i < n; i++) {
            w2[(s + n - i) % n] = max(w2[(s + n - i + 1) % n], h[(s + n - i) % n]);
        }
        for (int i = 0; i < n; i++) {
            w[i] = min(w1[i], w2[i]);
        }
        cout << accumulate(w.begin(), w.end(), 0ll) << " ";
    }
    cout << "\n";
}
 
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
 
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

Amazing

Good

Ok

Bad

Terrible

Let $$$A = a_1$$$, $$$B = a_{2^k + 1}$$$, $$$C = A \oplus B$$$.

Try to write out some values of $$$a$$$, for example, for $$$k = 3$$$.

$$$A \oplus B = C$$$, $$$B \oplus C = A$$$, $$$C \oplus A = B$$$.

Let's see how $$$a$$$ changes step by step:

• a = [A, ?, ?, ?, ?, ?, ?, ?, B];
• a = [A, ?, ?, ?, C, ?, ?, ?, B];
• a = [A, ?, B, ?, C, ?, A, ?, B];
• a = [A, C, B, A, C, B, A, C, B].

Try to notice and prove a pattern.

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n), b(n);
    char g;
    for (int i = 0; i < n; ++i) {
        cin >> g;
        a[i] = g - '0';
    }
    for (int i = 0; i < n; ++i) {
        cin >> g;
        b[i] = g - '0';
    }
    vector<int> c(4);
    for (int i = 0; i < n; ++i) {
        int x = 2 * a[i] + b[i];
        c[x]++;
    }
        
    if (k % 2) {
        long long p = 0, q = 0, r = 0;
        p = c[0] + c[1];
        q = c[0] + c[3];
        r = c[0] + c[2];
        cout << (((1ll << k) + 1) / 3) * (p * (n-p) + q * (n - q) + r * (n - r)) << "\n";
    } else {
        long long p = 0, q = 0, r = 0;
        p = c[0] + c[1];
        q = c[0] + c[2];
        r = c[0] + c[3];
        cout << (((1ll << k) + 1) / 3) * (p * (n-p) + q * (n - q) + r * (n - r)) + p * (n - p) + q * (n - q) << "\n";
    }
}

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

There is a rather straightforward solution that works in $$$\mathcal{O}(nk \log k)$$$.

Read the first two hints for Solution 1. Prove that each $$$a_i \in [A, B, C]$$$.

For every pair of bits $$$(x, y)$$$, count the number of positions $$$h$$$ for which the $$$h$$$-th bits of $$$a_1$$$ and $$$a_{2^k+1}$$$ are $$$x$$$ and $$$y$$$ respectively. Continue recursively.

Use caching.

Let the answer for the problem where $$$a_1 = A$$$, $$$a_{2^k+1} = B$$$ and $$$k = l$$$ be $$$F(l, A, B)$$$.

Then, as we write a value $$$A \oplus B$$$ in the middle of the array on the first step and then continue recursively, like for $$$k = l - 1$$$, $$$F(l, A, B) = F(l - 1, A, A \oplus B) + F(l - 1, A \oplus B, B) - [\text{product of the } 0 \text{ and } 1 \text{ bit counts for } A \oplus B]$$$.

Referring to the proof in Solution 1 that each $$$a_i \in [A, B, C]$$$, for each $$$l$$$ the function's value must be calculated for different pairs of $$$(A, B)$$$ at most $$$6$$$ times, thus, if we use a map for caching the answer of $$$F$$$, we will make not more than $$$6k$$$ calls to it, which makes the time complexity $$$\mathcal{O}(n + k \log k)$$$.

#include <bits/stdc++.h>

using namespace std;
#define int long long

int n, k, a, b, c;
string p, q, r;

int get(string &s) {
    int a = 0, b = 0;
    for (char c : s)
        if (c == '0') a++;
        else b++;
    return a * b;
}

map<array<int, 4>, int> mp;

int solve(int l, int a, int b, int c) {
    array<int, 4> t = {l, a, b, c};
    if (mp.find(t) == mp.end()) {
        if (l == 0) mp[t] = a + b;
        else mp[t] = solve(l - 1, c, a, b) + solve(l - 1, b, c, a) - c;
    }
    return mp[t];
}

void test_case() {
    cin >> n >> k >> p >> q;
    r.clear();
    for (int i = 0; i < n; i++)
        r.push_back('0' + ((p[i] - '0') ^ (q[i] - '0')));
    a = get(p);
    b = get(q);
    c = get(r);
    mp.clear();
    cout << solve(k, a, b, c) << '\n';
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while (t--) test_case();
}

Amazing

Good

Ok

Bad

Terrible

Looking only at the array $$$a$$$, how to deduce the index $$$i$$$ for which $$$p_i = 1$$$, i.e. the minimum of $$$p$$$?

Try to come up with a recursive solution that works in $$$\mathcal{O}(n^2)$$$.

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int Mod = 1e9 + 7, Max = 5e5 + 10;

vector<int> fact(Max), ifact(Max);

int binpow(int b, int p) {
    if (p == 0) return 1;
    if (p % 2 == 0) return binpow((b * b) % Mod, p / 2);
    return (binpow(b, p - 1) * b) % Mod;
}

int C(int n, int k) {
    return (fact[n] * ((ifact[k] * ifact[n - k]) % Mod)) % Mod;
}

int rec(int l, int r, vector<int> &b) {
    if (r < l) {
        return 1;
    }
    if (l == r) {
        return (b[l] == 1 ? 1 : 0);
    }
    for (int d = 0; d < r - l + 1; d++) {
        int i = d + l;
        if ((i - l + 1) * (r - i + 1) == b[i]) {
            return (((rec(l, i - 1, b) * rec(i + 1, r, b)) % Mod) * C(r - l, i - l)) % Mod;
        }
        i = r - d;
        if ((i - l + 1) * (r - i + 1) == b[i]) {
            return (((rec(l, i - 1, b) * rec(i + 1, r, b)) % Mod) * C(r - l, i - l)) % Mod;
        }
    }
    return 0;
}

void solve() {
    int n;
    cin >> n;
    vector<int> b(n);
    for (int i = 0; i < n; i++) cin >> b[i];

    int s = accumulate(b.begin(), b.end(), 0ll);
    if (s != n * (n + 1) / 2) {
        cout << "0\n";
        return;
    }

    cout << rec(0, n - 1, b) << "\n";
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    fact[0] = 1;
    for (int i = 1; i < Max; i++) {
        fact[i] = (fact[i - 1] * i) % Mod;
    }
    for (int i = 0; i < Max; i++) {
        ifact[i] = binpow(fact[i], Mod - 2);
    }

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

Will be added soon.

Amazing

Good

Ok

Bad

Terrible

Read the solution of C. Try to calculate the answer when the empty vessel is vessel $$$1$$$, then somehow change it quickly when moving the empty vessel to be vessel $$$2$$$, $$$3$$$, etc.

Consider the highest vessel connection.

You do not need any advanced data structures. Use a stack.

INF = float("inf")
 
tt = int(input())
for tc in range(tt):
    n = int(input())
    h = list(map(int, input().split()))
    t = 0
    for i in range(n):
        if h[i] > h[t]:
            t = i
    
    ls = [0 for i in range(n)]
    rs = [0 for i in range(n)]
 
    sm = [(INF, 0)]
    for ti in range(1, n):
        i = (ti + t) % n
        s = ls[i] + h[i]
        c = 1
        while sm[-1][0] <= h[i]:
            s += sm[-1][1] * (h[i] - sm[-1][0])
            c += sm[-1][1]
            sm.pop()
        sm.append((h[i], c))
        ls[(i + 1) % n] = s
    
    sm = [(INF, 0)]
    for ti in range(1, n):
        i = (t + n - ti) % n
        s = rs[(i + 1) % n] + h[i]
        c = 1
        while sm[-1][0] <= h[i]:
            s += sm[-1][1] * (h[i] - sm[-1][0])
            c += sm[-1][1]
            sm.pop()
        sm.append((h[i], c))
        rs[i] = s
    
    ans = [ls[i] + rs[i] for i in range(n)]
    print(*ans)

#include <bits/stdc++.h>
 
#define int long long
 
using namespace std;
 
using pii = pair<int, int>;
 
void solve() {
    int n;
    cin >> n;
    vector<int> h(n);
    for (int i = 0; i < n; i++) cin >> h[i];
    int t = max_element(h.begin(), h.end()) - h.begin();
    
    vector<int> ls(n), rs(n);
 
    stack<pii> sm;
    sm.push({1e18, 0});
    for (int ti = 1; ti < n; ti++) {
        int i = (ti + t) % n;
        int s = ls[i] + h[i], c = 1;
        while (sm.top().first <= h[i]) {
            s += sm.top().second * (h[i] - sm.top().first);
            c += sm.top().second;
            sm.pop();
        }
        sm.push({h[i], c});
        ls[(i + 1) % n] = s;
    }
    
    sm = stack<pii>();
    sm.push({1e18, 0});
    for (int ti = 1; ti < n; ti++) {
        int i = (t + n - ti) % n;
        int s = rs[(i + 1) % n] + h[i], c = 1;
        while (sm.top().first <= h[i]) {
            s += sm.top().second * (h[i] - sm.top().first);
            c += sm.top().second;
            sm.pop();
        }
        sm.push({h[i], c});
        rs[i] = s;
    }
    
    for (int i = 0; i < n; i++) {
        cout << ls[i] + rs[i] << " ";
    }
    cout << "\n";
}
 
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
 
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

Amazing

Good

Ok

Bad

Terrible

Think of a $$$\mathcal{O}(n^3)$$$ solution.

DP. For each pair $$$(cell, strength)$$$ you can find whether the player that makes the move from the position wins if the game is played optimally.

There are not many losing positions in this game. Why?

The number of losing positions $$$(i, k)$$$ for a fixed $$$k$$$ with $$$i \le n$$$ is no more than $$$\big\lceil \frac{n}{k + 1} \big\rceil$$$, since if position $$$(i, k)$$$ is a losing position, then all positions $$$(i + 1, k), (i + 2, k), \ldots, (i + k, k)$$$ must be winning if they exist. Then the total number of losing positions $$$(i, k)$$$ with $$$i \le n$$$ is no more than $$$\mathcal{O}(n \log n)$$$.

Try to iterate over cell number $$$i$$$ from $$$n$$$ to $$$1$$$ and explicitly find all losing positions.

You need to think of a data structure to optimize the solution to $$$\mathcal{O}(n \log^2 n)$$$.

We'll denote the state of the game where a chip is on cell $$$i$$$ and has strength $$$k$$$ before using bonuses as $$$(i, k)$$$. We need to determine whether position $$$(1, 1)$$$ is a winning position.

Note that the number of losing positions $$$(i, k)$$$ for a fixed $$$k$$$ with $$$i \le n$$$ is no more than $$$\big\lceil \frac{n}{k + 1} \big\rceil$$$, since if position $$$(i, k)$$$ is a losing position, then all positions $$$(i + 1, k), (i + 2, k), \ldots, (i + k, k)$$$ must be winning if they exist. Then the total number of losing positions $$$(i, k)$$$ with $$$i \le n$$$ is no more than $$$\mathcal{O}(n \log n)$$$.

We will iterate over cell number $$$i$$$ from $$$n$$$ to $$$1$$$ and explicitly find all losing positions.

Let's maintain a set $$$S$$$ containing all $$$k$$$ for which there is no losing position $$$(j, k)$$$, where $$$i \lt j \le i + k$$$. This can be done using a priority queue, adding the event "no more losing positions with strength $$$k$$$ on the interval $$$[i + 1, i + k]$$$" to position $$$i - k - 1$$$ when position $$$(i, k)$$$ is losing. (Also, this event addition is done initially for positions $$$(n + 1, 0), (n + 1, 1), \ldots, (n + 1, n)$$$, since they are all losing positions, and the strength can be limited to being not more than $$$n$$$ without changing the game.) The total number of such events added to the queue will be no more than $$$\mathcal{O}(n \log n)$$$ (based on the number of losing positions), which means there will be no more than $$$\mathcal{O}(n \log n)$$$ queries to the queue, since in each cell we will only read and delete events related to it. Note that only when we read such an event do we add one element to $$$S$$$, and the number of additions to $$$S$$$ is also no more than $$$\mathcal{O}(n \log n)$$$.

We will find losing positions for cell $$$i$$$ as follows: a position $$$(i, k)$$$ is a losing position if and only if, for all $$$0 \le d \le a_i$$$, there are no losing positions among positions $$$(j, k + d)$$$ for $$$j \in [i + 1, i + k + d]$$$, i.e., if and only if $$$S$$$ contains all $$$k, k + 1, \ldots, k + a_i$$$. To quickly find such $$$k$$$, we use the following data structure (we will call it a block container):

There is a set $$$s$$$ of natural numbers, initially empty. All numbers in $$$s$$$ will be on the interval $$$[1, n]$$$, and all operations are guaranteed to be valid (for example, a number already contained in $$$s$$$ will not be asked to be added there). A block container can:

• add a number $$$x$$$ to $$$s$$$ in $$$\mathcal{O}(\log n)$$$;
• find the length of the longest segment of consecutive numbers in $$$s$$$ in $$$\mathcal{O}(1)$$$;
• find any longest segment of consecutive numbers in $$$s$$$ and remove its smallest element from $$$s$$$ in $$$\mathcal{O}(\log n)$$$.

Now, let's show how to quickly find the required $$$k$$$. We'll store $$$S$$$ in a container of blocks. If the length of some block in $$$S$$$ is greater than $$$a_i$$$ and equals $$$l + a_i$$$, the $$$l$$$ smallest elements of this block will be losing strengths for cell $$$i$$$ — this determines all losing strengths for cell $$$i$$$ and only them. Then let's simply remove the smallest element of the longest block while its length is greater than $$$a_i$$$ — obviously, and all the removed numbers will be all the losing strengths for cell $$$i$$$. The number of requests to the block container for finding and removing when considering cell $$$i$$$ is then $$$1$$$ more than the number of losing positions $$$(i, k)$$$, that is, in total over all cells, no more than $$$\mathcal{O}(n \log n)$$$. The number of requests to the block container for adding, as we showed earlier, is also not more than $$$\mathcal{O}(n \log n)$$$.

That is, for each cell, we first process the events coming from the priority queue, load the new elements into the $$$S$$$ block container, then find the losing positions, and finally add new events for the next cells to the priority queue. This means we get every losing position in the process; all that remains is to check whether position $$$(1, 1)$$$ is a losing position.

This results in $$$\mathcal{O}(n \log^2 n)$$$ for requests to the priority queue, $$$\mathcal{O}(n \log^2 n)$$$ for requests to the block container, and a total asymptotic complexity of $$$\mathcal{O}(n \log^2 n)$$$.

Amazing

Good

Ok

Bad

Terrible