Even AI Can Stumble: Learning from “Anu Has a Function” (Codeforces 1300C)
Today I want to share one of those experiences that shape you in competitive learning: facing a problem, believing you have the right technique, and discovering — after several attempts and reviews — that there was a key nuance you were missing.
Yes, even with ChatGPT’s help!
The problem is C. Anu Has a Function from Codeforces, which looks like just another bit manipulation problem… until you actually solve it.
📝 The problem: Anu Has a Function (1300C)
Summary:
Given an array of integers, you must reorder it to maximize the result of a special function based on OR and subtraction, applied in a chain to all its elements.
Goal: put first the element that maximizes the final value, according to how the bits interact among all the numbers.
💡 First approach: “Unique bits” (The trap!)
At first, both ChatGPT and I fell for the classic “find the unique bits” technique to determine which number contributes the most when placed first.
This technique consists of:
- Computing, for each number, the bits set to 1 that appear only in it and in no other number (“unique bits”).
- Placing first the number with the highest unique-bits value.
In most cases, this approach works…
But there are cases where the result is not optimal. That’s where the surprise came.
⚠️ The lesson: “Unique bits” are not always enough
In one of the test cases, I noticed the answer didn’t match the one accepted by Codeforces. Why?
If no number has a completely unique bit, or if several share the highest-weight bits, the “most unique bits” approach does not always maximize the final function.
Here I learned that bit problems require looking not only for uniqueness, but also for the weight of each bit (the most significant one can be decisive!).
First solution (Wrong):
#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;
}🏆 The optimal solution: “The highest unique bit”
The correct technique is:
- Find the highest bit (greatest weight) that is unique to a single number.
- That number must go first, because it guarantees that bit will contribute the greatest possible value to the final result.
- If no such unique bit exists, any order is valid.
How to implement it?
- Iterate over the bits from the highest (29) to the lowest (0).
- For each bit, count how many numbers have it set.
- If only one has it, that’s the key number and it must go first.
This logic is simple and efficient (O(n * 30)), but it’s not the one that usually jumps out at first attempt.
👨💻 Correct code in 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;
}
}
// If there's no unique bit, any order is valid
for (auto &x: a) cout << x << " ";
cout << endl;👨💻 Correct code in Python
n = len(a) # a is your list of numbers
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:
# Print the number with the unique bit first, then the rest
print(a[pos], end=" ")
for i in range(n):
if i != pos:
print(a[i], end=" ")
print()
break
else:
# If there's no unique bit, print any order
print(*a)🎯 Lessons learned and reflections
Not all “textbook” techniques are infallible.
Bit problems require thinking not only about value, but also about the uniqueness and weight of each bit.
Even AI can be wrong when there’s a subtle nuance in the logic.
Reviewing examples, analyzing test cases, and looking for alternative implementations is a fundamental part of learning.
Share your mistakes and corrections: that’s how you and others learn faster!
🚀 Conclusion
Next time a bit problem looks “easy”, check whether the most significant unique bit can change the game. Competitive programming is about questioning, analyzing, and correcting — even when the answer seems obvious. Have you ever blindly trusted a technique and then found a trap? Tell me your story or share your own findings in the comments!