Think about the indices that have the same remainder after division by $$$x$$$.

Consider the subsequence formed from the indices that have the same remainder after division by $$$x$$$. There are $$$x$$$ such subsequences. Each subsequence contains distinct characters, so the maximum length of such subsequences is $$$k$$$. As such, the minimum string length that cannot be constructed is $$$n = kx+1$$$.

Time complexity: $$$\mathcal{O}(1)$$$

t = int(input())
for _ in range(t):
    k, x = [int(i) for i in input().split()]
    print(k*x+1)

First observe that it is always helpful to remove a floor. Now the question becomes which floor to remove.

You can simply simulate the process of removing any possible floor. To do this efficiently, compute the current time taken and consider the change to the time taken if a floor is removed. If we remove floor $$$i$$$ where $$$i \neq 1$$$ and $$$i \neq n$$$, then the differences $$$|a[i] - a[i-1]|$$$ and $$$|a[i+1] - a[i]|$$$ are removed and the difference $$$|a[i-1] - a[i+1]|$$$ is added. If $$$i = 1$$$ or $$$i = n$$$, only the adjacent difference is removed.

Time complexity: $$$\mathcal{O}(n)$$$

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
void test_case_run() {
    int n;
    cin >> n;
    
    ll a[n+1];
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    ll sum = 0;
    for (int i = 2; i <= n; i++) sum += abs(a[i]-a[i-1]);
    
    ll ans = min(sum - abs(a[2]-a[1]), sum - abs(a[n]-a[n-1]));
    for (int i = 2; i < n; i++) {
        ans = min(ans, sum - abs(a[i+1]-a[i]) - abs(a[i]-a[i-1]) + abs(a[i+1]-a[i-1]));
    }
    
    cout << ans << "\n";
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    while (t--) test_case_run();
    
    return 0;
}

Making everying zeros works often.

Sometimes, it's better to make all numbers something else that's not zero.

Following Hint 2, if we don't make everything zero, then what's our target number?

Sort the array from small to large.

We can mod every number in the array by itself, and this would require $$$k = a_1$$$.

For a larger value of $$$k$$$, we cannot modify the value of $$$a_1$$$, so every number must be made into $$$a_1$$$. We can mod $$$a_i$$$ with $$$a_i - a_1$$$, using $$$k = a_2 - a_1$$$.

The answer is thus $$$\max(a_1, a_2 - a_1)$$$.

Time complexity: $$$\mathcal{O}(n)$$$ or $$$\mathcal{O}(n \log n)$$$ depending on implementation.

for test_case in range(int(input())):
    n = int(input())
    a = sorted([int(_) for _ in input().split()])
    print(max(a[0], a[1]-a[0]))

Ignore the lexicographically minimum condition first. Can you find any permutation that maximizes $$$S(p)$$$? Can you explain why the permutation maximizes $$$S(p)$$$?

There's an easy permutation that maximizes $$$S(p)$$$.

There are at most $$$2^{n-i}$$$ prefixes of the permutation that has the popcount of the bitwise AND be at least $$$i$$$.

Read all hints. Now, look at this sentence in Hint 3.

"For a popcount of a prefix to exceed $$$i$$$, you'll need to fix $$$i$$$ bits to be all ones."

We will fix the $$$i$$$ lowest-value bits, and iterate the other bits lexicographically minimally.

Here's an example for $$$n=3$$$:

1 1 1 = 7

0 1 1 = 3

0 0 1 = 1

1 0 1 = 5

0 0 0 = 0

0 1 0 = 2

1 0 0 = 4

1 1 0 = 6

For a clean implementation, note that iterating the unfixed bits is basically iterating even numbers.

Time complexity: $$$\mathcal{O}(2^n)$$$.

t = int(input())
for _ in range(t):
    n = int(input())
    print(2**n - 1, end = ' ')
    for i in range(1, n+1):
        for j in range(0, 2**i, 2):
            print(j*2**(n-i) + 2**(n-i) - 1, end = ' ')
    print()

Denote the party that is supposed to win a district as the 'designated winner.' A minimum population $$$p_i$$$ for each district and a strict majority condition creates a lower bound on the number of votes from the designated winner. What is this lower bound?

The lower bound is $$$\lfloor \frac{p_i}{2} \rfloor + 1$$$.

What happens if at least one pair of districts has a different designated winner?

What happens if that is not true; i.e all districts have the same designated winner?

Consider the process of constructing a solution, even though we will not explicitly construct it in the code. First note that if $$$x+y \lt \sum p_i$$$, then it is impossible.

Then if $$$x+y \geq \sum p_i$$$, we start off by filling each district with the lower bound number $$$\lfloor \frac{p_i}{2} \rfloor + 1$$$ of votes from the designated winner. If we run out of votes from either party then the answer is no. After that we have two cases:

