# Number Theory Problem from Local Selection Contest EPFL | ETHZ

This was a question from the 2016 local (selection) contest in ETHZ, You have a high-precision alarm clock with three operations:

1) reset wake-up time to midnight (00:00:00.000000)

2) modify the wake-up time by  ± 1 microsecond (wrapping around at midnight).

You know your wake-up time ("hh:mm:ss.yyyyyy") for the next N consecutive days and want to modify the wake-up time accordingly. Any number of the above two operations can be executed at an arbitrary instant in time, at or after the start of day one.

Pressing the same button a million times can be quite frustrating. You came up with the following idea to reduce the number of button presses: Exactly 24h before day one, the alarm clock is unplugged, which makes the timer pause. You can plug it in again at a real-world time t0 chosen by you to resume the timer. Select this time such as to minimize the total number of operations required to ensure the clock rings at the correct time on each day. If there are multiple choices for t0, take the smallest one.

Input: The first lines contains a single number N, with 1 ≤ N ≤ 10^5. The following N lines contain the wake-up times in the form "hh:mm:ss.yyyyyy" (the letters standing for hours, minutes, seconds, microsecond respectively). It is guaranteed that the seconds and minutes do not exceed 59 and the hours do not exceed 23. In case the numbers can be written using less characters, they will have leading zeros.

Output: On the first line, print the number of operations (it is guaranteed that this numbers will be smaller than 10^18). On the second line, print the time t0 in the format "hh:mm:ss.yyyyyy".

The approach I tried was to formulate the problem as follows (any difference of times is assumed to be taken modulo 24):

1) We are given the timer is stopped at the start of day 0. Thus during day 0 (i.e. before start of day 1) the timer is resumed at some time $$x$$ (that is at time $$x$$, the timer displays 00:00:00.000000). Hence if for a given day $$i$$, the wake-up time is $$w_i$$ then the alarm should be set to $$w_i - x$$

2) The cost of setting timer for first wake up time necessarily includes the operation of resetting wake-up time to midnight and then increasing wake-up time (if $$w_1-x$$ happens to be AM) or otherwise decreasing if the wake-up time is PM.

3) For the other days $$j$$ the wake-up time is minimum of setting alarm to time $$w_j - x$$ starting from midnight and setting the alarm by increasing or decreasing from wake-up time of day before. So $$min(w_j-x, w_j-w_{j-1})$$

However I do not know of an algorithm, greedy or number theoretic, which can solve this problem.

• Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources!
– Evil
Feb 3 '19 at 2:26
• Please credit the original source of this problem. Also, is it from a live contest? Is the contest still running?
– D.W.
Feb 3 '19 at 2:52
• @AMRO It is relevant to know whether that the contest has finished, as most people would rather not help some cheat in an ongoing contest. If the contest is finished, there is no problem, of course. A more precise source for the contest than only the university that made it would also help us see that. Feb 3 '19 at 13:26
The solution will be one of the alarm times so a solution would be to sort the times by increasing order and the earliest time that gives the minimum would be the solution. The proof is simple: Suppose the optimal time, $$x=t_0$$, is not one of the alarm times. Further imagine a number line (or segment) spanning from 00:00:00.000 000 up to 23:59:59.999 999 now plot the points representing the wake up times. Clearly selecting time $$x$$ as the optimal choice will shift the points to the left by $$x$$ (if a point happens to hit left-most border of this segment then it will wrap around so it will end up at the right-most border). Now suppose there are $$s$$ points that we reach by resetting i.e. by starting from 00:00:00.000 000 (midnight) relative to alarm time not real time. Of these points $$r$$ will be by increasing time from midnight and $$l$$ by decreasing time from midnight. Suppose $$l>r$$ (the other case is identical) so there are more points to which we decrease from midnight to, and graphically this would correspond to starting from the right-most border of the interval and going left to the desired points. Clearly, if we shift all points to the right so that the right-most of these points coincides with right-most border then we have gained a net advantage since we have decreased all the distance to the $$l$$ points by some constant, $$c$$, but increased distances to $$r$$ points by the same constant $$c$$ but since $$l>r$$ we have a net decrease of $$(l-r)c$$.