...

...

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();
}