TopCoder problem "SuperWatch" used in TCO08 Round 3 (Division I Level Three)

Problem Statement


Year 3001. Your company needs to know if new model of watch is precise enough, so you need to run a small experiment. You'll take several watches, set them to "00:00", wait for a couple of years and then compute the watch imprecision which is equal to the largest difference between the two times shown on the watches. For example, if you've taken four watches and at the end of the experiment they've shown "11:11", "10:59", "11:02" and "11:13", then the biggest difference is 14 minutes (between "11:13" and "10:59").

To make the experiment a bit more interesting you've decided to give the watches to volunteers living in different time zones. The time zones have positive 0-based indices, so time zone number K is K hours ahead of yours. For example, 2:15 in your zone, 4:15 in zone 2 and 8:15 in zone 6 are the same moment of time. The watches of the volunteers were set according to the time zones they are from, so the watch for the volunteer from time zone X was set to X hours zero minutes at the beginning of the experiment. Before the start of the experiment you wrote down the time zones your volunteers are from, and at the end of the experiment each of the volunteers recorded the time shown on his watch. Unfortunately, you messed up the order of the records, so now you do not know which time zone corresponds to which volunteer. You are optimistic so you want to find the minimal possible imprecision under given data. Please note that the watches does not show date, so, for example, the difference between "23:50" and "00:10" can be only 20 minutes (or 23 hours and 40 minutes, if needed).

You will be given a String[] times, giving you the times recorded by volunteers. Each element of times is formatted as "HH:MM" (quotes for clarity), where HH is an hour between 00 and 23 and MM is a minute between 00 and 59. You will be also given a int[] zones, giving you the time zones for the volunteers. You are to assign each time zone to exactly one volunteer and return the minimal watch imprecision in minutes.



Parameters:String[], int[]
Method signature:int smallestImprecision(String[] times, int[] zones)
(be sure your method is public)


-times will contain between 2 and 40 elements, inclusive.
-zones will contain the same number of elements as times.
-Each element of times will be formatted as "HH:MM", where HH is a 2-digit integer between 00 and 23, inclusive, and MM is a 2-digit integer between 00 and 59, inclusive.
-Each element of zones will be between 0 and 23, inclusive.


{"16:11", "15:59", "16:02", "16:13"}
{5, 5, 5, 5}
Returns: 14
The example from the problem statement, but all watches got a 5 hours time shift.
{"12:11", "13:59", "19:02", "18:13"}
{1, 3, 7, 8}
Returns: 14
Assign zone 1 to watch 1, zone 3 to watch 2, zone 7 to watch 4 and zone 8 to watch 3 to achieve the same imprecision of 14 minutes.
{"23:59", "00:02", "12:00", "08:01"}
{0, 0, 8, 12}
Returns: 3
It is near midnight now. The first two watches are in your zone, while the third and the fourth are offset by 12 and 8 hours, respectively.
{"13:23", "11:54", "00:03", "22:22", "10:38"}
{1, 4, 13, 21, 13}
Returns: 256
{ "00:00", "08:00", "16:00" }
{ 0, 0, 0 }
Returns: 960

Problem url:

Problem stats url:




PabloGilberto , legakis , ivan_metelsky

Problem categories:

Graph Theory