## 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:

## Comments

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?

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

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

15 edits, wow.

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