Since it has been quite a while since this problem was posted, and it was actually on ELMO, would the OP mind posting his/the official solution?

OK, I was planning to write everything up soon anyway (but I've been getting distracted a lot). As I tried to point out in my original post, this is unfortunately a special case of Ehrenfucht's criterion, but IMO the problem is still instructive. I suggested the first solution during our initial discussion (it's essentially a Newton polygon argument), and found the second solution after the contest (though in spirit, the two solutions are actually the same), but I don't know if there are other fundamentally different approaches, as no ELMO takers made much progress (I gave a total of two points, neither of which really should've been given). Solution 1: It will be convenient in this solution to set $\deg0=0$. If $f(x,y)=x^n+x^{n-1}f_1(y)+\cdots+x^0f_n(y)$ for some polynomials $f_1,\ldots,f_n$ and positive integer $n$ (call such a polynomial good), set $\alpha(f)=\max_{1\le i\le n}\deg{f_i}/i$ (let $f_0=1$). (This "modified degree" is related to Newton polygons.) Lemma: If $f=gh$ for some nonconstant good polynomials $f,g,h$, then $\alpha(f)=\max(\alpha(g),\alpha(h))$. Proof: Obviously $\alpha(f)\le\max(\alpha(g),\alpha(h))$, so it's enough to show that $\alpha(f)\ge\max(\alpha(g),\alpha(h))$. WLOG $\alpha(g)\ge \alpha(h)$. Note that for all nonzero $k$, $\deg{g_0h_k}/k=\deg{h_k}/k$ and $\deg{g_kh_0}/k=\deg{g_k}/k$. If $\alpha(g)>\alpha(h)$, then consider the smallest $u\ge1$ such that $\deg{g_u}/u=\alpha(g)$; by the minimality of $u$, \[\deg{f_u}/u=\deg{g_uh_0}/u=\deg{g_u}/u=\alpha(g),\]so we're done in this case ($g_0h_u$ is not an issue if it exists). Otherwise, $\alpha(g)=\alpha(h)=r$, so take the largest $u,v\ge1$ such that $\deg{g_u}/u=\deg{h_v}/v=r$; by the maximality of $u,v$, \[\deg{f_{u+v}}/(u+v)=\deg{g_uh_v}/(u+v)=r,\]as desired (by maximality, $g_0h_{u+v},g_{u+v}h_0$ are not issues if they exist).$\blacksquare$ Go by contradiction, letting $m=\deg{f}$ and $n=\deg{g}$. If one of $\deg{f},\deg{g}$ is constant, then the other must be linear or constant (and the problem is obvious), so suppose $m,n>0$. Returning to the original problem, suppose $f(x)+g(y)=P(x,y)Q(x,y)$. By scaling we can assume $f,P,Q$ are monic in $x$; clearly $f,P,Q$ are good. If $\deg_x{P}=a>0$ and $\deg_x{Q}=b>0$ (if one of these degrees is 0, then $PQ$ must contain a term divisible by $xy$), we have \[\max(\deg{P_a}/a,\deg{Q_b}/b)\le\max(\alpha(P),\alpha(Q))\le\alpha(f(x)+g(y))=n/m,\]but $(\deg{P_a}+\deg{Q_b})/(a+b)=n/m$, contradicting the fact that $a,b\ge1$ (since $\gcd(m,n)=1$). Solution 2: Define $m,n,a,b$ as before and again go by contradiction (it's enough to deal with the case $m,n>0$). Then there exists a complex number $c\ne0$ such that $\deg_z(f(z^n)+g(cz^m))<mn$ (we are just "cancelling out" the leading coefficients). To get the desired contradiction, it suffices to show that $\deg_z P(z^n,cz^m) \ge an$ and $\deg_z Q(z^n,cz^m) \ge bn$, as $a+b=m$. The method for A5 also works here: since $\gcd(m,n)=1$, there don't exist distinct pairs of integers $(i,j),(i',j')\in[0,m)\times[0,n)$ such that $(z^n)^i (z^m)^j = (z^n)^{i'} (z^m)^{j'}$ (as a polynomial identity in $z$), so when we substitute $x=z^n$ and $y=cz^m$, there's no way to cancel any terms in either of $P,Q$. In particular, the $(z^n)^a,(z^n)^b$ terms of $P,Q$ cannot be canceled, so we're done.

Denote $m=\deg f\,,\, n=\deg g$. Suppose on the contrary, $P$ and $Q$ are not constant. Then $\deg_x P<m, \deg_y P<n$. The idea is to construct complex pairs $(x,y), P(x,y)=0$, with $|x|\to \infty, |y|\to \infty$ and $x^r \sim y^s$, where $r<m, s<n$; and then to show it's not possible for big enough such $x,y$, to hold $P(x)+Q(y)=0$, since $m/n \neq r/s$. Here $x^r \sim y^s$ means $y^s= C\cdot x^r + o(x^r)$, where $C$ is a constant and $o(x^r)$ means it's growth is negligible compared to the growth of $x^r$. Thus, the problem reduces to a pure analytic one. In order to implement that plan, divide $P(x,y)$ by $x^k$, where $k=\deg_x P$ and we obtain a sum $P_1(x,y):=P/x^k=\sum_{ (i,j)\in I} c_{i,j} y^i/x^j$. Let $s/r=\max_{(i,j)\in I} i/j$, hence $P_1(x,y)= \sum_{i} c_i \left(\frac{y^s}{x^r}\right)^i+ \sum d_i \left(\frac{y^s}{x^r}\right)^{\alpha_i} x^{-\beta_i} $, where $\alpha_i,\beta_i$ may not be integer, but $\alpha_i,\beta_i >0$. Take $C$ to be a root of $\sum_{i} c_i z^i$, and apply Rouche's theorem with respect to $\sum_{i} c_i \left(\frac{y^s}{x^r}\right)^i$ and $\sum d_i \left(\frac{y^s}{x^r}\right)^{\alpha_i} x^{-\beta_i}$, for a fixed, big enough $x$, where $y$ vary around on a contour close enough (but not too much) around $y_0$, such that $y_0^s=C x^r$. As a result, one get that $P_1$, as a function of $y$, also has zero inside that contour. Thus, we proved there are enough $(x,y)$ with $P(x,y)=0, |x|,|y| \to \infty\,,\,y^s= C\cdot x^r + o(x^r)$, where $r<m, s<n$. For all these $(x,y)$, it must hold $P(x)+Q(y)=0$. But $Q(y)=\text{const}\cdot x^{rn/s}+ o(x^{rn/s}) $, therefore $r n /s =m$, hence $m/n=r/s$. But, it's impossible since $ \gcd(\deg f,\deg g)=1 $ and $r<m, s<n$. Comment. It's essentially the same argument as the first solution of the author (Victor Wang), but with a bit different point of view. I remember that I tried this problem at the time it was first published here, more than two years ago. Unfortunately, without success and I gave up soon. A few days ago, I saw this problem again, posted in a duplicated thread at the forum. This time, luckily for me, the right approach appeared. EDIT: A typo corrected.

Let the degrees of $f$ and $g$ be $a, b$ respectively. Note that $f(x^b) + g(x^a) = P(x^b, y^a) \cdot Q(x^b, y^a).$ For a polynomial $T(x, y) \in \mathbb{C}[x, y]$, let $\alpha (T)$ be the sum of the terms of $T$ which are of maximal degree, where the degree of a term is the sum of the exponents of $x$ and $y$. Notice that $\alpha$ is both additive and multiplicative, and so $\alpha(f(x^b)) + \alpha(g(x^a)) = \alpha(P(x^b, y^a)) \cdot \alpha(Q(x^b, y^a)).$ Let the degrees of $P(x^b, y^a), Q(x^b, y^a)$ be $d_1$ and $d_2$ respectively. Observe that $\alpha(f(x^b))$ is $z_x x^{ab}$ for some nonzero complex number $z_x$, and $\alpha(g(y^a))$ is $z_y y^{ab}$ for some nonzero complex number $z_y.$ This implies that the terms $x^{d_1}, x^{d_2}$ must appear in $\alpha(P(x^b, y^a)), \alpha(Q(x^b, y^a))$ respectively, and same for $y^{d_1}, y^{d_2}.$ These imply that $b| d_1, d_2$ and $a|d_1, d_2$, so from $\gcd(a, b) = 1$ we get $ab | d_1, d_2.$ Since $d_1 + d_2 = ab$ we get that one of them is zero, and hence one of $P, Q$ is constant. $\square$

FTSOC suppose that \[ f(x) + g(y) = p(x,y)q(x,y) \]for some $p(x, y)$ and $q(x, y)$. Let $F = \deg f, G = \deg G$. Let $x = z^G$ and $y = cz^F$ such that \[ f(z^G) + g(cz^F) = p(z^G,cz^F)q(z^G,cz^F) \]and the LHS has degree at most $mn - 1$ by cancellation. Note that all terms in $p(z^G, cz^F)$ remain distinct after substitution since $\gcd\{G, F\} = 1$. However, the RHS has at least degree $mn$ by considering the highest powers in $x$ for $p$ and $g$.

Let $m = \deg f$ and $n = \deg g$. Then set $$f(z^n) + g(cz^m) = p(z^n, cz^m)q(z^n, cz^m)$$with $c$ chosen such that the $x^{mn}$ term on the left has coefficient zero. We may assume $c=1$ without loss of generality. Now \begin{align*} \text{maxdeg}_z P = \text{max}(nx_p, my_p) \\ \text{maxdeg}_z Q = \text{max}(nx_q, my_q) \end{align*}where $x_p, x_q$ are the maximal degrees of $x$ in $p, q$, and $y_p, y_q$ are defined similarly. Because $x_p+x_q = m$ and $y_p+y_q = n$, $$\text{maxdeg}_z (PQ) \geq n(x_p+x_q) = mn,$$contradiction.