...

...

What is the optimal strategy for Bob?

It is optimal for Bob to negate the $$$x$$$ largest elements of the array. So what should Alice do?

It is optimal for Bob to negate the $$$x$$$ largest elements of the array. So in order to minimize the damage Bob will do, Alice should always remove some number of largest elements.

To solve the problem, we can sort the array and iterate over $$$i$$$ ($$$0 \leq i \leq k$$$) where $$$i$$$ is the number of elements Alice removes. For each $$$i$$$, we know that Alice will remove the $$$i$$$ largest elements of the array and Bob will then negate the $$$x$$$ largest remaining elements. So the sum at the end can be calculated quickly with prefix sums. The time complexity is $$$O(n \log n)$$$ because of sorting.

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

void solve(){
    int n, k, x;
    cin >> n >> k >> x;
    
    int A[n + 1] = {};
    for (int i = 1; i <= n; i++)
        cin >> A[i];
    
    sort(A + 1, A + n + 1, greater<int>());

    for (int i = 1; i <= n; i++)
        A[i] += A[i - 1];
    
    int ans = -1e9;
    for (int i = 0; i <= k; i++)
        ans = max(ans, A[n] - 2 * A[min(i + x, n)] + A[i]);
    
    cout<<ans<<"\n";
}

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

Try to solve the problem for just two integers $$$x$$$ and $$$y$$$. Under what $$$m$$$ are they equal (modulo $$$m$$$).

How can we use the previous hint and gcd to solve the problem?

For some $$$x$$$ and $$$y$$$, let's try to find all $$$m$$$ such that $$$x \bmod m \equiv y \bmod m$$$. We can rearrange the equation into $$$(x-y) \equiv 0 \pmod m$$$. Thus, if $$$m$$$ is a factor of $$$|x-y|$$$, then $$$x$$$ and $$$y$$$ will be equal modulo $$$m$$$.

Let's solve for some $$$k$$$. A valid partition exists if there exists some $$$m>1$$$ such that the following is true:

• $$$a_1 \equiv a_{1+k} \pmod m$$$
• $$$a_2 \equiv a_{2+k} \pmod m$$$
• ...
• $$$a_{n-k} \equiv a_{n} \pmod m$$$

The first condition $$$a_1 \equiv a_{1+k} \pmod m$$$ is satisfied if $$$m$$$ is a factor of $$$|a_1-a_{1+k}|$$$. The second condition $$$a_2 \equiv a_{2+k} \pmod m$$$ is satisfied if $$$m$$$ is a factor of $$$|a_2-a_{2+k}|$$$. And so on...

Thus, all conditions are satisfied if $$$m$$$ is a factor of:

In other words, all conditions are satisfied if $$$m$$$ is a factor of:

So a valid $$$m$$$ exists for some $$$k$$$ if the aforementioned $$$\gcd$$$ is greater than $$$1$$$.

The time complexity of this will be $$$O(n \cdot \text{max divisors of n})$$$. Note that there should not be a log factor from calculating the gcd given how the gcd will either be halved or stay the same at each point.

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

void solve(){
    int n; 
    cin >> n;

    int A[n];
    for (int &i : A)
        cin >> i;
    
    int ans = 0;
    for (int k = 1; k <= n; k++){
        if (n % k == 0){
            int g = 0;
            for (int i = 0; i + k < n; i++)
                g = __gcd(g, abs(A[i + k] - A[i]));
            ans += (g != 1);
        }
    }
    cout<<ans<<"\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    int tc; 
    cin >> tc;

    while (tc--) 
        solve();
}

For some query try to trace your way back to where the $$$k$$$-th number was added.

Here's an example of tracing back:

Suppose the $$$k$$$-th element is the bolded $$$l_2$$$. Finding the $$$k$$$-th element is equivalent to finding the ($$$k \bmod x$$$)-th element.

First, let's precalculate some things:

We can calculate $$$dp$$$ as follows (calculating $$$lst$$$ can be done with similar reasoning):

Now, let's try answering some query $$$k$$$. If we have some $$$dp_i=k$$$ then the answer is $$$lst_i$$$.

Otherwise, let's find the first $$$i$$$ such that $$$dp_i > k$$$. This $$$i$$$ will be a repeat operation and our answer will lie within one of the repetitions. Our list at this point will look like:

Let the $$$k$$$-th element be the bolded $$$l_2$$$ of the final repetition. As you can see, finding the $$$k$$$-the element is equivalent to finding the $$$(k \bmod dp_{i-1})$$$-th element. Thus, we should do $$$k:=k \bmod dp_{i-1}$$$ and repeat! But there is one more case! If $$$k \equiv 0 \pmod {dp_{i-1}}$$$ then the answer is $$$lst_{i-1}$$$.