Case 1: if there is at least one pair of districts with different designated winners, we can arbitrarily fill (with any color) each district up to its minimum capacity $$$p_i$$$, and then allocate the rest of the votes to a district where that vote's party is supposed to win in. Therefore we only need to check if the lower bound on designated winner votes can be achieved.

Case 2: if all districts have the same designated winner, sometimes there are too many votes from the 'losing' party for a solution to exist. The minimum votes the winning party must have over the losing party is $$$n$$$, because we need a strict majority in every district, which corresponds to a vote difference of at least 1 in each district. WLOG let $$$x$$$ be the votes from the winning party and $$$y$$$ be the votes from the losing party, and we simply check if $$$x \geq y + n$$$.

Time complexity: $$$\mathcal{O}(n)$$$

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
void test_case_run() {
    int n;
    ll x, y;
    cin >> n >> x >> y;
    
    string s;
    cin >> s;
    s = '.'+s;
    
    ll p[n+1];
    for (int i = 1; i <= n; i++) cin >> p[i];
    
    if (accumulate(p+1, p+n+1, 0LL) > x+y) {
        cout << "NO\n";
        return;
    }
    
    if (s == "." + string(n, '0') || s == "." + string(n, '1')) {
        if (s == "." + string(n, '1')) {
            swap(x, y);
        }
        
        ll x_need = 0;
        for (int i = 1; i <= n; i++) {
            x_need += p[i]/2 + 1;
        }
        
        if (x < x_need || x < y+n) {
            cout << "NO\n";
        } else {
            cout << "YES\n";
        }
        
        return;
    }
    
    ll x_need = 0, y_need = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] == '0') {
            x_need += p[i]/2 + 1;
        } else {
            y_need += p[i]/2 + 1;
        }
    }
    if (x >= x_need && y >= y_need) cout << "YES\n";
    else cout << "NO\n";
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    while (t--) test_case_run();
    
    return 0;
}

Solve for a line graph.

Solve for a tree.

Does the exact same thing work? Why?

In the first run, use breadth-first search to find the distance of each vertex from vertex $$$1$$$. Color a vertex red if the distance is dividsible by $$$3$$$, green if the remainder of the division by $$$3$$$ is $$$1$$$, and blue if the remainder of the division by $$$3$$$ is $$$2$$$.

Note that if two vertices are connected by an edge, then their distances differ by no more than $$$1$$$. In fact, the distances differ by exactly $$$1$$$ for a bipartite graph.

In the second run, move anywhere if every neighbor have the same color. Otherwise, note that

• If the neighbors are red and green, then B is at a blue vertex, and should move to any green vertex.

• If the neighbors are green and blue, then B is at a red vertex, and should move to any blue vertex.

• If the neighbors are blue and red, then B is at a green vertex, and should move to any red vertex.

Time complexity: $$$\mathcal{O}(n+m)$$$

#include <bits/stdc++.h>
 
using namespace std;
const int INF = 1e9;
 
void test_first() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> edge(n+1);
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    
    vector<int> dist(n+1, INF);
    dist[1] = 0;
        
    queue<int> bfs;
    bfs.push(1);
    while (!bfs.empty()) {
        int a = bfs.front();
        bfs.pop();
            
        for (int b : edge[a]) {
            if (dist[b] > dist[a] + 1) {
                dist[b] = dist[a] + 1;
                bfs.push(b);
            }
        }
    }
    
    for (int i = 1; i <= n; i++) cout << "rgb"[dist[i]%3];
    cout << "\n";
}
 
