PROBLEM STATEMENT
The celebrated general Archibald Waving took charge of the fourth army in the occidental front.
After losing the first three armies, Waving has become obsessed with effective synchronization of
the army.
Whenever Waving needs to write the time at which military operations will be performed, he writes
only the
minute part of the time (the time also has an hour part, which Waving does not write down). This
strategy prevents the enemy from figuring out the exact times of the operations even if he
obtains the
schedule written by Archibald Waving. Of course, Waving's soldiers are very smart, so they are
able to
reconstruct the entire schedule from the minute parts alone.
A particular time can be written as AB:CD, where AB represents the hour part, and CD represents
the minute part.
The schedule is a list of times within the same day, where time can lie in the range from 00:00
to 23:59.
Moreover, the times appear in chronological order, i.e. the time of the operation performed
earlier
should be listed before the time of the operation performed later during the day. Also, no two
operations can be performed at the same time.
Waving wants to know if the enemy will be able to figure out anything from the schedule he has
written.
You are given a vector minuteValues representing minute parts of the times as written by
Waving.
An hour assignment can be represented by a vector whose i-th element is the hour part
corresponding to minuteValues[i]. The assignment is considered valid if and only if
the schedule obtained from the assignment follows the rules mentioned above. Help Waving by
returning the K-th (1-indexed) lexicographically smallest valid hour assignment. If there are
less than K valid hour assignments, return a vector containing single element -1 instead.
DEFINITION
Class:WeirdTimes
Method:hourValues
Parameters:vector , int
Returns:vector
Method signature:vector hourValues(vector minuteValues, int K)
NOTES
-vector X is lexicographically smaller than vector Y of the same size iff there exists
an index i such that X[j] = Y[j], j < i, and X[i] < Y[i].
CONSTRAINTS
-minuteValues will contain between 1 and 50 elements, inclusive.
-Each element of minuteValues will be between 0 and 59, inclusive.
-K will be between 1 and 1,000,000,000, inclusive.
EXAMPLES
0)
{22, 11, 33}
3
Returns: {0, 1, 3 }
The three lexicographically smallest valid hour assignments and the corresponding schedules
obtained from them are:
{0, 1, 1} ---> {00:22, 01:11, 01:33}
{0, 1, 2} ---> {00:22, 01:11, 02:33}
{0, 1, 3} ---> {00:22, 01:11, 03:33}
1)
{10}
2
Returns: {1 }
All possible schedules in lexicographically sorted order are
00:10, 01:10, 02:10, 03:10, 04:10, 05:10, 06:10, 07:10,
08:10, 09:10, 10:10, 11:10, 12:10, 13:10, 14:10, 15:10,
16:10, 17:10, 18:10, 19:10, 20:10, 21:10, 22:10, 23:10.
2)
{2, 1}
20
Returns: {0, 20 }
3)
{1, 2}
20
Returns: {0, 19 }
4)
{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 15, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}
1
Returns: {-1 }
In the list of minute parts, each next element is less than or equal to the previous one.
Operations must follow in chronological order and no two operations can be performed at the same
time, so no two listed operations can happen within the same hour. There are 25 elements in the
list, but a single day consists of just 24 hours, therefore there are no valid hour assignments.
5)
{45, 12, 0, 3, 2, 7, 4, 9, 23, 6, 17, 33}
12345
Returns: {0, 1, 2, 2, 3, 3, 4, 5, 12, 13, 18, 18 }
6)
{43, 58}
318
Returns: {-1 }
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any
unauthorized use or reproduction of this information without the prior written consent of
TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.