I admit that both of them could have been more interesting and less annoying (or at least I can do some edit to them), and even from the problem statement, anyone could tell.

But what I am trying to say is that I learned more from E and J than from any problem I did this year, so they are still the best. By the way, I think E was way more annoying than J, considering the amount of time I spent for both.

Some contestants found a O(Q*log^2) solution for E, which was quite nice :D

Let $$$x_i = c*d_i$$$ be the bandwidth allocated as denoted. We can do a binary search on $$$c$$$. For a fixed $$$c$$$, we can allocate bandwidth in the same manner as in the editorial (either $$$x_i$$$ itself or the closest valid value). Increase $$$c$$$ if we still have bandwidth to share, or decrease if we allocated too much bandwidth. Code

I have figured out it can be split in blocks. Using matrix exponential I can solve it with $$$O(p^3*logN)$$$, but I'm struggling with optimization.

Can you share a bit more?

Edit: My transfer used $$$O(p^3)$$$, which is unnecessary. I can simply merge two dp in $$$O(p^2)$$$!

Let's fix the painting of the top horizontal $$$C$$$ edges arbitrary.

In addition to this, let's fix the painting of the top leftmost edge arbitrary. Then, how many different paintings are there to color the top remaining $$$C$$$ vertical edges?

$$$3^{C}*(3 * 2 ^ {C})^{R} = 3^{R+C}* 2^{RC}$$$