void test_second() {
    int dv;
    string color;
    cin >> dv >> color;
    
    bool fr = false, fg = false, fb = false;
    for (char c : color) {
        if (c == 'r') fr = true;
        if (c == 'g') fg = true;
        if (c == 'b') fb = true;
    }
    
    if ((int)fr + (int)fg + (int)fb == 1) {
        cout << 1 << "\n";
        return;
    }
    
    char target;
    if (fr && fg) target = 'g';
    if (fg && fb) target = 'b';
    if (fb && fr) target = 'r';
    
    for (int i = 0; i < dv; i++) {
        if (color[i] == target) {
            cout << i+1 << "\n";
            return;
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    string player;
    int t;
    cin >> player >> t;
    
    if (player == "first") while (t--) test_first();
    else while (t--) {
        int q;
        cin >> q;
        while (q--) test_second();
    }
    
    return 0;
}

Think about corners.

Think about non-opposite corners.

Think about cells furthest from another cell.

The idea is that distance from two non-opposite corners uniquely determine the position.

Start from an arbitrary cell, and query the distance from that cell to every other cell, using $$$n^2$$$ queries. Any cell furthest is a corner.

Next, from that corner, query to every other cell, using $$$n^2$$$ queries. We now get the distances from one corner.

Now, notice that the non-opposite corners would have a distance of $$$n-1$$$ from the corner we have right now. There will be $$$n$$$ candidate corners. Choose one arbitrary candidate and query the distance from this candidate to all other candidates, using $$$n$$$ queries. Any furthest cell is a desired non-opposite corner.

Lastly, query from the new-found corner, using $$$n^2$$$ queries. We now have sufficient information to answer.

Query count: $$$3n^2 + n - \mathcal{O}(1)$$$. This analysis did not account for small constant optimizations like not querying the same pair twice and not querying the distance to self.

Time complexity: $$$\mathcal{O}(n^2)$$$

#include <bits/stdc++.h>
 
using namespace std;
 
int query(int i, int j) {
    cout << "? " << i << " " << j << endl;
    int ret;
    cin >> ret;
    return ret;
}
 
void test_case_run() {
    int n;
    cin >> n;
    
    // Find the first corner
    int dist1[n*n+1];
    for (int i = 1; i <= n*n; i++) dist1[i] = query(1, i);
    
    int corner1 = 1;
    for (int i = 1; i <= n*n; i++) if (dist1[i] > dist1[corner1]) corner1 = i;
    
    // Query distance from first corner
    int dist_corner1[n*n+1];
    for (int i = 1; i <= n*n; i++) {
        dist_corner1[i] = query(corner1, i);
    }
 
    // Find second corner    
    vector<int> corner2_candidates;
    for (int i = 1; i <= n*n; i++) {
        if (dist_corner1[i] == n-1) corner2_candidates.push_back(i);
    }
    
    int dist_findcorner2[corner2_candidates.size()];
    for (int i = 0; i < corner2_candidates.size(); i++) {
        dist_findcorner2[i] = query(corner2_candidates[0], corner2_candidates[i]); 
    }
    
    int corner2_index = 0;
    for (int i = 0; i < corner2_candidates.size(); i++) {
        if (dist_findcorner2[i] > dist_findcorner2[corner2_index]) corner2_index = i;
    }
    
    int corner2 = corner2_candidates[corner2_index];
    
    // Query distance from second corner
    int dist_corner2[n*n+1];
    for (int i = 1; i <= n*n; i++) {
        dist_corner2[i] = query(corner2, i);
    }
    
    // Find position
    /*
    d1 = |x-1|+|y-1| = x+y-2
    d2 = |x-1|+|y-n| = x-y+n-1
    
    d1 + d2 = 2x+n-3 => x = (d1+d2-n+3)/2
    d1 - d2 = 2y-n-1 => y = (d1-d2+n+1)/2
    */
    int ans[n+1][n+1];
    for (int i = 1; i <= n*n; i++) {
        int d1 = dist_corner1[i], d2 = dist_corner2[i];
        int x = (d1+d2-n+3)/2;
        int y = (d1-d2+n+1)/2;
        ans[x][y] = i;
    }
    
    cout << "!" << endl;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) cout << ans[i][j] << " ";
        cout << endl;
    }
};
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    while (t--) test_case_run();
    
    return 0;
}

This problem is solvable in $$$3n^2$$$ queries. Try it.

Solve the easier version of this problem first:

• Let $$$f(x)$$$ be the value of the least significant bit of $$$x$$$.

Read Hint 1 first.

You can extend the idea from the easier version to solve the actual task.

Since the value of the least significant bit can be represented using the sum of $$$2^0, 2^1, 2^2, \ldots$$$, the only thing left to consider is the coefficient of those values in each position.

For watering operations that cover the range $$$[l, r]$$$, you can perform the following update to the coefficient array:

• For all $$$l \leq i \leq r$$$, add $$$i$$$ to the $$$i$$$-th position.
• For all $$$l \leq i \leq r$$$, subtract $$$l-1$$$ from the $$$i$$$-th position.

Which is basically the same as increasing the coefficients value in each $$$l \leq i \leq r$$$ by $$$i - l + 1$$$.

These operations can be implemented using prefix sum arrays separately in each $$$a$$$, too.

