G can be solved by finding a partition s.t. every vertex has more neighbours in other part than in its part. This can be done by iteratively taking a vertex that does not satisfy this condition and moving it to the other part. The number of inner edges decreases and thus this process converges.

G: If you can find a cycle of even size in every connected component, you can keep a tree with 1 edge added such that the only cycle in the result will be that even cycle, so the graph will obviously be bipartite. To find a cycle of even size, find a maximal path. Because it's maximal, all 3 of the endpoints' neighbours will be on the path; one will obviously be right next to it on the path, one will be $$$a$$$ edges away and one will be $$$b$$$ edges away. If $$$a$$$ is odd, you found an obvious even cycle. If $$$b$$$ is odd, you found an obvious even cycle. If $$$a$$$ and $$$b$$$ are even, you can make an even cycle of the path between those 2 neighbours and the original endpoint.

M: Make a graph with edges $$$x$$$ -> $$$(x+c_i)$$$ $$$mod$$$ $$$c_0$$$ with cost $$$c_i$$$, now the answer is (the maximum distance from $$$0$$$ to any other node)-$$$c_0$$$. You don't have to run dijkstra with $$$n \cdot c_0$$$ edges for each query; you can keep the distances from the previous iteration of dijkstra and just use the edges using the new $$$c_i$$$ because the order in which the $$$c_i$$$ are added doesn't matter, so you can answer each query in $$$O(c_0$$$ $$$log$$$ $$$c_0)$$$.

Thank you!

Let dp[i][j] be the minimum amount of money required for the first $$$i$$$ days if the $$$j$$$-th student wasn't working on the $$$i$$$-th day, and let pref[i][j] be the prefix sum by rows of $$$c$$$. If dp2[i][j] is the minimum amount of money required for the first $$$i$$$ days if the $$$j$$$-th student was working on the $$$i$$$-th day, then dp2[i][j] is the minimum from $$$k=i-a_j$$$ to $$$k=i-1$$$ of dp[k][j]+pref[j][i]-pref[j][k]. You can separate pref[j][i] from dp[k][j]-pref[j][k] and minimizing dp[k][j]-pref[j][k] can easily be done using one monotonic queue for each $$$j$$$. dp can easily be computed from dp2.

Come to think of it, top-to-bottom version of this is significantly easier: start from $$$dp[1][0][0] = 1$$$, and successively choose how many copies of $$$h$$$ will be decomposed into $$$h - 1, h - 2$$$.

We integrated numerically over $$$z$$$; within a plane, we used black-box halfplane intersection and circle-polygon intersection, both from KACTL.

We found that surprisingly, you only need to take $$$z$$$ in increments of $$$0.01$$$ ($$$10^{-2}$$$) in order to have enough precision to pass all tests.

For C, you can do a single BFS from the target state, so you shouldn't have to repeat it for each number/each testcase.

For C there are only $$$\binom{25}{5} \approx 53000$$$ useful states, so naive implementation (each state takes $$$5^2$$$) should be enough for the time limit, no need to struggle on bitwise operation. The key point is to do BFS only once.

For A, I think you can just you can just make the figure compact and see that the number of sides shared by two cells does not decrease: suppose all cells have positive coordinates $$$(x, y)$$$ and you first keep moving all cells downward (i.e. along $$$y$$$-axis) as long as cells have positive coordinates and no two cells coincide. Then you do the same thing but along $$$x$$$-axis. You can see the figure then has the shape of Young tableau.

This gives you the maximal perimeter you can achieve while the area is fixed. And the perimeter is equal to the perimeter of the bounding box of the figure. It is also easy to see that you can achieve any perimeter (which has to be even) between the lower bound shown above and the trivial upper bound (by moving one cell to the border and thus making bounding box larger).