🏆 Meta Hacker Cup 2018 — Qualification Round: Interception

Difficulty: Hard
Topic: Polynomials, parenthesization, root-finding
📄 View original problem statement

Problem Summary

Given coefficients of an N-degree polynomial, normally we’d evaluate it as:

P_N * x^N + P_{N-1} * x^{N-1} + ... + P_1 * x + P_0

But this problem removes all parentheses and order-of-operations rules. We must find all x-intercepts for every possible way of parenthesizing the expression.

For example, with polynomial 9*x^0 + 0*x^1 + (-6)*x^2:

• Standard evaluation: -6x² + 0x + 9 = 0 → x = ±1.22…
• But with different parenthesizations like ((9 + 0x) + -6x*x), we get different polynomials!

This tests understanding of polynomial evaluation, parenthesization strategies, and root-finding algorithms.

Understanding the Problem

Let’s trace through Sample 1:

Input:

N = 1 (polynomial degree)
P = [1, 1] (coefficients)

This represents: P₁x¹ + P₀x⁰ = 1*x + 1

Standard form: x + 1 = 0 → x = -1