Problem D is a bit difficult for me, and the editorial just says "construct it like this" and then gives a construction and code. However, I'm having trouble understanding exactly how it works and how one would come up with it. Is this really just an ad-hoc problem? I'm more inclined to believe that it's because "No self-respecting architect leaves the scaffolding in place after completing his building" which led the editorial to omit the problem proposer's thought process. Could someone share how they arrived at the idea? Thanks.

Beautiful simple solution for C from power series: $$$x^a + y^a + x^{-a} + y^{-a} = (x^a+y^a)(1 + (xy)^{-a})$$$, we want the term with $$$x^0 y^0$$$ in the product where $$$a = P_i$$$. Since the second bracket has the same coefficients of $$$x$$$ and $$$y$$$ in each term, the first bracket's product also needs that, and the sum of coefficients is always $$$S = \sum P_i$$$ so those have to be $$$x^{S/2} y^{S/2}$$$, and for the second bracket's product it also has to be $$$(xy)^{-S/2}$$$. Both are the same and calculated using knapsack.

Am I the only one who finds C very difficult (for 600pts level)?