It even had a problem with 'Amrita University' in it. :-|

If you say so..

Will be fixed after contest.

Fixed at the frontend now.

There's no case for no.

Consider connected components of the graph formed by the initial associations.

Lets consider the $$$\lfloor \frac{n}{2}\rfloor$$$ cheapest nodes of a given connected component to be coloured black, and the others coloured white.

Clearly there always exists an edge between some black and white nodes, otherwise the component wouldn't be connected.

Also after performing an operation on the nodes connected by this edge, the nodes are removed, but the component remains connected, so the previous logic still holds.

In the case of odd sized components, we can just remove the median value (the smallest white coloured node) on its own, which will leave the graph connected allowing us to use the previously discussed logic.

So we can always use the $$$\lfloor \frac{n}{2}\rfloor$$$ cheapest nodes of a given connected component to eliminate the $$$\lfloor \frac{n}{2}\rfloor$$$ costliest nodes.

#include <bits/stdc++.h>
#define int long long
using pii=std::pair<int,int>;
using namespace std;

const int maxn = 1505;

int t, n, p, u, v, c[maxn], visited[maxn];
vector<int> adj[maxn];

void dfs(int x, vector<int>& vals)
{
    visited[x] = 1;
    vals.push_back(c[x]);
    for(auto v : adj[x])
        if(!visited[v])
            dfs(v, vals);
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    for(int cases = 0; cases < t; cases++)
    {
        cin >> n >> p;
        for(int i = 0; i < n; i++)
        {
            adj[i].clear();
            visited[i] = 0;
            cin >> c[i];
        }
        for(int i = 0; i < p; i++)
        {
            cin >> u >> v;
            u--; v--;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        int ans = 0;
        for(int i = 0; i < n; i++)
            if(!visited[i])
            {
                vector<int> vals;
                dfs(i, vals);
                sort(vals.begin(), vals.end());
                int sz = vals.size();
                for(int i = 0; i < sz; i++)
                    ans += min(vals[i], vals[sz - 1 - i]);
            }
        cout << ans << "\n";
    }
    return 0;
}

I'm still confused why the problem had $$$n \leq 1500$$$

We got TLE with NTT, though FFT is faster so maybe it might pass? We didn't end up trying it though.

We got TLE using a (hopefully) fairly fast FFT implementation, too

FFT is not required.

Since polynomial can be converted to this form :

(1 + x^k + x^2k + ... + x^mk)

We can find resultant polynomial in O(n) using prefix sums taken at k distances.

Please T1duS BlessRNG

Hint: The optimal answer will come from subsegment of length 2

For a given $$$l$$$, $$$r = l + 1$$$ is always the best possible choice. This can be easily proved by analyzing all possible options of the $$$r = l + 2$$$ case.

• If $$$a_{l + 2} \leq min(a_l, a_{l + 1}) \leq max(a_l, a_{l + 1}) $$$ — $$$answer= max(a_l, a_{l + 1}) - a_{l + 2} \geq max(a_l, a_{l + 1}) - min(a_l, a_{l + 1})$$$

• If $$$min(a_l, a_{l + 1}) \leq a_{l + 2} \leq max(a_l, a_{l + 1})$$$ — $$$answer=max(a_l, a_{l + 1}) - min(a_l, a_{l + 1})$$$

• If $$$min(a_l, a_{l + 1}) \leq max(a_l, a_{l + 1}) \leq a_{l + 2} $$$ — $$$answer= a_{l + 2} - min(a_l, a_{l + 1}) \geq max(a_l, a_{l + 1}) - min(a_l, a_{l + 1})$$$

So in all cases, the answer is no better than the answer of just taking $$$r = l + 1$$$.

Now when we update the power of a position $$$x$$$, the only two subarrays which change are $$$[x-1, x]$$$ and $$$[x, x + 1]$$$, so we can just remove the old values for these subarrays and add the new values.

So we want to perform the following operations quickly:

• Insert an element

• Remove an element

• Find minimum element

A multiset can do all these operations in $$$O(log n)$$$.

Could you please tell how did you get the answer for odd M?

Solve for $$$m \lt =6$$$ by hand. So now take $$$m \gt 6$$$, and let $$$p$$$ be the smallest prime factor of $$$m$$$.

First suppose $$$p \neq m$$$. Then consider the quadruple -

$$$(x,y,z,n)=(m/p,3,m/p+3,p) \text{ if } p \gt 2$$$

$$$(x,y,z,n)=(m/2,3,m/2+3,4) \text{ if } p=2$$$

To show this works, use the fact that $$$p \mid \binom{p}{i}$$$ for all $$$i \in {1,2,\dots, p-1}$$$.

Else if $$$m=p$$$, then take $$$n=p-2$$$, and notice that $$$x^{p-2} \equiv x^{-1} \pmod{p}$$$. So take the three cases $$$(x,y)=(3,3),$$$ $$$(3,4),$$$ $$$(4,4),$$$ and find $$$z \equiv (x^{-1}+y^{-1})^{-1} \pmod{p}$$$ for all three possibilities. It's easy to see that these three values will be different, and so one of them will be $$$ \gt 2$$$. Take the corresponding $$$(x,y,z)$$$.

Discussion session will be on 23rd. More details will be shared soon.