Codility
You are given N round clocks.
Every clock has M hands, and these hands can point to positions 1, 2, 3, ..., P (yes, these represent numbers around each face). The clocks are represented by the matrix A consisting of N rows and M columns of integers. The first row represents the hands of the first clock, and so on.
For example, you are given matrix A consisting of five rows and two columns, and P = 4:
A[0][0] = 1 A[0][1] = 2 A[1][0] = 2 A[1][1] = 4 A[2][0] = 4 A[2][1] = 3 A[3][0] = 2 A[3][1] = 3 A[4][0] = 1 A[4][1] = 3
You can rotate the clocks to obtain several clocks that look identical. For example, if you rotate the third, fourth and fifth clocks you can obtain the following clocks:
After rotation, the first, third and fourth clocks look the same, and the second clock looks the same as the fifth one. That means there are four pairs of clocks that look the same: (1, 3), (1, 4), (2, 5) and (3, 4).
Write a function:
For example, given the following array A and P = 4:
A[0][0] = 1 A[0][1] = 2 A[1][0] = 2 A[1][1] = 4 A[2][0] = 4 A[2][1] = 3 A[3][0] = 2 A[3][1] = 3 A[4][0] = 1 A[4][1] = 3
the function should return 4, as explained above.
Assume that:
With this approach, the time complexity is O(N · M ·(log M + log N)). This solution should
achieve the maximum number of points.
At the very beginning, I found this task is very similar with the string rotation question in CTCI. And I did transfer this question into a string rotation one. The string rotation solution worked, and gave the right answer. But I could only get 95/100, because of the TIMEOUT ERROR in the large_constantSpace test set.
https://github.com/linjiyuan90/OJ_Code/blob/master/codility/challenges/Clocks.cc
https://github.com/xiongjunliang/codility/blob/master/lithium2013/clock.cpp
Read full article from Codility
You are given N round clocks.
Every clock has M hands, and these hands can point to positions 1, 2, 3, ..., P (yes, these represent numbers around each face). The clocks are represented by the matrix A consisting of N rows and M columns of integers. The first row represents the hands of the first clock, and so on.
For example, you are given matrix A consisting of five rows and two columns, and P = 4:
A[0][0] = 1 A[0][1] = 2 A[1][0] = 2 A[1][1] = 4 A[2][0] = 4 A[2][1] = 3 A[3][0] = 2 A[3][1] = 3 A[4][0] = 1 A[4][1] = 3
You can rotate the clocks to obtain several clocks that look identical. For example, if you rotate the third, fourth and fifth clocks you can obtain the following clocks:
After rotation, the first, third and fourth clocks look the same, and the second clock looks the same as the fifth one. That means there are four pairs of clocks that look the same: (1, 3), (1, 4), (2, 5) and (3, 4).
Write a function:
that, given a zero-indexed matrix A consisting of N rows and M columns of integers and integer P, returns the maximal number of pairs of clocks that can look the same after rotation.class Solution { public int solution(int[][] A, int P); }
For example, given the following array A and P = 4:
A[0][0] = 1 A[0][1] = 2 A[1][0] = 2 A[1][1] = 4 A[2][0] = 4 A[2][1] = 3 A[3][0] = 2 A[3][1] = 3 A[4][0] = 1 A[4][1] = 3
the function should return 4, as explained above.
Assume that:
Complexity:
- N and M are integers within the range [1..500];
- P is an integer within the range [1..1,000,000,000];
- each element of matrix A is an integer within the range [1..P];
- the elements of each row of matrix A are all distinct.
- expected worst-case time complexity is O(N*M*log(N+M));
- expected worst-case space complexity is O(N*M).
Brute-force solution
For every pair of clocks, we will check whether they can look identical or not. Let’s sort the
hands of each clock. After that, we can easily count the distances between consecutive hands.
Two clocks look identical if the first hands are aligned and the consecutive distances between
hands are the same. When we rotate a clock, some other hand can become the first one. So
to check whether two clocks can be rotated to look identically, we have to check every cyclic
rotation of the distances between consecutive hands.
Here is a program comparing all the pairs of clocks and checking whether they can be
rotated so that they look identically. Assume that matrix A contains distances between
consecutive hands.
However, the solution is inefficient. We have O(N^2
) pairs of clocks, and every pair is
compared in O(M2
) time, so the whole algorithm may require O(N^2
· M^2
) time.
1 def clocks(A):
2
N = len(A)
3 M = len(A[0])
4
result = 0
5
for i in xrange(N):
6
for k in xrange(i + 1, N):
7
for l in xrange(M):
8
|
ok = True
|
9
|
for j in xrange(M):
|
10
|
if (A[i][j] != A[k][(j + l) % M]):
|
11
|
ok = False
|
12
|
break;
|
13
|
if ok:
|
14
|
result += 1
|
15
|
break;
|
16
|
return result
|
Slow solution
To find a
better solution, we should be able to compare two clocks faster than in O(M2) time. There is a suitable algorithm
called lexicographically minimal string rotation. For each clock, we find its
canonical rotation. If two clocks can be rotated so that look identically,
their canonical rotations should be identical. For this purpose we can choose
such a rotation of distances between consecutive hands that is minimal in the
lexicographical order. Finding the minimal rotation of a clock requires O(M)
time, so the time complexity of the whole algorithm is O(N2 · M
+ N · M log M).
2: Slow
solution.
1 def clocks(A):
2
N =
len(A)
3
M =
len(A[0])
4
for i in xrange(N):
5 minimal_lexicographically_rotation(A[i])
6
result = 0
7
for i in xrange(N):
8
for k in xrange(i + 1, N):
9
ok = True
|
10
|
for j in xrange(M):
|
|
11
|
if (A[i][j] != A[k][j]):
|
|
12
|
ok = False
|
|
13
|
break;
|
|
14
|
if ok:
|
|
15
|
result += 1
|
|
16
|
return result
|
Optimal solution
We can find an even faster
solution to this task by simply sorting the clocks in the order of their
lexicographically minimal rotations. That will cause identical clocks to be
adjacent to each other in the array. Assume that matrix A contains distances between consecutive hands.
1 def clocks(A):
2
N = len(A)
3
for i in xrange(N):
4
minimal_lexicographically_rotation(A[i])
5
A.sort()
6 result = 0
7
pairs = 0
8
for i in xrange(1, N):
9
if (equal(A[i], A[i - 1])):
10
pairs += 1
11
result += pairs
12
else:
13
pairs = 0
14
return result
With this approach, the
time complexity is O(N · M
· (log M + log N)). This solution should achieve the maximum number of points.
Alternative solution
We can also solve this task in alternative
way. Instead of looking for lexicographically minimal rotations, we can find
the rotation in which we get the maximal (or minimal) hash. If the maximal hash
for two clocks is the same, we claim that the two clocks look identical.
Finally,
just sort the clocks by their maximal hashes and identical clocks will also be
next to each other. The time complexity is O(N · M
· log M + N · log N).
http://codesays.com/2014/solution-to-lithium2013-clocks-by-codility/At the very beginning, I found this task is very similar with the string rotation question in CTCI. And I did transfer this question into a string rotation one. The string rotation solution worked, and gave the right answer. But I could only get 95/100, because of the TIMEOUT ERROR in the large_constantSpace test set.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
def solution(A, P):
columns = len(A[0])
same_after_rotation = {}
for row_index in xrange(len(A)):
A[row_index].sort()
signature = "-".join([str((A[row_index][column_index] -
A[row_index][column_index-1]) % P)
for column_index in xrange(columns)])
for sig, count in same_after_rotation.items():
if signature in sig:
same_after_rotation[sig] += 1
break
else:
same_after_rotation[signature+"-"+signature] = 1
same_pairs = sum([item*(item-1)/2 for item in same_after_rotation.values()])
return same_pairs
|
https://github.com/linjiyuan90/OJ_Code/blob/master/codility/challenges/Clocks.cc
https://github.com/xiongjunliang/codility/blob/master/lithium2013/clock.cpp
Read full article from Codility
