DMOPC '15 October Solutions
By Jerry Zhang (cheesecake)
Sort the ratings in any order and the answer is the name that corresponds with the highest rating.
To simulate each squad leader picking the best available soldier, sort the strengths of the soldiers in non-increasing order. We then iterate through the array starting with soldier (in a -index array) and increment by , adding their respective strengths will result in the maximum strength of Itami's squad.
As mentioned in the problem statement, there are only possible shifts . Knowing this, we can simply search for string in every single shift of string in increasing order and output the first viable shift.
Time Complexity: , proof is left as an exercise for the reader.
We can precompute all primes up to with Sieve of Eratosthenes. For each prime, we have two cases: Tuka takes either or candy. For each case, the number of ways we can give candies to Rory is the remaining number of candies (integer division).
Using a 2-D prefix sum array, we can calculate the total number of scales in any rectangle in . For a rectangle with its top left corner at and its bottom right corner at , we can use inclusion-exclusion to see that the total number of scales = . Brute forcing all possible rectangles gives us a solution, which will give us of the points. To get , we need to make the insight that since all cells have a non-negative number of scales, we only need to consider the number of scales in the rectangle with maximum length with each possible width.
The simplest solution here is segment tree with lazy propagation. Operation 1 is the classical range update. Operation 2 requires a little more mathematical insight. Using Fermat's Little Theorem and binomial expansion via Pascal's Triangle, we can see that for all values given in the constraints, . The operation then becomes a simple range sum query.