Codeforces Round #835 (Div. 4) E. Binary Inversions

Codeforces Round #835 (Div. 4) E. Binary Inversions

Let’s find out how to count the number of binary inversions, without flips. This is the number of $1$s that appear before a $0$. To do this, iterate through the array and keep a running total $k$ of the number of $1$s seen so far. When we see a $0$, increase the total inversion count by $k$, since this $0$ makes $k$ inversions: one for each of the $1$s before it.

Now let’s see how to maximize the inversions. Consider the flip $0\to 1$. We claim that it is best to always flip the earliest $0$ in the array. It’s never optimal to flip a later $0$, since we have strictly fewer $0$s after it to form inversions. Similarly, we should flip the latest $1$ in the array.

Now recalculate the answer for these two choices for flipping, and pick the maximum. The complexity is $O(n)$.

#include
using namespace std;

int main()
{
    int T=1;cin>>T;
    while(T--)
    {
        int n;cin>>n;
        vector<int> a(n);

        int sum0=0;
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
            if(!a[i]) sum0++;
        }

        int mx=0;
        int res0=0,res1=0;
        long long ans=0;
        for(int i=0;i<n;i++)
        {
            if(a[i])
            {
                ans+=sum0-res0;
                mx=max(mx,res1-(sum0-res0));
                res1++;
            }
            else
            {
                ans+=res1;
                mx=max(mx,(sum0-res0-1)-res1);
                res0++;
            }
        }
        cout<<ans/2+mx<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40