PROBLEM LINK:
Author: Dr. M Kaykobad
Tester: Jingbo Shang
Editorialist: Jingbo Shang
DIFFICULTY:
Easy – Medium
PREREQUISITES:
Fraction, Math
PROBLEM:
Given a clock system, determine how many good times are there in a time frame. A good time is that it will still be a valid time if we swap the positions of hour and minute arms.
EXPLANATION:
To solve this problem, we can calculate all tuples (h1, m1, h2, m2) such that h1:m1 is the time by swapping two arms of h2:m2.
It is important to observe that if we have known h1 and h2, we can have two equations to determine m1 and m2. Therefore, with fraction operations, we can get at most one solution (m1, m2) for some given h1 and h2. This means that there are at most O(H^2) good times.
With prepared all good times, it is easy to calculate how many of them are in the given time frame.
Another way is to derivate the equations further by hand. Then you will get a simpler expression such that you don’t need to implement fraction operations.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.