G - Flip Row or Col
Source: atcoder
Difficulty: 600

Problem Statement
There is a
H \times W
grid, and each cell contains
0
or
1
. The cell at the
i
-th row from the top and the
j
-th column from the left contains an integer
A_{i,j}
.
You can perform the following two operations any number of times in any order:
Operation X: Choose an integer
x
(
1 \leq x \leq H
). For every integer
1 \leq y \leq W
, replace
A_{x,y}
with
1 - A_{x,y}
.
Operation Y: Choose an integer
y
(
1 \leq y \leq W
). For every integer
1 \leq x \leq H
, replace
A_{x,y}
with
1 - A_{x,y}
.
Find the minimum possible value of
\displaystyle \sum_{x=1}^H\sum_{y=1}^W A_{x,y}
after the process.
Constraints
1 \leq H \leq 2\times 10^5
1 \leq W \leq 18
H
and
W
are integers.
A_{i,1}A_{i,2}\ldots A_{i,W}
is a length-
W
string consisting of
0
and
1
.
Input
The input is given from Standard Input in the following format:
H
W
A_{1,1}A_{1,2}\ldots A_{1,W}
A_{2,1}A_{2,2}\ldots A_{2,W}
\vdots
A_{H,1}A_{H,2}\ldots A_{H,W}
Output
Print the answer.
Sample Input 1
3 3
100
010
110
Sample Output 1
2
By performing the following operations, the grid changes as shown below, and you get
\displaystyle \sum_{x=1}^H\sum_{y=1}^W A_{x,y} = 2
.
Operation Y with
y=1
Operation X with
x=2
It is impossible to make
\displaystyle \sum_{x=1}^H\sum_{y=1}^W A_{x,y} \leq 1
, so the answer is
2
.
Sample Input 2
3 4
1111
1111
1111
Sample Output 2
0
Sample Input 3
10 5
10000
00111
11000
01000
10110
01110
10101
00100
00100
10001
Sample Output 3
13

C++ solution:
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define ldb long double
#define pii pair<int,int>
#define mkp make_pair
#define mkt make_tuple
#define fr first
#define se second
#define uset unordered_set
#define umap unordered_map
#define pqueue priority_queue
#define all(_box) _box.begin(),_box.end()
#define ppc __builtin_popcount
#define ctz __builtin_ctz
#define clz __builtin_clz
#define lbd lower_bound
#define ubd upper_bound
#define deb(x) cerr<<#x<<'='<<(x)<<' '
using namespace std;
const int N=2e5+4;
const int B=18;
int n,m;
ll f[1<<B],cnt[1<<B],ans[1<<B];

void tran(ll &x,ll &y){
    tie(x,y)=mkp(x+y,x-y);
}
void fwt(ll a[]){
    for(int o=1;o<(1<<m);o<<=1)
        for(int i=0;i<(1<<m);i+=o<<1)
            for(int j=0;j<o;j++)
                tran(a[i+j],a[i+j+o]);
}
void ifwt(ll a[]){
    for(int o=1;o<(1<<m);o<<=1)
        for(int i=0;i<(1<<m);i+=o<<1)
            for(int j=0;j<o;j++)
                tran(a[i+j],a[i+j+o]);
	for(int i=0;i<(1<<m);i++)a[i]>>=m;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    cin>>n>>m;
    for(int i=1;i<=n;i++){
        string s;
        int x=0;
        cin>>s;
        for(char c:s)x=x<<1|(c&1);
        cnt[x]++;
    }
    for(int i=0;i<(1<<m);i++)
        f[i]=min(ppc(i),m-ppc(i));
    
    fwt(f),fwt(cnt);
    for(int i=0;i<(1<<m);i++)ans[i]=f[i]*cnt[i];
    ifwt(ans);
    cout<<*min_element(ans,ans+(1<<m));
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	scanner.Scan()
	H, _ := strconv.Atoi(scanner.Text())
	scanner.Scan()
	W, _ := strconv.Atoi(scanner.Text())

	maxMask := 1 << W
	C := make([]int, maxMask)

	for i := 0; i < H; i++ {
		scanner.Scan()
		s := scanner.Text()
		x, _ := strconv.ParseInt(s, 2, 64)
		C[x]++
	}

	g := make([]int, maxMask)
	for x := 0; x < maxMask; x++ {
		cnt := 0
		for j := 0; j < W; j++ {
			if x&(1<<j) != 0 {
				cnt++
			}
		}
		g[x] = min(cnt, W-cnt)
	}

	fwt(C)
	fwt(g)

	tmp := make([]int, maxMask)
	for i := 0; i < maxMask; i++ {
		tmp[i] = C[i] * g[i]
	}

	invFwt(tmp)

	minVal := math.MaxInt32
	for _, v := range tmp {
		if v < minVal {
			minVal = v
		}
	}
	fmt.Println(minVal)
}

