For B, the recurrence relation has closed form

so you can just precompute primes up to 10^8 + 7 and then check for each n if both 5n + 6 and kn + 7 are primes.

I is half-plane intersection. You binary search on the distance, and for a given distance d, you move each of the line segments forming your polygon in by d, and check if there still exists a convex polygon.

Not sure if this is surprising or not, but I had no issues with the standard DFS-based matching, which I think is $$$O(V E^2)$$$ in worst case, but difficult to come up with test cases for. Some discussion here: https://codeforces.me/blog/entry/58048?#comment-417398

You have the right idea, but I think you aren't implementing the check for "all non-isolated nodes are in a single component" correctly. You start the search from node 0, but what if 0 is itself isolated and not part of the component?

You actually don't 'technically' need to precompute: If you modify your code to step your shift up from 1 while you've found no solutions it passes in 0.57s. I also have no idea how to prove an upper bound; I expect that most solves didn't prove one but instead relied on a guess and check to solve.

D: For all $$$n>25$$$ we can find a solution with $$$k\le 3.$$$ Suppose that we fix the number of bits in each of the $$$k$$$ numbers $$$a_1,\ldots,a_k$$$, we can do dynamic programming where the states are determined by

• $$$idx:$$$ the current bit of $$$N$$$ (iterate from $$$60$$$ down to $$$0$$$)
• $$$carry:$$$ the carry from the previous bit of $$$N$$$
• $$$b_1, \ldots, b_k:$$$ the number of bits which each of the $$$k$$$ numbers needs (in order to make each one equinumerous)

You can do transitions based on whether $$$a_1,\ldots,a_k$$$ have $$$1$$$ or $$$0$$$ in the $$$idx-1$$$'th bit.

Jason Yuen's Code

M: Let $$$num$$$ be the final number of piles, and let $$$sum$$$ be the total number of crates. For all possible values of $$$num$$$ you can calculate the needed number of moves in linear time. Let $$$v_i$$$ be the number of crates in the $$$i$$$-th pile initially. In total, we must do $$$ans=\sum_{i=1}^{num}\left |b_i-sum/num\right |$$$ pickups and dropoffs in total.

Now we need to deal with the moves in between stacks. Let $$$l_i$$$, $$$r_i$$$ be the # of moves from stack $$$i+1$$$ to $$$i$$$ and stack $$$i$$$ to $$$i+1,$$$ respectively. We can get a lower bound on $$$l_i$$$ or $$$r_i$$$ based on how many crates we need to move between $$$i$$$ and $$$i+1.$$$ After doing this, we should increment each $$$l_i$$$ or $$$r_i$$$ until $$$0\le r_i-l_i\le 1$$$ and $$$r_i-l_i\ge r_{i+1}-l_{i+1}$$$ for all $$$i.$$$ Also, if $$$r_j>0,$$$ then for all $$$0\le k<j$$$ we must have $$$r_k>0.$$$

After calculating all the $$$l_i,r_i,$$$ we can add them to $$$ans$$$ to get the result. If $$$sum$$$ is large we might not have enough time to calculate these values when $$$N<i\le num,$$$ but we can do these separately.

Code