Time complexity: $$$\mathcal{O}((n+q)\log n)$$$.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200200;
int qs1[20][N];
ll qs2[20][N];
ll ans[N];
void solve() {
    int n, q;
    cin >> n >> q;
    int sz = 31 - __builtin_clz(n);
    for (int i = 1;i <= n;i++) ans[i] = 0;
    for (int j = 0;j <= sz;j++) {
        for (int i = 0;i <= n;i++) qs1[j][i] = 0, qs2[j][i] = 0;
    }
    while (q--) {
        int l, r;
        cin >> l >> r;
        int sz = 31 - __builtin_clz(r - l + 1);
        for (int j = 0;j <= sz;j++) {
            int k = (r - l + 1) >> j;
            qs1[j][l + (1 << j) - 1]++;
            qs2[j][l + (1 << j) - 1] += l - 1;
            qs1[j][min(n + 1, l + ((k + 1) << j) - 1)]--;
            qs2[j][min(n + 1, l + ((k + 1) << j) - 1)] -= l - 1;
        }
    }
    for (int i = 0;i <= sz;i++) {
        for (int j = 1;j <= n;j++) {
            if (j >= (1 << i)) {
                qs1[i][j] += qs1[i][j - (1 << i)];
                qs2[i][j] += qs2[i][j - (1 << i)];
            }
            ans[j] += 1ll * qs1[i][j] * j * (1 << max(0, i - 1));
            ans[j] -= 1ll * qs2[i][j] * (1 << max(0, i - 1));
        }
    }
    for (int i = 1;i <= n;i++) {
        cout << ans[i] << ' ';
    }
    cout << '\n';
}
 
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int q;
    cin >> q;
    while (q--) {
        solve();
    }
    return 0;
}

#include "vision.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> bit_circuit(vector<int> row) {
    int n = row.size();
    vector<int> ret;
    for (int bit = 0; (1<<bit) < n; bit++) {
        vector<int> all_pair;
        for (int i = 0; i+(1<<bit) < n; i++) {
            vector<int> all_can;
            for (int j = i+1; j < n; j++) {
                if ((j-i)&(1<<bit)) all_can.push_back(row[j]);
            }
            all_pair.push_back(add_and({row[i], add_or(all_can)}));
        }
        ret.push_back(add_or(all_pair));
    }

    return ret;
}

void construct_network(int H, int W, int K) {
    vector<int> row(H), col(W);

    for (int i = 0; i < H; i++) {
        vector<int> inp(W);
        for (int j = 0; j < W; j++) inp[j] = i*W + j;
        row[i] = add_or(inp);
    }

    for (int j = 0; j < W; j++) {
        vector<int> inp(H);
        for (int i = 0; i < H; i++) inp[i] = i*W + j;
        col[j] = add_or(inp);
    }

    vector<int> row_bit = bit_circuit(row);
    vector<int> col_bit = bit_circuit(col);

    if (row_bit.size() < col_bit.size()) swap(row_bit, col_bit);

    vector<int> carry = {-1};
    vector<int> value;

    for (int i = 0; i < max(row_bit.size(), col_bit.size()); i++) {
        if (i < col_bit.size()) {
            int value_node, carry_node;
            if (carry.back() != -1) {
                value_node = add_xor({row_bit[i], col_bit[i], carry[i]});
                carry_node = add_or({add_and({row_bit[i], col_bit[i]}), add_and({row_bit[i], carry[i]}), add_and({col_bit[i], carry[i]})});
            }
            else {
                value_node = add_xor({row_bit[i], col_bit[i]});
                carry_node = add_and({row_bit[i], col_bit[i]});
            }

            value.push_back(value_node);
            carry.push_back(carry_node);
        } else {
            int value_node, carry_node;
            if (carry.back() != -1) {
                value_node = add_xor({row_bit[i], carry[i]});
                carry_node = add_and({row_bit[i], carry[i]});
            } else {
                value_node = row_bit[i];
                carry_node = -1;
            }

            value.push_back(value_node);
            carry.push_back(carry_node);
        }
    }
    if (carry.back() != -1)value.push_back(carry.back());

    vector<int> bit_match;
    for (int i = 0; i < value.size(); i++) {
        if ((K>>i)&1) bit_match.push_back(value[i]);
        else bit_match.push_back(add_not(value[i]));
    }

    int final_answer = add_and(bit_match);
}

Something doesn't change after each operation.

The average of the entire array doesn't change after each operation. Simply check whether the average value of $$$a$$$ is $$$x$$$ or not.

Time complexity: $$$\mathcal{O}(n)$$$ per test case.

Submission: 310297520

Try to put as many people in cell $$$n$$$ as possible.

The minimum sum of distances will always be $$$1$$$.

The following configuration gives $$$1$$$ as the sum of distances.

For odd $$$k$$$: $$$n, n, \ldots, n, n, n-1$$$

For even $$$k$$$: $$$n-1, n-1, \ldots, n-1, n, n-1$$$

And the sum of distances cannot be $$$0$$$.

Time complexity: $$$\mathcal{O}(n)$$$ per test case.

Submission: 310297574

Prove that the optimal configuration is unique.

Rearrange the equation around.

Try to maximize the missing number.

The equation can be rearranged to