func fwt(a []int) {
	n := len(a)
	h := 1
	for h < n {
		for i := 0; i < n; i += h * 2 {
			for j := i; j < i+h; j++ {
				x := a[j]
				y := a[j+h]
				a[j] = x + y
				a[j+h] = x - y
			}
		}
		h <<= 1
	}
}

func invFwt(a []int) {
	n := len(a)
	h := 1
	for h < n {
		for i := 0; i < n; i += h * 2 {
			for j := i; j < i+h; j++ {
				x := a[j]
				y := a[j+h]
				a[j] = (x + y) / 2
				a[j+h] = (x - y) / 2
			}
		}
		h <<= 1
	}
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

Java solution:
import java.io.*;
import java.util.*;
public class Main {
    static void fwt(long[] arr, int n) {
        for (int len = 1; len < n; len <<= 1) {
            for (int i = 0; i < n; i += (len << 1)) {
                for (int j = 0; j < len; j++) {
                    long u = arr[i+j], v = arr[i+j+len];
                    arr[i+j] = u + v;
                    arr[i+j+len] = u - v;
                }
            }
        }
    }
    static void ifwt(long[] arr, int n) {
        for (int len = 1; len < n; len <<= 1) {
            for (int i = 0; i < n; i += (len << 1)) {
                for (int j = 0; j < len; j++) {
                    long u = arr[i+j], v = arr[i+j+len];
                    arr[i+j] = (u + v) / 2;
                    arr[i+j+len] = (u - v) / 2;
                }
            }
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader padh = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter likh = new PrintWriter(System.out);
        StringTokenizer tok = new StringTokenizer(padh.readLine());
        int kulRows = Integer.parseInt(tok.nextToken());
        int kulCols = Integer.parseInt(tok.nextToken());
        int L = 1 << kulCols;
        long[] freq = new long[L];
        for (int i = 0; i < kulRows; i++) {
            String line = padh.readLine();
            int mask = 0;
            for (int j = 0; j < kulCols; j++) {
                if (line.charAt(j) == '1') {
                    mask |= (1 << j);
                }
            }
            freq[mask]++;
        }
        long[] gArr = new long[L];
        for (int mask = 0; mask < L; mask++) {
            int ones = Integer.bitCount(mask);
            gArr[mask] = Math.min(ones, kulCols - ones);
        }
        long[] F = Arrays.copyOf(freq, L);
        long[] G = Arrays.copyOf(gArr, L);
        
        fwt(F, L);
        fwt(G, L);
        
        long[] conv = new long[L];
        
        for (int i = 0; i < L; i++) {
            conv[i] = F[i] * G[i];
        }
        ifwt(conv, L);
        long ans = Long.MAX_VALUE;
        for (int mask = 0; mask < L; mask++) {
            ans = Math.min(ans, conv[mask]);
        }
        likh.println(ans);
        likh.flush();
    }
}

JavaScript solution:
const { readFileSync } = require('fs');

function fourierTransform(f) {
    const n = f.length;
    const levels = Math.log2(n);
    for (let d = 0; d < levels; d++) {
        const m = 1 << d;
        for (let i = 0; i < n; i += (m << 1)) {
            for (let j = 0; j < m; j++) {
                const x = f[i + j];
                const y = f[i + j + m];
                f[i + j] = x + y;
                f[i + j + m] = x - y;
            }
        }
    }
    return f;
}

function solve() {
    const input = readFileSync(0, 'utf-8').split('\n').filter(line => line.trim() !== '');
    let ptr = 0;
    const [H, W] = input[ptr++].split(' ').map(Number);
    const A = [];
    for (let i = 0; i < H; i++) {
        const bits = input[ptr++].trim();
        let mask = 0;
        for (let j = 0; j < W; j++) {
            if (bits[j] === '1') {
                mask |= 1 << (W - 1 - j);
            }
        }
        A.push(mask);
    }

    const size = 1 << W;
    const popcount = new Array(size).fill(0);
    for (let U = 1; U < size; U++) {
        popcount[U] = popcount[U & (U - 1)] + 1;
    }

    const g = new Array(size).fill(0);
    for (let U = 0; U < size; U++) {
        g[U] = Math.min(popcount[U], W - popcount[U]);
    }

    const h = new Array(size).fill(0);
    for (const a of A) {
        h[a]++;
    }

    const Fg = fourierTransform([...g]);
    const Fh = fourierTransform([...h]);
    const Fgh = new Array(size);
    for (let i = 0; i < size; i++) {
        Fgh[i] = Fg[i] * Fh[i];
    }
    const gh = fourierTransform([...Fgh]);
    let minSum = Infinity;
    for (let i = 0; i < size; i++) {
        const current = Math.round(gh[i] / size);
        if (current < minSum) {
            minSum = current;
        }
    }

    console.log(minSum);
}

solve();

Python solution:
import os
import sys
INF = 1 << 60
MOD = 119 << 23 | 1

def fourier(f):
    W = len(f).bit_length() - 1
    for d in range(W):
        for U in range(1 << W):
            if U >> d & 1 == 0:
                V = U ^ 1 << d
                f[U], f[V] = f[U] + f[V], f[U] - f[V]
    return f

def solve():
    H, W = map(int, input().split())
    A = [int(input(), 2) for _ in range(H)]

    popcount = [0] * (1 << W)
    for U in range(1, 1 << W):
        lsb = U & -U
        popcount[U] = popcount[U ^ lsb] + 1

    g = [min(c, W - c) for c in popcount]
    h = [0] * (1 << W)
    for a in A:
        h[a] += 1
    
    Fg = fourier(g)
    Fh = fourier(h)
    Fgh = [a * b for a, b in zip(Fg, Fh)]
    gh = [x >> W for x in fourier(Fgh)]

    ans = min(gh)
    print(ans)

if __name__ == "__main__":
    if "ATCODER" in os.environ:
        input = lambda: sys.stdin.readline().rstrip()
        solve()
    else:
        from io import StringIO
        import unittest
        class TestClass(unittest.TestCase):
            def test_sample1(self):
                input = """3 3
100
010
110"""
                expected = """2"""
                self.judge(input, expected)

            def test_sample2(self):
                input = """3 4
1111
1111
1111"""
                expected = """0"""
                self.judge(input, expected)

            def test_sample3(self):
                input = """10 5
10000
00111
11000
01000
10110
01110
10101
00100
00100
10001"""
                expected = """13"""
                self.judge(input, expected)

            def judge(self, input, expected):
                stdout, stdin = sys.stdout, sys.stdin
                sys.stdout, sys.stdin = StringIO(), StringIO(input)
                solve()
                sys.stdout.seek(0)
                actual = sys.stdout.read()[:-1]
                sys.stdout, sys.stdin = stdout, stdin
                self.assertEqual(expected, actual)
        unittest.main(verbosity=2)

Ruby solution:
a=[0]*4**9
w=$<.min{a[_1.to_i 2]+=1}[/ .*/].to_i
f=->a{w.times{|k|i=-1
a.map!{a[1<<k^i+=1]+_1-_1*i[k]*3}}
a}
p f[f[(0...1<<w).map{[c=_1.digits(2).sum,w-c].min}].zip(f[a]).map{_1*_2}].min>>w