Problem A.

Let’s call the monster dimension sizes as x₁, x₂, x₃.

1. O(min(k, x₁ + x₂ + x₃)) solution

We can make at most (x₁ – 1) + (x₂ – 1) + (x₃ – 1) cuttings, so we may assume that k <= x₁ + x₂ + x₃ – 3. For each of the three dimensions we will store an integer a_i – number of cuttings performed through the corresponding dimension. Let’s perform the following actions k times: consider all numbers a_i which we may increase (a_i <  x_i - 1) , call these dimensions “uncompleted”. Select the minimum number a_j among all uncompleted a_i and perform a cut through the corresponding dimension (a_j will be increased by 1 as the result). Now let’s consider the resulting set after k actions: {a₁, a₂, a₃}. Using the described algorithm we grant that the maximum element of this set is as little as possible and the minimum element is as big as possible. Because the sum a₁ + a₂ + a₃ = k is fixed, we get the maximum product (a₁ + 1) * (a₂ + 1) * (a₃ + 1) which is the answer for the problem.

2. O(1) solution

Instead of simulation all the k actions we may quickly determine values of numbers a_i after using the algorithm described above.

Let x – the smallest value among (x_i – 1). When x * 3 >= k on each of the algorithm iterations all three dimensions will be uncompleted. It means that during the first (k / 3) * 3 steps each of numbers a_i will be increased by (k / 3). Then 0, 1 or 2 numbers a_i will be increased by 1 subject to value of k % 3. So, we have found values a_i.

Otherwise (x * 3 < k) during the first x * 3 steps each of a_i will be increased by x. After that we will have at most two uncompleted dimensions which can be processed a similar way (we should choose the minimum value x among the remaining uncompleted dimensions).

Problem B.

We may assume that we have exactly n awarded places but some of them give 0 points.

Let’s sort places by amount of points (b_i) and racers by amount of currently gained points (a_i). First let’s find the best place Vasya can reach. In the best case he will get b₀ points (where b₀ is the greatest number among b_i). So, let the total Vasya’s point is v. Now we should to distribute other prize points to racers so that the number of racers better than Vasya will be minimal. For doing that we are to give maximum number of prizes so that corresponding racers will have less than v points. Note that if we can give k prizes keeping this property, than we can give k “cheapest” prizes too. The following statement is also true: if we can get a prize with t points to racer i and to racer j , a_i > a_j, then it is better to give this prize to racer i. Formally: if there exists a way to give k prizes where this prize will get racer j, than there exists a way to give k prizes where this prize will get racer i. It can be proven the following way. Consider a way to give k prizes where racer j got prize with t points, racer i – s points or didn’t get prize at all. In the first case we can swap prizes for racers i and j: a_i > a_j and a_i + s < v (since racer i have got the prize), so a_j + s < v, and a_i + t < v i.e. this change is acceptable. In the second case we can just give the prize t to racer i instead of racer j. In the both cases we get a way to give k prizes where racer i receive prize t.

Now including this statement we may give prizes to racers using the following greedy algorithm. Let’s begin to give prizes starting from the cheapest one and check the racers starting from the best one (of course excluding Vasya and the best prize). For each prize i we will go through the racers until applicable racer (j) found: b_i + a_j < v. If no such racers remain we are unable to give more prizes without violating the rule (racers should have less than v points). In this case we should stop the algorithm and the answer is n – k where k is the number of prizes we have given. If we have found such racer j we can give him prize b_i and go to the next prize. Complexity of this step is O(n).

Similarly we can find the worst place for Vasya. For doing that we should give him the cheapest prize (note it may have positive points though). After that we should distribute the prizes iterating over prizes from the largest to cheapest and check racers from the worst to the best one trying to make sum of racer’s points more than v.

Total complexity of the described algorithm is O(n * log(n)) because we have to sort prizes and racers.

Problem C.

It is easy to see that if we put some symbol c at position p of the string s it will not affect symbols at positions (p+2) and greater. So we have a standard DP problem. State of the dynamic is described by three parameters: p – the number of already processed symbols (or the index of currently processed symbol of the string), c – the previous symbol, t – the number of allowed symbol changes. To calculate the answer for a state we should choose the best value among all symbols for current position (when t > 0) or just go to the index (p + 1) with current symbol s[p]. Thus we get the followings formulas:

d[n][*][*] = 0

d[p][c][t] = d[p + 1][s[p]][t] + bonus[c][s[p]] when t = 0

d[p][c][t] = max(d[p + 1][c’][t – (c’ <> s[p])] + bonus[c][c’])

where n  is the length of string s.

Computation complexity of the algorithm is O(n * k * h^2), where h is the alphabet size (h = 26 for current problem).