Choose $$$a_1$$$ as the largest number, $$$a_3, a_5, \ldots, a_{2n+1}$$$ as the next $$$n$$$ largest numbers, and the rest as $$$a_2, a_4, \ldots, a_{2n-2}$$$. The value of the missing number $$$a_{2n}$$$ will be larger than $$$a_1$$$, and so larger than every number in $$$b$$$.

Time complexity: $$$\mathcal{O}(n \log n)$$$ per test case. Logarithmic factor is from sorting.

Submission: 310297635

There are some randomization solutions where we just shuffle $$$b$$$ randomly, fill the missing number, and attempt it as a possible solution. I do not have a proof or disproof of whether this would work well enough.

It is optimal to place everyone on the same lane.

Think about the multiplier.

It is best to think of each $$$\tt{+}$$$ as "how much can we multiply this by".

This is the greedy solution.

When we get more people, place all to where the $$$\tt{x}$$$ will occur first. If both lanes have the next multiply at the same gate pair, then choose the one with higher multiply. If the multiply is the same, look to the next multiply.

Time complexity: $$$\mathcal{O}(n)$$$ per test case. $$$\mathcal{O}(n^2)$$$ implementations are also acceptable.

Submission: 310297718

This is the dynamic programming solution.

Let $$$dp_l[i]$$$ and $$$dp_r[i]$$$ be the maximum possible multiplication possible that can be applied if a person enters the $$$i$$$-th left and right gate, respectively. Then we have the following equation (only for left is written, it's the same for the right).

If the gate is $$$\tt{+}$$$

If the gate is $$$\tt{x}$$$ by $$$a$$$

For each $$$\tt{+}$$$, we choose to place people at the side with more multiplication.

Time complexity: $$$\mathcal{O}(n)$$$ per test case.

Submission: 310297763

$$$n = 30$$$ constraint is due to overflow. The maximum answer is the case with $$$n = 30$$$, the first pair of gates is $$$\tt{+} 1000$$$ $$$\tt{+} 1000$$$, and the other pairs of gates are $$$\tt{+} 1000$$$ $$$\tt{x} 3$$$, giving the answer $$$171644573789571884 \lt 10^{18}$$$.

It is possible to solve this task under modulo and force $$$\mathcal{O}(n)$$$ solution, but it will be hard, or maybe impossible, to implement the DP solution which requires min/max operations, so I decided against it.

Try to get information on half of the bits.

Alternate the bits.

The queries are $$$\ldots 0101_2$$$ and $$$\ldots 1010_2$$$.

It's easier to look at the case with only two binary digits first.

Let the result of query $$$01_2$$$ be $$$q_1$$$ and $$$10_2$$$ be $$$q_2$$$.

Observe that if

• $$$q_2 = 100_2$$$ then the first (from the right) digit of both $$$x$$$ and $$$y$$$ is $$$0$$$.

• $$$q_2 = 101_2$$$ then the first (from the right) digit of one of $$$x$$$ or $$$y$$$ is $$$0$$$, and the other one is $$$1$$$.

• $$$q_2 = 110_2$$$ then the first (from the right) digit of both $$$x$$$ and $$$y$$$ is $$$1$$$.

Similarly, if

• $$$q_1 = 10_2$$$ then the second (from the right) digit of both $$$x$$$ and $$$y$$$ is $$$0$$$.

• $$$q_1 = 100_2$$$ then the second (from the right) digit of one of $$$x$$$ or $$$y$$$ is $$$0$$$, and the other one is $$$1$$$.

• $$$q_1 = 110_2$$$ then the second (from the right) digit of both $$$x$$$ and $$$y$$$ is $$$1$$$.

To generalize to every other digit, apply the same logic to every consecutive pair of digits in $$$x$$$ and $$$y$$$. Note that you must account for the carries from the digits before too.

After this, you will know for every digit position whether both $$$x$$$ and $$$y$$$ are $$$0$$$, are $$$1$$$, or have one $$$0$$$ and one $$$1$$$. You can use this information to find $$$(m|x) + (m|y)$$$ for any $$$m$$$.

Time complexity: $$$\mathcal{O}(\log \max (x))$$$ per test case.

Submission: 310297820

Find a closed-form expression for the score of a binary string.

The closed-form expression for the score of a binary string is

Where $$$cnt_0$$$ and $$$cnt_1$$$ are the number of $$$\tt{0}$$$ and $$$\tt{1}$$$ in the binary string, respectively.

The expression for counting subsequences might be simpler than you think.

Think of $$$\tt{0}$$$ as $$$-1$$$ and $$$\tt{1}$$$ as $$$1$$$. Let us count the number of subsequences of a binary string which will have the sum of $$$i$$$. Let $$$cnt_0$$$ and $$$cnt_1$$$ as the number of $$$\tt{0}$$$ and $$$\tt{1}$$$ in the binary string. The number of subsequences is

So the desired sum of the score over all subsequences (see expression of score of a single string in Hint 2) is

At this point, you can throw convolution at the problem by precomputing the answer for $$$cnt_0 = 0, 1, \ldots, n$$$ and solve it in $$$\mathcal{O}(n \log n + q)$$$.

Submission: 310298025

Alternatively, you can do more algebra to arrive at a closed-form expression.

Time complexity: $$$\mathcal{O}(n+q)$$$ per test case.

Submission: 310297950

Find a way to get the answer if you fixed the largest value or the first value of the subsequence.

Sufficiently long (which is not that long) arrays will definitely be polygon side lengths.

Suppose we consider some integer $$$x$$$, and we try to find the lexicographically largest subsequence (say $$$s$$$) such that the maximum element of $$$s$$$ is $$$x$$$.

We can do it greedily.

For the subsequence $$$s$$$ to be valid, we need to ensure that the sum of the elements of $$$s$$$ is greater than $$$2x$$$.

So, our greedy strategy is like we have an empty vector $$$s$$$, and we iterate over the array $$$a$$$ from left to right, and for each element $$$a_i$$$, we do the following:

If $$$s$$$ is not empty and $$$a_i$$$ is greater than the last element of $$$s$$$, we will check whether we can make the total sum of $$$s$$$ greater than $$$2x$$$, if we remove the last element of $$$s$$$. Now what can be the maximum possible sum of $$$s$$$? We can just append all the elements of $$$a$$$ which are less than or equal to $$$x$$$, and are present to the right of $$$a_i$$$ to $$$s$$$.

Append $$$a_i$$$ to $$$s$$$.

Thus, we see that the subsequence $$$s$$$ is the lexicographically largest subsequence such that the maximum element of $$$s$$$ is $$$x$$$.

Now, we have $$$O(n)$$$ candidates for the maximum element of $$$s$$$. We cannot find the best subsequence for each candidate, as it will be too slow.

Here comes the key observation.

Now, what can be the maximum possible size of a sorted vector $$$v$$$ such that there does not exist any subsequence of $$$v$$$ which can form the sides of a valid polygon?

We should have $$$v_i \gt \sum_{j=1}^{i-1} v_j$$$.

Now, to get the maximum possible size of $$$v$$$, we should have $$$v_1 = 1$$$ and $$$v_i = 2^{i - 2}$$$ for $$$i \geq 2$$$.

Thus, the maximum possible size of $$$v$$$ can be $$$p = \log_2(10^9) + 2$$$.

Our claim is that in the lexicographically largest subsequence $$$s$$$, the maximum element should be one of the largest $$$p + 1$$$ elements of $$$a$$$.

Suppose we do not have the maximum element of $$$s$$$ in the largest $$$p + 1$$$ elements of $$$a$$$. Let's consider the multiset of the largest $$$p + 1$$$ elements of $$$a$$$. As we saw above, there should be a subsequence (say $$$t$$$) of this multiset which forms the sides of a valid polygon. Now if we insert the elements of $$$t$$$ in $$$s$$$, we will get a subsequence $$$s'$$$ such that $$$s'$$$ is valid and $$$s'$$$ is lexicographically larger than $$$s$$$.

Thus, we cannot have a subsequence $$$s$$$ such that $$$s$$$ is the largest possible subsequence and the maximum element of $$$s$$$ is not in the largest $$$p + 1$$$ elements of $$$a$$$.

Time complexity: $$$\mathcal{O}(n \log \max(a))$$$ per test case.

Submission: 310298095

Folding is basically alternating the parity of the indices.

Maximum subarray sum.

As mentioned in Hint 1, we can see that if the darkness of the cells $$$i_1, i_2, \ldots, i_k$$$ increases in some operation, the parity of $$$i_j$$$ should be different from that of $$$i_{j+1}$$$ for $$$1 \le j \le k - 1$$$

Let us try to find $$$f(a[1, n])$$$.

Consider an array $$$b$$$ such that $$$b_i = (-1)^i a_i$$$ for all $$$1 \le i \le n$$$.

Let us perform exactly one operation, and say our subsequence of indices is $$$i_1, i_2, \ldots, i_k$$$.

Let $$$a'$$$ be the updated array after performing the operation, and $$$b'_i = (-1)^{i'} a'_i$$$ for all $$$1 \le i \le n$$$.

Now we can see that

for all $$$1 \le l \le r \le n$$$.

This is so because for any subarray $$$b[l, r]$$$, if $$$x$$$ elements at odd indices and $$$y$$$ elements at even indices were selected, we should have $$$|x - y| \le 1$$$.

So, we can see that after any operation, the absolute sum of any subarray of $$$b$$$ decreases by at most $$$1$$$.

Thus, this gives us a lower bound for the value of $$$f(a[1, n])$$$, which is

Now let us consider the following greedy algorithm for selecting a subsequence $$$s$$$ of indices:

• Start from $$$i = 1$$$ and move to the right.
• If $$$b_i$$$ is zero, we continue.
• If $$$s$$$ is empty, we append $$$i$$$ to $$$s$$$, and continue.
• If $$$i$$$ does not have the same parity as the last element of $$$s$$$, we append $$$i$$$ to $$$s$$$, and continue.
• Otherwise, we continue.

Now suppose $$$T$$$ is the set of pairs of indices $$$(l, r)$$$ such that $$$b_l$$$ and $$$b_r$$$ are nonzero and

is maximized.

We can prove that the absolute sum of all subarrays in $$$T$$$ would be reduced by $$$1$$$ after performing the operation.

We can notice that if $$$(l, r) \in T$$$, then $$$l$$$ and $$$r$$$ should have the same parity. Otherwise,

Next, we claim that $$$l$$$ should be in $$$s$$$.

Suppose $$$l$$$ is not in $$$s$$$. This means that there should be an index $$$k$$$ in $$$s$$$ such that $$$k$$$ has the same parity as $$$l$$$ and there are no nonzero elements between $$$k$$$ and $$$l$$$ that have a parity different from $$$l$$$.

Now if that is the case, then $$$b[k, r]$$$ would have a greater absolute sum than $$$b[l, r]$$$.

Thus, we conclude that $$$l$$$ will always be in $$$s$$$.

Now let $$$d$$$ be the largest index in $$$s$$$ smaller than or equal to $$$r$$$.

First of all, we should have $$$d \ge l$$$.

Now $$$d$$$ should have the same parity as $$$r$$$.

This is so because if that is not the case, we should have $$$d \lt r$$$ and we would have selected $$$r$$$ or any other element having the same parity as $$$r$$$ after $$$d$$$ in $$$s$$$.

Thus, we can see that for all the pairs $$$(l, r) \in T$$$, we should have $$$l$$$ in $$$s$$$ and the largest element smaller than or equal to $$$r$$$ in $$$s$$$ should have the same parity as that of $$$r$$$. This implies that the absolute sum of all subarrays in $$$T$$$ would be reduced by $$$1$$$ after performing the operation.

This is because if $$$l$$$ is odd, we would have added $$$1, -1, 1, -1, \ldots, 1$$$ to the subarray $$$b[l, r]$$$, increasing the subarray sum of $$$b[l, r]$$$ by $$$1$$$.

And if $$$l$$$ is even, we would have added $$$-1, 1, -1, 1, \ldots, -1$$$ to the subarray $$$b[l, r]$$$, decreasing the subarray sum of $$$b[l, r]$$$ by $$$1$$$.

Now we can see that the greedy algorithm would achieve the lower bound.

So, the answer for the array $$$a$$$ is the maximum absolute sum over all subarrays of $$$b$$$.

Let us consider an array $$$c$$$ such that

We can further notice that the maximum absolute sum over all subarrays of $$$b$$$ is equal to

Now we can see that

Thus,

So,

Finding the value of

is a fairly standard exercise, which can be done using a stack in $$$O(n)$$$ time.

Submission: 310317161

Characterize the property of a good pair of arrays.

Think about the last operation that turns a good pair of arrays into the same array.

$$$(a, b)$$$ is a good pair only if at least one of these two conditions hold

• $$$a = b$$$

• There exist two distinct indices $$$i$$$, $$$j$$$ such that $$$b_i$$$ is a submask of $$$b_j$$$.

We need to check the two cases.

In the first case, the minimum cost will be $$$\sum_{i=1}^n |a_i - b_i|$$$.

In the second case, we want the minimum cost to create a submask-supermask pair in $$$b$$$.

Solution 1

For explanation simplicity, consider the graph $$$G$$$ with $$$2m$$$ vertices, representing the numbers from $$$1$$$ to $$$2m$$$. In this graph, there's an unweighted edge from vertex $$$i$$$ to vertex $$$i+1$$$, and from vertex $$$i$$$ to all submask vertices. Color all vertices in which its value appears in $$$b$$$. The answer is the shortest path between all pairs of distinct colored vertices.

The implementation itself (see below) uses dynamic programming consisting of three phases. The dynamic programming tracks the first and second closest vertex to each vertex, because the first closest vertex would be itself.

• Propagate each colored vertices up (from $$$i$$$ to $$$i+1$$$).

• Propagate to the submasks (from $$$i$$$ to its submasks).

• Propagate down (from $$$i$$$ to $$$i-1$$$).

Time complexity: $$$\mathcal{O}(n \log n + m \log m)$$$ per test case. The $$$\log n$$$ factor is from the implementation which checks for duplicates in $$$b$$$ by sorting.

Submission: 310298215

Solution 2

Submission: 310317931

It might help to solve this task with two colors first. As in, minimize the difference between red and blue.

In the two-color version (in Hint 1), we created a state graph on the parity. Can a similar idea be used?

Think about each color separately first.

Let

• the edge weights of the red edges be $$$r_1, r_2, \ldots$$$, the green edges be $$$g_1, g_2, \ldots$$$ and the blue edges be $$$b_1, b_2, \ldots$$$.

• $$$\gcd(r_1, r_2, \ldots)$$$, $$$\gcd(g_1, g_2, \ldots)$$$ and $$$\gcd(b_1, b_2, \ldots)$$$ be $$$c_r, c_g, c_b$$$.

• the sum of weights of red, green and blue edges traversed be $$$d_r, d_g, d_b$$$.

Define $$$ \lt d_{r_1}, d_{g_1}, d_{b_1} \gt = \lt d_{r_2}, d_{g_2}, d_{b_2} \gt $$$ only if $$$d_{r_1}-d_{g_1} = d_{r_2}-d_{g_2}$$$, $$$d_{r_1}-d_{b_1} = d_{r_2}-d_{b_2}$$$ and $$$d_{g_1}-d_{b_1} = d_{g_2}-d_{b_2}$$$.

In a similar manner to hint 1, there's a walk that passes through every edge and have $$$ \lt d_r, d_g, d_b \gt = \lt 0, 0, 0 \gt $$$. Furthermore, if we have $$$ \lt d_r, d_g, d_b \gt $$$, then we can have $$$ \lt d_r + 2g_r, d_g, d_b \gt $$$ and $$$ \lt d_r - 2g_r, d_g, d_b \gt $$$. The analogous statement holds for the other two colors.

Consequently, from any reachable $$$ \lt d_r, d_g, d_b \gt $$$, we can have $$$ \lt s_r, s_g, s_b \gt $$$, where $$$s_r$$$ is either $$$0$$$ or $$$c_r$$$ depending on whether $$$d_r \equiv 0$$$ ($$$\mod 2c_r$$$) or $$$d_r \equiv c_r$$$ ($$$\mod 2c_r$$$). The idea holds similarly for the other two colors. This invites us to look at each vertex as $$$8$$$ possible states, corresponding to $$$3$$$ binary options of each color.

We simply need to solve the answer for each reachable state then take the minimum. Each state corresponds to the following system of linear congruences.

We aim to minimize $$$\max(d_r, d_g, d_b) - \min(d_r, d_g, d_b)$$$ over all triplets which satisfy the conditions.

To do so, we will fix one of them, which we'll suppose is $$$d_r$$$, as the minimum.

Denote $$$f_g(p)$$$ and $$$f_b(p)$$$ as the minimum possible $$$d_g - (d_r + 2pc_r)$$$ and $$$r_b - (d_r + 2pc_r)$$$ where $$$r_g, r_p \geq d_r + 2pc_r$$$.

We want to find

Observe that $$$f_g(k + c_g) = f_g(p)$$$ and $$$fb(k + c_b) = f_b(p)$$$. By the Chinese remainder theorem, the expression above reduces to

Which can be evaluated in $$$\mathcal{O}(x)$$$.

Time complexity: $$$\mathcal{O}(n \log x + x)$$$ per test case. The logarithmic factor is from gcd computations.

Submission: 310298269

This contest was originally proposed as a Div. 2 only. It was changed to Div. 1 + Div. 2 because we found task 1G, which was originally proposed with only two colors as 2D.

The contest itself retained little of the original proposal, and most of the tasks were once proposed for a lower position.

• 2B was proposed as 2A.

• 1A/2C was proposed as 2A.

• 2D was proposed as 2B. The base story is credited to my friend Punpun.

• 1B/2E was proposed as 2C.

• 1C/2F was proposed as 2E with $$$n \leq 5000$$$. The testers found the solutions for the current version.

• 1D was originally made for permutation arrays only. Credit to satyam343 for making the task.

• 1E/2G was proposed as 2D with binary arrays. The testers found the solutions for the current version. The idea of folding and dropping color is credited to my friend Punpun.

• 1F was proposed in a much easier form as 2B. It was buffed by satyam343.

• 1G was proposed as 2D with two colors. Solving this easier version can hint the full solution.

Arcaea is a good rhythm game with good mechanics, music, and story. In some tasks, I put music from Arcaea in it because I want to.