## DMOPC '15 October Solutions

By Jerry Zhang (cheesecake)

#### P1 - Itami and Manga

Sort the ratings in any order and the answer is the name that corresponds with the highest rating.

Time Complexity:

#### P2 - Itami and Squad

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.

Time Complexity:

#### P3 - Itami and Cipher

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.

#### P4 - Itami and Candy

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).

Time Complexity:

#### P5 - Lelei and Dragon Scales

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.

Time Complexity:

#### P6 - Lelei and Contest

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.

Time Complexity: