Editorial for CCC '17 J4 - Favourite Times

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Phoenix1369

For 4 out of the 15 available marks (D \le 10^4), we can simply iterate over every possible time as displayed on the clock face and check if the digits form an arithmetic sequence, taking care to ignore the leading zero in the hour as required.

Time Complexity: \mathcal O(D)

For the full 15 marks, we make the observation the analog clock cycles through its faces in 12 hours, or 720 minutes, meaning we only need to compute the amount of times an arithmetic sequence is formed within the first 12 hours after 12:00 in the worst case. To obtain our answer, we can multiply the maximum number of times an arithmetic sequence is seen in the 12 hour interval by \lfloor \frac{D}{720} \rfloor and add the amount of time an arithmetic sequence is seen in the time left over.

Time Complexity: \mathcal O(1)


There are no comments at the moment.