🎮 CENTAURI

Nintendo Sponsored Contest — CodinGame.com

A complete and deterministic solution to the GF(2) bitplane decoding challenge

---

🧩 The Challenge

In this Nintendo Open Contest problem, an encoded message is provided as a sequence of hexadecimal values representing a binary polynomial over GF(2).

The task is to decode this message by finding all valid decoded values that satisfy a specific algebraic relationship — and to present them exactly as required by the judge.

This is not a “find one answer” problem.
It is a find all valid answers problem.

---

🔍 Problem Statement (Simplified)

You are given a polynomial P(x) encoded as two S-bit planes.

Your goal is to find every pair of polynomials:

A(x), B(x)

such that:

A(x) · B(x) = P(x) (over GF(2))

with the constraints:

• deg(A) < S
• deg(B) < S

If more than one decoded value exists, all must be printed, in the correct order.

---

✅ The Solution

CENTAURI solves this problem by working directly in the algebra of GF(2).

At a high level, the program:

1. Interprets the input as a polynomial over GF(2)
2. Factorizes the polynomial into irreducible components
3. Enumerates all valid factor pairings that respect the degree limits
4. Verifies each candidate locally
5. Outputs the results in the required canonical order

This guarantees:

• Completeness — no valid decoded value is missed
• Correctness — no invalid value is printed
• Determinism — the same input always produces the same output

---

📥 Input Format

S < S/16 hexadecimal 32-bit words >

• 0 < S ≤ 256
• S is a multiple of 32
• The input encodes exactly 2S bits, least-significant bit first

---

📤 Output Format

Each line represents one valid decoded value:

A0 A1 … A(L−1) B0 B1 … B(L−1)

where L = S / 32.

• Lowercase hexadecimal
• Zero-padded to 8 digits
• Ordered exactly as expected by the contest judge

---

📐 Ordering & Edge Cases

• All valid decoded values are printed
• Results are sorted deterministically
• Duplicate outputs are removed
• When the encoded polynomial has degree < S, the trivial decoded values
  (1, P) and (P, 1) are also included — matching official reference outputs

---

⚙️ Build & Run

g++ -O2 -std=c++17 centauri.cpp -o centauri
./centauri < input.txt


⸻

🏁 Final Notes
	•	No randomness
	•	No floating point arithmetic
	•	No undefined behavior
	•	Fixed memory footprint
	•	Fully self-verifying

This submission was validated against all provided test cases.

⸻

📄 License

MIT License
© 2025 Antonio Torquato