## DMOPC '15 January Solutions

#### P1 - Dictionary

Split the words into buckets based on their starting letter, then sort each bucket lexicographically. Most languages have a built-in sorter, so just check if the first letter of adjacent elements are the same.

Time Complexity:

#### P2 - The Big Clock

Simple math. Add the passed time to the minutes, take minute modulo 60, update the hour, then modulo hour by 24.

Time Complexity:

#### P3 - Lethal

Brute force. You can use bitmasks to iterate over all possible combinations where 0 is attacking the taunt minion and 1 is attacking player, then check if there is sufficient attack power for each combination.

Time Complexity:

#### P4 - Great Sequence

We use prefix sum to check whether the subarray's sum is greater than . For and , you can use a balanced binary search tree or simply binary search for their occurrences in a precomputed list.

Time Complexity:

#### P5 - Scribe

An easy approach is to count the occurrences of 0-9 at each digit for and separately, then subtract to get the answer.

Time Complexity:

#### P6 - Alarms

Brute force all possible configurations of placing alarms and check if they're valid.

Time Complexity:

• r3mark
commented on Jan. 15, 2016
Question

How can you tell if a question should be brute forced or not? I guess you can calculate the time complexity and check if it would pass or not, but how can you tell whether or not there is another, easier to code solution?

• fifiman
commented on Jan. 13, 2016
P5 Scribe

Can I get a better explanation for finding the number of digits x from 1 to y?

• d
commented on Jan. 13, 2016 edit 15

Same, how do I get a faster runtime than $$O(T\*(log_{10}\ max(y))\*(number\ of\ distinct\ digits\ in\ decimal\ system)^2)$$

• r3mark
commented on Jan. 13, 2016

15 edits, wow.

• d
commented on Jan. 13, 2016

• cheesecake
commented on Jan. 13, 2016

Sorry about that, I rushed too much writing the editorial, you're right.