August 3, 2025

Incluso la IA puede tropezar: Aprendiendo de “Anu Has a Function” (Codeforces 1300C)

Visual relacionado al problema 'Anu Has a Function' de Codeforces

Hoy quiero compartir una de esas experiencias que te marcan en el aprendizaje competitivo: enfrentarte a un problema, creer tener la técnica correcta y descubrir —tras varios intentos y repasos— que hay un matiz clave que se te escapaba.
¡Sí, incluso con la ayuda de ChatGPT!

El problema es C. Anu Has a Function de Codeforces, que aparenta ser uno más de manipulación de bits… hasta que lo resuelves de verdad.


📝 El problema: Anu Has a Function (1300C)

Enunciado resumido:
Dado un array de enteros, debes reordenarlo para maximizar el resultado de una función especial basada en OR y resta, aplicada en cadena a todos sus elementos.
Objetivo: poner al inicio el elemento que maximiza el valor final, de acuerdo a cómo interactúan los bits entre todos los números.


💡 Primer enfoque: “Bits únicos” (¡La trampa!)

Al principio, tanto yo como ChatGPT caímos en la clásica técnica de “encontrar los bits únicos” para determinar qué número aporta el máximo al ponerlo primero.
Esta técnica consiste en:

  • Calcular, para cada número, los bits en 1 que solo aparecen en él y no en ningún otro (“bits únicos”).
  • Colocar al inicio el número con mayor valor de bits únicos.

En la mayoría de los casos, este enfoque funciona…
Pero hay casos donde el resultado no es óptimo. Aquí llegó la sorpresa.


⚠️ La lección: “Bits únicos” no siempre bastan

En uno de los test cases, noté que la respuesta no coincidía con la aceptada por Codeforces. ¿Por qué?
Si ningún número tiene un bit completamente único, o si varios comparten los bits de mayor peso, el enfoque de “más bits únicos” no siempre maximiza la función final.

Aquí aprendí que los problemas de bits requieren no solo buscar unicidad, sino también el peso de cada bit (¡el más significativo puede ser decisivo!).

Primera solución (Equivocada):

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (auto &x : arr) cin >> x;

    int or_all = 0;
    for (int x : arr) or_all |= x;

    int best_unique = -1, idx = 0;
    for (int i = 0; i < n; ++i) {
        int unique = arr[i] & (~(or_all ^ arr[i]));
        if (unique > best_unique) {
            best_unique = unique;
            idx = i;
        }
    }

    cout << arr[idx] << " ";
    for (int i = 0; i < n; ++i)
        if (i != idx)
            cout << arr[i] << " ";
    cout << "\n";
    return 0;
}

🏆 La solución óptima: “El bit único más alto”

La técnica correcta es:

  1. Buscar el bit más alto (mayor peso) que sea único en un solo número.
  2. Ese número debe ir primero, porque así garantiza que ese bit aportará el mayor valor posible al resultado final.
  3. Si no existe tal bit único, cualquier orden es válido.

¿Cómo implementarlo?

  • Recorre los bits del más alto (29) al más bajo (0).
  • Para cada bit, cuenta cuántos números lo tienen encendido.
  • Si solo uno lo tiene, ese es el número clave y debe ir primero.

Esta lógica es sencilla y eficiente (O(n * 30)), pero no es la que siempre salta a la vista en un primer intento.


👨‍💻 Código correcto en C++

for (int k = 29; k >= 0; k--) {
    int count = 0, pos = -1;
    for (int i = 0; i < n; i++) {
        if ((a[i] >> k) & 1) {
            count++;
            pos = i;
        }
    }
    if (count == 1) {
        cout << a[pos] << " ";
        for (int i = 0; i < n; i++)
            if (i != pos) cout << a[i] << " ";
        cout << endl;
        return;
    }
}
// Si no hay bit único, cualquier orden es válido
for (auto &x: a) cout << x << " ";
cout << endl;

👨‍💻 Código correcto en Python

n = len(a)  # a es tu lista de números

for k in range(29, -1, -1):
    count = 0
    pos = -1
    for i in range(n):
        if (a[i] >> k) & 1:
            count += 1
            pos = i
    if count == 1:
        # Imprime primero el número con el bit único, luego el resto
        print(a[pos], end=" ")
        for i in range(n):
            if i != pos:
                print(a[i], end=" ")
        print()
        break
else:
    # Si no hay bit único, imprime cualquier orden
    print(*a)

🎯 Lecciones aprendidas y reflexiones

No todas las técnicas “de manual” son infalibles.

Los problemas de bits requieren pensar no solo en el valor, sino en la unicidad y el peso de cada bit.

Incluso la IA puede equivocarse si hay un matiz sutil en la lógica.

Revisar ejemplos, analizar test cases y buscar implementaciones alternativas es parte fundamental del aprendizaje.

Comparte tus errores y correcciones: ¡así tú y otros aprenden más rápido!


🚀 Conclusión

La próxima vez que un problema de bits parezca “sencillo”, verifica si el bit más significativo y único puede cambiar el juego. La programación competitiva se trata de cuestionar, analizar y corregir —incluso cuando la respuesta parece obvia. ¿Te pasó alguna vez confiar ciegamente en una técnica y luego encontrar una trampa? ¡Cuéntame tu historia o comparte tus propios hallazgos en los comentarios!


📝 Referencias

Share