I：There will be an optimal solution in which all the added numbers are in nonincreasing order. Use this to formulate an O(n²k) dynamic program and then optimize using divide and conquer trick or convex hull trick.

M: I'm unsure about the solution, but apparently it can be proven that you spend all your money on at most two people. Then some sort of ternary search should work.

M: Transform (c, h, p) to (h * C / c, p * C / c). The answer is a combination x1 * v1 (vi is (hi, pi)) + x2 * v2 + ..., you take that vector and take x*y. But that combination has other constraint, x1 + x2 + ... + xn == 1 and xi is in [0, 1] so it's a convex combination (https://en.wikipedia.org/wiki/Convex_combination). This means that you can take the convex hull and solve the problem for the vertices and edges and it will have the greatest answer.

We have reference solutions in C++ (and we also have some other AC in C++ from other contestants independently). I'm not sure why yours is failing.

dp[number of digits filled in][this number is k modulo m] or dp[n][k] can transition to dp[n+1][2*k] and dp[n+1][2*k+1]. dp[n][k] = (number of ways to get to this state from [0][0], sum of 1's of these ways). answer is dp[bits][0].second

Similar solution to tfg's Is dp[position of bit (from higher to lower)][number module n][how many ones i've put]. Base case is when pos =  =  - 1, if module is 0, return ones (third dimension). otherwise return 0. transifions is:

f(p, k, o) = f(p-1, (2^p + k)%n, o+1) + f(p-1, k, o)

It can be solved by DP. let's focus on minimum expected value, and then its similar for maximum. Be f(mask) = minimum expected value if I have the current mask (1 for available numbers, and 0 otherwise). So, the transition would some something like.

You have to calculate values of what numbers can I remove such that sum up d, and add that movement to moves[d]. There a few cases to handle, in case you can't make any movement, that will be the base case. Also you have to calculate the probabilitie of get d with 2 dice. For that just do a double nested loop and sum up for i+j, and then divide all (for 2 to 12) by 36.

Here is the code

E: You have to find the shortest cycle around cell having 'B'. For each cell, consider 2 nodes in the graph, P and Q. Also, consider a line from 'B' to an edge of the grid. For a particular cell, you are on node Q if you have crossed that line an odd number of times in your path. Otherwise, you are on node P. Now, calculate the shortest distance from P to Q for any cell.

problem E can be solved using max-flow(min-cut actually). Lets build the following flow network: for every position on the matrix lets create two nodes(call them entry node and exit node) and add an edge between them with capacity equal to the cost of blocking that position if it has a letter('a', 'b', ...) or INF in case it is the position of 'B' or a dot('.'). The source will be entry node of 'B' and the sink will be an extra node that we will connect with the exit nodes of every position on the borders with capacity equal to INF. Then for every position add an edge between its exit node and the entry nodes of every adjacent position with capacity equal to INF. Then run max-flow algorithm on this graph and that is the answer. What we are actually computing here is the minimum cost to separate the sink from the source(min-cut) which is equivalent to max-flow. The problem is similar to this one http://coj.uci.cu/24h/problem.xhtml?pid=2505 in case you want to practice this approach. Good luck

I assume that you mean your solution is $$$O(\max(a,b,c,d))$$$ and just iterates up to $$$10^7$$$, $$$10^9$$$ would TLE.

I never actually figured out why this worked, but during the contest I just observe that the inclusion exclusion only took on values of 0 or 1 and ran fast enough when I put the answers in a char array (but 2-4x slower in an int array)

You can also solve the problem in $$$O(n)$$$ with Möbius inversion and a linear-time sieve.