At this point there are 2 ways we can go about solving this:

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

#define ll long long

void solve(){
    int n, q;
    cin >> n >> q;

    ll dp[n + 1] = {};
    int lstAdd[n + 1] = {};
    vector<int> pos;

    for (int i = 1, doAdd = true; i <= n; i++){
        int a, v; 
        cin >> a >> v;

        if (a == 1){
            lstAdd[i] = v;
            dp[i] = dp[i - 1] + 1;
        }
        else{
            lstAdd[i] = lstAdd[i - 1];
            dp[i] = ((v + 1) > 2e18 / dp[i - 1]) ? (ll)2e18 : dp[i - 1] * (v + 1);

            if (doAdd)
                pos.push_back(i);
        }
        // No need to consider any more repetitions after this point
        if (dp[i] == 2e18)
            doAdd = false;
    }
    while (q--){
        ll k; 
        cin >> k;

        for (int i = pos.size() - 1; ~i; i--){
            int idx = pos[i];

            if (dp[idx] > k and dp[idx - 1] < k){
                if (k % dp[idx - 1] == 0){
                    k = dp[idx - 1];
                    break;
                }
                k %= dp[idx - 1];
            }
        }
        cout<<lstAdd[lower_bound(dp + 1, dp + n + 1, k) - dp]<<" \n"[q == 0];
    }
}

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

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

#define ll long long

void solve(){
    int n, q;
    cin >> n >> q;

    ll dp[n + 1] = {};
    int lstAdd[n + 1] = {};

    for (int i = 1; i <= n; i++){
        int a, v; 
        cin >> a >> v;

        if (a == 1){
            lstAdd[i] = v;
            dp[i] = dp[i - 1] + 1;
        }
        else{
            lstAdd[i] = lstAdd[i - 1];
            dp[i] = ((v + 1) > 2e18 / dp[i - 1]) ? (ll)2e18 : dp[i - 1] * (v + 1);
        }
    }
    while (q--){
        ll k; 
        cin >> k;

        while (true){
            int pos = lower_bound(dp + 1, dp + n + 1, k) - dp;
            
            if (dp[pos] == k){
                cout<<lstAdd[pos]<<" \n"[q == 0];
                break;
            }
            if (k % dp[pos - 1] == 0){
                cout<<lstAdd[pos - 1]<<" \n"[q == 0];
                break;
            }
            k %= dp[pos - 1];
        }
    }
}

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

How do you count the number of good substrings in a string?

We can count the number of good substrings in a string with the counting contribution technique. How can you formulate this into a dp?

$$$\frac{n}{1} + \frac{n}{2} + \cdots + \frac{n}{n} = O(n\log n)$$$

Let's first solve the problem where we are given some string $$$s$$$ and must count the number of good substrings. To do this we use the technique of counting contributions. For every $$$1$$$ in $$$s$$$, we find the number of good substrings containing that $$$1$$$. Consider the following example:

The number of good substrings in this example is $$$a_1 a_2 + a_2 a_3 + a_3 a_4 + a_4 a_5$$$. We can create such array for any string $$$s$$$ and the number of good substrings of $$$s$$$ is the sum of the products of adjacent elements of the array.

This motivates us to reformulate the problem. Instead, we count the number of arrays $$$a_1,a_2,...,a_m$$$ such that every element is positive and the sum of the products of adjacent elements is exactly equal to $$$n$$$. Furthermore, every pair of adjacent elements should have sum minus $$$1$$$ be less than or equal to $$$k$$$. We can solve this with dynamic programming.

The key observation is that we only have to iterate $$$p$$$ up to $$$\lfloor \frac{i}{j} \rfloor$$$ (since if $$$p$$$ is any greater, $$$j \cdot p$$$ will exceed $$$i$$$). At $$$j=1$$$, we will iterate over at most $$$\lfloor \frac{i}{1} \rfloor$$$ values of $$$p$$$. At $$$j=2$$$, we will iterate over at most $$$\lfloor \frac{i}{2} \rfloor$$$ values of $$$p$$$. In total, at each $$$i$$$, we will iterate over at most $$$\lfloor \frac{i}{1} \rfloor + \lfloor \frac{i}{2} \rfloor +\cdots + \lfloor \frac{i}{i} \rfloor \approx i \log i$$$ values of $$$p$$$. Thus, the time complexity of our solution is $$$O(n^2\log n)$$$.