Binary Inversions (Codeforces 1760E)
Tags: Greedy, data structures

You are given a binary array$$$^{\dagger}$$$ of length $$$n$$$. You are allowed to perform one operation on it at most once. In an operation, you can choose any element and flip it: turn a $$$0$$$ into a $$$1$$$ or vice-versa.What is the maximum number of inversions$$$^{\ddagger}$$$ the array can have after performing at most one operation?$$$^\dagger$$$ A binary array is an array that contains only zeroes and ones.$$$^\ddagger$$$ The number of inversions in an array is the number of pairs of indices $$$i,j$$$ such that $$$i<j$$$ and $$$a_i > a_j$$$.

Input: The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — the length of the array.The following line contains $$$n$$$ space-separated positive integers $$$a_1$$$, $$$a_2$$$,..., $$$a_n$$$ ($$$0 \leq a_i \leq 1$$$) — the elements of the array.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

Output: For each test case, output a single integer  — the maximum number of inversions the array can have after performing at most one operation.

Note: For the first test case, the inversions are initially formed by the pairs of indices ($$$1, 2$$$), ($$$1, 4$$$), ($$$3, 4$$$), being a total of $$$3$$$, which already is the maximum possible.For the second test case, the inversions are initially formed by the pairs of indices ($$$2, 3$$$), ($$$2, 4$$$), ($$$2, 6$$$), ($$$5, 6$$$), being a total of four. But, by flipping the first element, the array becomes $$${1, 1, 0, 0, 1, 0}$$$, which has the inversions formed by the pairs of indices ($$$1, 3$$$), ($$$1, 4$$$), ($$$1, 6$$$), ($$$2, 3$$$), ($$$2, 4$$$), ($$$2, 6$$$), ($$$5, 6$$$) which total to $$$7$$$ inversions which is the maximum possible.

Sample Inputs:
5
4
1 0 1 0
6
0 1 0 0 1 0
2
0 0
8
1 0 1 1 0 0 0 1
3
1 1 1

Sample Outputs:
3
7
1
13
2

Solution (Python):
import math
import cmath
import string
result = string.ascii_lowercase

def XOR(n):
    return [n, 1, n + 1, 0][n % 4]
aa = []
1
for _ in range(int(input())):
    n = int(input())
    l = list(map(str, input().split()))
    c = 0
    c0 = 0
    c1 = 0
    c2 = 0
    if '0' in l:
        ind = l.index('0')
        countLeft1 = l[:ind].count('1')
        countRight0 = l[ind + 1:].count('0')
        if countRight0 > countLeft1:
            c1 = countRight0 - countLeft1
    if '1' in l:
        s = ''.join(l)
        ind2 = s.rfind('1')
        counterLeft1_2 = l[:ind2].count('1')
        counterRight0_2 = l[ind2:].count('0')
        if counterLeft1_2 > counterRight0_2:
            c2 = counterLeft1_2 - counterRight0_2
    if c1 or c2:
        if c1 > c2:
            l[ind] = '1'
        else:
            l[ind2] = '0'
    for i in range(n - 1, -1, -1):
        if l[i] == '1':
            c += c0
        else:
            c0 += 1
    aa.append(c)
for i in aa:
    print(i)

Solution (Python):
import sys

def input():
    return sys.stdin.readline().rstrip()

def print(*args, **kwargs):
    (sep, end) = (kwargs.pop('sep', ' '), kwargs.pop('end', '\n'))
    sys.stdout.write(sep.join(map(str, args)) + end)

def int_list():
    return [int(x) for x in input().split()]

def inversion(arr, freq, n):
    cnt = 0
    for i in range(n):
        if arr[i] == 1:
            cnt += freq[i]
    return cnt

def solve():
    T = int(input())
    for _ in range(T):
        n = int(input())
        arr = int_list()
        freq = [0] * n
        zero = 0
        for i in range(n - 1, -1, -1):
            freq[i] = zero
            if arr[i] == 0:
                zero += 1
        total = inversion(arr, freq, n)
        i = 0
        while i < n and arr[i] == 1:
            freq[i] -= 1
            i += 1
        if i < n and i >= 0:
            arr[i] = 1
        tempOne = inversion(arr, freq, n)
        if i < n and i >= 0:
            arr[i] = 0
        while i >= 0:
            if i >= 0 and i < n:
                freq[i] += 1
            i -= 1
        i = n - 1
        while i >= 0 and arr[i] == 0:
            i -= 1
        if i >= 0 and i < n:
            arr[i] = 0
        for j in range(i):
            freq[j] += 1
        tempTwo = inversion(arr, freq, n)
        print(max(total, tempOne, tempTwo))
if __name__ == '__main__':
    solve()

Solution (Python):
for a in [*open(0)][2::2]:
    a = [*map(int, a.split())]
    ans = 0
    z = 0
    n = len(a)
    for i in a:
        z += i
        if i == 0:
            ans += z
    x = ans
    for i in range(len(a)):
        if a[i] == 0:
            ans = max(ans, ans - i + n - z - 1)
            break
    for i in range(len(a) - 1, -1, -1):
        if a[i] == 1:
            ans = max(ans, x - n + i + z)
    print(ans)