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

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

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: \mathcal{O}(G \times 2^N)

P4 - Great Sequence

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

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

P5 - Scribe

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

Time Complexity: \mathcal{O}(T \log_{10} y)

P6 - Alarms

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

Time Complexity: \mathcal{O}(N! \times N! \times N^2)

Comments


  • 2
    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?


  • 2
    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?


    • 0
      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)\)


      • 2
        r3mark
         commented on Jan. 13, 2016

        15 edits, wow.


        • 2
          d
           commented on Jan. 13, 2016

          \mathcal{The}\ math\ format\ decided\ to\ be\ annoying.


      • 1
        cheesecake
         commented on Jan. 13, 2016

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