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: \mathcal{O}(NlogN)

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 R-1 (in a 0-index array) and increment by L, adding their respective strengths will result in the maximum strength of Itami's squad.

Time Complexity: \mathcal{O}(NlogN)

P3 - Itami and Cipher

As mentioned in the problem statement, there are only 26 possible shifts (0 \le shift \le 25). Knowing this, we can simply search for string T in every single shift of string S in increasing order and output the first viable shift.

Time Complexity: \mathcal{O}(|S| \times |T|), proof is left as an exercise for the reader.

P4 - Itami and Candy

We can precompute all primes up to N with Sieve of Eratosthenes. For each prime, we have two cases: Tuka takes either 0 or 1 candy. For each case, the number of ways we can give candies to Rory is the remaining number of candies/X + 1 (integer division).

Time Complexity: \mathcal{O}(NlogN)

P5 - Lelei and Dragon Scales

Using a 2-D prefix sum array, we can calculate the total number of scales in any rectangle in \mathcal{O}(1). For a rectangle with its top left corner at (a,b) and its bottom right corner at (c,d), we can use inclusion-exclusion to see that the total number of scales = prefix[c][d] - prefix[a][d] - prefix[c][b] + prefix[a][b]. Brute forcing all possible rectangles gives us a \mathcal{O}(W^2 \times H^2) solution, which will give us 50\% of the points. To get 100\%, 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: \mathcal{O}(W \times H \times \min(W,H))

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 M values given in the constraints, (a_1^M + a_2^M + ... + a_n^M) \mod M \equiv (a_1 + a_2 + ... + a_n) \mod M. The operation then becomes a simple range sum query.

Time Complexity: \mathcal{O}((N+Q)logN)


There are no comments at the moment.