AND, OR and square sum

Explicación

Pista 1

Observemos que $x \ \& \ y + x \ | \ y = x + y$ , así que la suma total de todos los elementos nunca cambia.

¿Por qué es cierto?

Analicemos cuánto aporta cada posición de bit a la suma. Para cada $i$ , sea $A$ el $i$ -ésimo bit más a la derecha de $x$ y $B$ el $i$ -ésimo bit más a la derecha de $y$ ( $A, B \in \{0, 1\}$ ).

Probando todos los casos posibles para $A$ y $B$ , obtenemos que $A \ \& \ B + A \ | \ B = A + B$ , como se muestra en la siguiente tabla de verdad:

A	B	A & B	A \| B	A & B + A \| B	A + B
0	0	0	0	0	0
0	1	0	1	1	1
1	0	0	1	1	1
1	1	1	1	2	2

Sumando las posiciones de bits individuales obtenemos $x \ \& \ y + x \ | \ y = x + y$ .

Pista 2

Observemos que antes y después de cada operación, el número de bits activos en cada posición no cambia.

Por ejemplo, sea $x = 110_2$ , $y = 101_2$ . $x \ \& \ y = 100_2$ , y $x \ | \ y = 111_2$ .

Los bits más a la derecha de $y$ y de $x \ | \ y$ están activos.
Los segundos bits más a la derecha de $x$ y de $x \ | \ y$ están activos.
Los terceros bits más a la derecha de $x$ , $y$ , $x \ \& \ y$ y $x \ | \ y$ están activos.

Antes y después de las operaciones, siempre hay un bit activo en la posición más a la derecha, un bit activo en la segunda posición más a la derecha, y dos bits activos en la tercera posición más a la derecha.

Pista 3

Observemos que al realizar una operación, $\sum_{i=1}^{n}{a_i^2}$ aumenta cuando $|x - y|$ aumenta.

Solución

Queremos seguir realizando operaciones de modo que $|x - y|$ aumente. De hecho, como $x \ \& \ y \leq \min(x, y)$ y $x \ | \ y \geq \max(x, y)$ , realizar una operación nunca disminuye $|x - y|$ . Por lo tanto, la configuración óptima ocurre cuando es imposible cambiar $|x - y|$ con más operaciones. Esto sucede cuando, para cualesquiera dos valores $a_i$ y $a_j$ , $a_i \ \& \ a_j = \min(a_i, a_j)$ , y $a_i \ | \ a_j = \max(a_i, a_j)$ . En otras palabras, cuando ordenamos la configuración óptima de forma creciente, $a_i \ \& \ a_{i + 1} = a_i$ .

La configuración óptima se puede construir tratando cada bit por separado. Este enfoque tiene en cuenta la Pista 2, que afirma que ninguna operación altera la cantidad de bits activos en una posición dada. Para cada posición de bit, movemos todos los bits activos de esa posición al extremo derecho del arreglo.

Por ejemplo, consideremos el arreglo [1, 5, 4, 7, 3], que en binario se representa como [001, 101, 100, 111, 011].

Para la posición más a la derecha, movemos todos los bits activos al extremo derecho del arreglo. Tras esta operación, el arreglo queda [000, 101, 101, 111, 011].
Para la segunda posición más a la derecha, no hace falta hacer nada porque todos los bits activos ya están en el extremo derecho del arreglo.
Para la tercera posición más a la derecha, movemos todos los bits activos al extremo derecho del arreglo. Esto da el arreglo [000, 001, 101, 111, 111].

Esto da el arreglo reconfigurado: [000, 001, 101, 111, 111]. En decimal, este nuevo arreglo se lee [0, 1, 5, 7, 7]. Finalmente, hallamos la suma de los cuadrados de los elementos de este nuevo arreglo. El total resultante proporciona la solución deseada.

Implementación

Complejidad temporal: $\mathcal{O}(N)$

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
const int MAX_BIT = 20;
 
int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) { cin >> a[i]; }
 
	// Contar el número de bits activos en cada posición.
	vector<int> num_bits(MAX_BIT);
	for (int i = 0; i < MAX_BIT; i++) {
		for (int j = 0; j < n; j++) {
			if (a[j] & (1ll << i)) { num_bits[i]++; }
		}
	}
 
	/*
	 * Crear el arreglo óptimo y calcular
	 * la suma de los cuadrados del nuevo arreglo.
	 */
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		long long new_val = 0;
		for (int j = 0; j < MAX_BIT; j++) {
			if (num_bits[j]) {
				new_val |= (1ll << j);
				num_bits[j]--;
			}
		}
		ans += new_val * new_val;
	}
	cout << ans << "\n";
}


import java.io.*;
import java.util.*;
 
public class AndOrSquareSum {
	public final static int MAX_BIT = 20;
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		int n = Integer.parseInt(br.readLine().trim());
		int[] a = new int[n];
 
		String[] inputs = br.readLine().trim().split(" ");
		for (int i = 0; i < n; i++) { a[i] = Integer.parseInt(inputs[i]); }
 
		// Contar el número de bits activos en cada posición.
		int[] num_bits = new int[MAX_BIT];
		for (int i = 0; i < MAX_BIT; i++) {
			for (int j = 0; j < n; j++) {
				if ((a[j] & (1L << i)) != 0) { num_bits[i]++; }
			}
		}
 
		/*
		 * Crear el arreglo óptimo y calcular
		 * la suma de los cuadrados del nuevo arreglo.
		 */
		long ans = 0;
		for (int i = 0; i < n; i++) {
			long new_val = 0;
			for (int j = 0; j < MAX_BIT; j++) {
				if (num_bits[j] != 0) {
					new_val |= (1L << j);
					num_bits[j]--;
				}
			}
			ans += new_val * new_val;
		}
 
		System.out.println(ans);
	}
}


MAX_BIT = 20
 
n = int(input())
a = list(map(int, input().split()))
 
# Contar el número de bits activos en cada posición.
num_bits = [0] * MAX_BIT
for i in range(MAX_BIT):
	for j in range(n):
		if a[j] & (1 << i):
			num_bits[i] += 1
 
# Crear el arreglo óptimo y calcular
# la suma de los cuadrados del nuevo arreglo.
ans = 0
for i in range(n):
	curr = 0
	for j in range(MAX_BIT):
		if num_bits[j]:
			curr |= 1 << j
			num_bits[j] -= 1
	ans += curr * curr
 
print(ans)