Tasks Details
hard
1.
Clocks
Find the maximal number of clocks with hands that look identical when rotated.
Task Score
90%
Correctness
Not assessed
Performance
Not assessed
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:
int solution(int **A, int N, int M, int P);
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.
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] = 3the function should return 4, as explained above.
Write an efficient algorithm for the following assumptions:
- 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.
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used C
Time spent on task 60 minutes
Notes
not defined yet
Task timeline
Code: 13:57:04 UTC,
c,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869
int compare_ints (int a, int b) { return a - b ; }
int compare_clocks_M;
int compare_clocks (const int * a, const int * b)
{
int i;
for (i = 0 ; i != compare_clocks_M ; i++)
{
if (a[i] != b[i]) return a[i] - b[i];
}
return 0;
}
int solution(int **clocks, int num_clocks, int num_hands, int positions)
{
int c;
int pairs = 0; // the result
int repeat = 0; // clock signature repetition counter
// put all clocks in canonical position
for (c = 0 ; c != num_clocks ; c++)
{
int i;
unsigned s_min = (unsigned)-1, o_min;
int * clock = clocks[c];
for (i = 0 ; i != num_hands ; i++)
{
// signature of positions with current hand rotated to 0
int j;
unsigned offset = positions - clock[i];
unsigned signature = 0;
for (j = 0 ; j != num_hands ; j++)
{
signature += (clock[j] + offset) % positions;
}
// retain position with minimal signature
if (signature < s_min)
{
s_min = signature;
o_min = offset;
}
}
// put clock in its canonical position
for (i = 0 ; i != num_hands ; i++)
{
clock[i] = (clock[i] + offset) % positions;
}
qsort (clock, hands, sizeof(int), compare_ints);
}
// sort clocks
compare_clocks_M = num_hands;
qsort (clocks, num_clocks, sizeof(*clocks), compare_clocks);
// count duplicates
repeat = 0;
for (c = 1 ; c != num_clocks ; c++)
{
if (compare_clocks (&clocks[c-1], &clocks[c]))
{
pairs += ++repeat;
}
else repeat = 0;
}
return pairs;
}
Analysis
Compile error
In file included from user.c:23: func.c: In function 'solution': func.c:48: error: 'offset' undeclared (first use in this function) func.c:48: error: (Each undeclared identifier is reported only once func.c:48: error: for each function it appears in.) func.c:50: error: 'hands' undeclared (first use in this function) func.c:50: warning: passing argument 4 of 'qsort' from incompatible pointer type /usr/include/stdlib.h:756: note: expected '__compar_fn_t' but argument is of type 'int (*)(int, int)' func.c:55: warning: passing argument 4 of 'qsort' from incompatible pointer type /usr/include/stdlib.h:756: note: expected '__compar_fn_t' but argument is of type 'int (*)(const int *, const int *)' func.c:61: warning: passing argument 1 of 'compare_clocks' from incompatible pointer type func.c:4: note: expected 'const int *' but argument is of type 'int **' func.c:61: warning: passing argument 2 of 'compare_clocks' from incompatible pointer type func.c:4: note: expected 'const int *' but argument is of type 'int **'
Code: 13:57:32 UTC,
c,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869
int compare_ints (int a, int b) { return a - b ; }
int compare_clocks_M;
int compare_clocks (const int * a, const int * b)
{
int i;
for (i = 0 ; i != compare_clocks_M ; i++)
{
if (a[i] != b[i]) return a[i] - b[i];
}
return 0;
}
int solution(int **clocks, int num_clocks, int num_hands, int positions)
{
int c;
int pairs = 0; // the result
int repeat = 0; // clock signature repetition counter
// put all clocks in canonical position
for (c = 0 ; c != num_clocks ; c++)
{
int i;
unsigned s_min = (unsigned)-1, o_min;
int * clock = clocks[c];
for (i = 0 ; i != num_hands ; i++)
{
// signature of positions with current hand rotated to 0
int j;
unsigned offset = positions - clock[i];
unsigned signature = 0;
for (j = 0 ; j != num_hands ; j++)
{
signature += (clock[j] + offset) % positions;
}
// retain position with minimal signature
if (signature < s_min)
{
s_min = signature;
o_min = offset;
}
}
// put clock in its canonical position
for (i = 0 ; i != num_hands ; i++)
{
clock[i] = (clock[i] + o_min) % positions;
}
qsort (clock, hands, sizeof(int), compare_ints);
}
// sort clocks
compare_clocks_M = num_hands;
qsort (clocks, num_clocks, sizeof(*clocks), compare_clocks);
// count duplicates
repeat = 0;
for (c = 1 ; c != num_clocks ; c++)
{
if (compare_clocks (&clocks[c-1], &clocks[c]))
{
pairs += ++repeat;
}
else repeat = 0;
}
return pairs;
}
Analysis
Compile error
In file included from user.c:23: func.c: In function 'solution': func.c:50: error: 'hands' undeclared (first use in this function) func.c:50: error: (Each undeclared identifier is reported only once func.c:50: error: for each function it appears in.) func.c:50: warning: passing argument 4 of 'qsort' from incompatible pointer type /usr/include/stdlib.h:756: note: expected '__compar_fn_t' but argument is of type 'int (*)(int, int)' func.c:55: warning: passing argument 4 of 'qsort' from incompatible pointer type /usr/include/stdlib.h:756: note: expected '__compar_fn_t' but argument is of type 'int (*)(const int *, const int *)' func.c:61: warning: passing argument 1 of 'compare_clocks' from incompatible pointer type func.c:4: note: expected 'const int *' but argument is of type 'int **' func.c:61: warning: passing argument 2 of 'compare_clocks' from incompatible pointer type func.c:4: note: expected 'const int *' but argument is of type 'int **'
Code: 13:57:55 UTC,
c,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869
int compare_ints (int a, int b) { return a - b ; }
int compare_clocks_M;
int compare_clocks (const int * a, const int * b)
{
int i;
for (i = 0 ; i != compare_clocks_M ; i++)
{
if (a[i] != b[i]) return a[i] - b[i];
}
return 0;
}
int solution(int **clocks, int num_clocks, int num_hands, int positions)
{
int c;
int pairs = 0; // the result
int repeat = 0; // clock signature repetition counter
// put all clocks in canonical position
for (c = 0 ; c != num_clocks ; c++)
{
int i;
unsigned s_min = (unsigned)-1, o_min;
int * clock = clocks[c];
for (i = 0 ; i != num_hands ; i++)
{
// signature of positions with current hand rotated to 0
int j;
unsigned offset = positions - clock[i];
unsigned signature = 0;
for (j = 0 ; j != num_hands ; j++)
{
signature += (clock[j] + offset) % positions;
}
// retain position with minimal signature
if (signature < s_min)
{
s_min = signature;
o_min = offset;
}
}
// put clock in its canonical position
for (i = 0 ; i != num_hands ; i++)
{
clock[i] = (clock[i] + o_min) % positions;
}
qsort (clock, num_hands, sizeof(int), compare_ints);
}
// sort clocks
compare_clocks_M = num_hands;
qsort (clocks, num_clocks, sizeof(*clocks), compare_clocks);
// count duplicates
repeat = 0;
for (c = 1 ; c != num_clocks ; c++)
{
if (compare_clocks (&clocks[c-1], &clocks[c]))
{
pairs += ++repeat;
}
else repeat = 0;
}
return pairs;
}
Analysis
expand all
Example tests
1.
0.020 s
WRONG ANSWER,
got 10 expected 4
Code: 14:04:36 UTC,
c,
verify,
result: Failed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273
#include <stdlib.h>
static int compare_ints (const void * pa, const void * pb) { return *(int*)pa - *(int *)pb ; }
static int compare_clocks_M;
static int compare_clocks (const void * pa, const void * pb)
{
int i;
const int * a = *(const int *)pa;
const int * b = *(const int *)pb;
for (i = 0 ; i != compare_clocks_M ; i++)
{
if (a[i] != b[i]) return a[i] - b[i];
}
return 0;
}
int solution(int **clocks, int num_clocks, int num_hands, int positions)
{
int c;
int pairs = 0; // the result
int repeat = 0; // clock signature repetition counter
// put all clocks in canonical position
for (c = 0 ; c != num_clocks ; c++)
{
int i;
unsigned s_min = (unsigned)-1, o_min;
int * clock = clocks[c];
for (i = 0 ; i != num_hands ; i++)
{
// signature of positions with current hand rotated to 0
int j;
unsigned offset = positions - clock[i];
unsigned signature = 0;
for (j = 0 ; j != num_hands ; j++)
{
signature += (clock[j] + offset) % positions;
}
// retain position with minimal signature
if (signature < s_min)
{
s_min = signature;
o_min = offset;
}
}
// put clock in its canonical position
for (i = 0 ; i != num_hands ; i++)
{
clock[i] = (clock[i] + o_min) % positions;
}
qsort (clock, num_hands, sizeof(*clock), compare_ints);
}
// sort clocks
compare_clocks_M = num_hands;
qsort (clocks, num_clocks, sizeof(*clocks), compare_clocks);
// count duplicates
repeat = 0;
for (c = 1 ; c != num_clocks ; c++)
{
if (compare_clocks (&clocks[c-1], &clocks[c]))
{
pairs += ++repeat;
}
else repeat = 0;
}
return pairs;
}
Analysis
expand all
Example tests
1.
0.020 s
WRONG ANSWER,
got 1 expected 4
Code: 14:05:45 UTC,
c,
verify,
result: Failed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273
#include <stdlib.h>
static int compare_ints (const void * pa, const void * pb) { return *(int*)pa - *(int *)pb ; }
static int compare_clocks_M;
static int compare_clocks (const void * pa, const void * pb)
{
int i;
const int * a = *((const int *)pa);
const int * b = *(const int *)pb;
for (i = 0 ; i != compare_clocks_M ; i++)
{
if (a[i] != b[i]) return a[i] - b[i];
}
return 0;
}
int solution(int **clocks, int num_clocks, int num_hands, int positions)
{
int c;
int pairs = 0; // the result
int repeat = 0; // clock signature repetition counter
// put all clocks in canonical position
for (c = 0 ; c != num_clocks ; c++)
{
int i;
unsigned s_min = (unsigned)-1, o_min;
int * clock = clocks[c];
for (i = 0 ; i != num_hands ; i++)
{
// signature of positions with current hand rotated to 0
int j;
unsigned offset = positions - clock[i];
unsigned signature = 0;
for (j = 0 ; j != num_hands ; j++)
{
signature += (clock[j] + offset) % positions;
}
// retain position with minimal signature
if (signature < s_min)
{
s_min = signature;
o_min = offset;
}
}
// put clock in its canonical position
for (i = 0 ; i != num_hands ; i++)
{
clock[i] = (clock[i] + o_min) % positions;
}
qsort (clock, num_hands, sizeof(*clock), compare_ints);
}
// sort clocks
compare_clocks_M = num_hands;
qsort (clocks, num_clocks, sizeof(*clocks), compare_clocks);
// count duplicates
repeat = 0;
for (c = 1 ; c != num_clocks ; c++)
{
if (compare_clocks (&clocks[c-1], &clocks[c]))
{
pairs += ++repeat;
}
else repeat = 0;
}
return pairs;
}
Analysis
expand all
Example tests
1.
0.020 s
WRONG ANSWER,
got 1 expected 4
Code: 14:10:51 UTC,
c,
verify,
result: Failed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273
#include <stdlib.h>
static int compare_ints (const void * pa, const void * pb) { return *(int*)pa - *(int *)pb ; }
static int compare_clocks_M;
static int compare_clocks (const void * pa, const void * pb)
{
int i;
const int * a = *((const int *)pa);
const int * b = *(const int *)pb;
for (i = 0 ; i != compare_clocks_M ; i++)
{
if (a[i] != b[i]) return a[i] - b[i];
}
return 0;
}
int solution(int **clocks, int num_clocks, int num_hands, int positions)
{
int c;
int pairs = 0; // the result
int repeat = 0; // clock signature repetition counter
// put all clocks in canonical position
for (c = 0 ; c != num_clocks ; c++)
{
int i;
unsigned s_min = (unsigned)-1, o_min;
int * clock = clocks[c];
for (i = 0 ; i != num_hands ; i++)
{
// signature of positions with current hand rotated to 0
int j;
unsigned offset = positions - clock[i];
unsigned signature = 0;
for (j = 0 ; j != num_hands ; j++)
{
signature += (clock[j] + offset) % positions;
}
// retain position with minimal signature
if (signature < s_min)
{
s_min = signature;
o_min = offset;
}
}
// put clock in its canonical position
for (i = 0 ; i != num_hands ; i++)
{
clock[i] = (clock[i] + o_min) % positions;
}
qsort (clock, num_hands, sizeof(*clock), compare_ints);
}
// sort clocks
compare_clocks_M = num_hands;
qsort (clocks, num_clocks, num_hands * sizeof(**clocks), compare_clocks);
// count duplicates
repeat = 0;
for (c = 1 ; c != num_clocks ; c++)
{
if (compare_clocks (&clocks[c-1], &clocks[c]))
{
pairs += ++repeat;
}
else repeat = 0;
}
return pairs;
}
Analysis
expand all
Example tests
1.
0.020 s
RUNTIME ERROR,
tested program terminated unexpectedly
stdout:
Segmentation Fault [MONITOR] syscall tgkill was blocked! [MONITOR] syscall tgkill was blocked!
Code: 14:12:22 UTC,
c,
verify,
result: Failed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273
#include <stdlib.h>
static int compare_ints (const void * pa, const void * pb) { return *(int*)pa - *(int *)pb ; }
static int compare_clocks_M;
static int compare_clocks (const void * pa, const void * pb)
{
int i;
const int * a = *((const int *)pa);
const int * b = *(const int *)pb;
for (i = 0 ; i != compare_clocks_M ; i++)
{
if (a[i] != b[i]) return a[i] - b[i];
}
return 0;
}
int solution(int **clocks, int num_clocks, int num_hands, int positions)
{
int c;
int pairs = 0; // the result
int repeat = 0; // clock signature repetition counter
// put all clocks in canonical position
for (c = 0 ; c != num_clocks ; c++)
{
int i;
unsigned s_min = (unsigned)-1, o_min;
int * clock = clocks[c];
for (i = 0 ; i != num_hands ; i++)
{
// signature of positions with current hand rotated to 0
int j;
unsigned offset = positions - clock[i];
unsigned signature = 0;
for (j = 0 ; j != num_hands ; j++)
{
signature += (clock[j] + offset) % positions;
}
// retain position with minimal signature
if (signature < s_min)
{
s_min = signature;
o_min = offset;
}
}
// put clock in its canonical position
for (i = 0 ; i != num_hands ; i++)
{
clock[i] = (clock[i] + o_min) % positions;
}
qsort (clock, num_hands, sizeof(*clock), compare_ints);
}
// sort clocks
compare_clocks_M = num_hands;
qsort (clocks, num_clocks, sizeof(*clocks), compare_clocks);
// count duplicates
repeat = 0;
for (c = 1 ; c != num_clocks ; c++)
{
if (compare_clocks (&clocks[c-1], &clocks[c]))
{
pairs += ++repeat;
}
else repeat = 0;
}
return pairs;
}
Analysis
expand all
Example tests
1.
0.020 s
WRONG ANSWER,
got 1 expected 4
Code: 14:14:33 UTC,
c,
verify,
result: Passed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273
#include <stdlib.h>
static int compare_ints (const void * pa, const void * pb) { return *(int*)pa - *(int *)pb ; }
static int compare_clocks_M;
static int compare_clocks (const void * pa, const void * pb)
{
int i;
const int * a = *((const int *)pa);
const int * b = *(const int *)pb;
for (i = 0 ; i != compare_clocks_M ; i++)
{
if (a[i] != b[i]) return a[i] - b[i];
}
return 0;
}
int solution(int **clocks, int num_clocks, int num_hands, int positions)
{
int c;
int pairs = 0; // the result
int repeat = 0; // clock signature repetition counter
// put all clocks in canonical position
for (c = 0 ; c != num_clocks ; c++)
{
int i;
unsigned s_min = (unsigned)-1, o_min;
int * clock = clocks[c];
for (i = 0 ; i != num_hands ; i++)
{
// signature of positions with current hand rotated to 0
int j;
unsigned offset = positions - clock[i];
unsigned signature = 0;
for (j = 0 ; j != num_hands ; j++)
{
signature += (clock[j] + offset) % positions;
}
// retain position with minimal signature
if (signature < s_min)
{
s_min = signature;
o_min = offset;
}
}
// put clock in its canonical position
for (i = 0 ; i != num_hands ; i++)
{
clock[i] = (clock[i] + o_min) % positions;
}
qsort (clock, num_hands, sizeof(*clock), compare_ints);
}
// sort clocks
compare_clocks_M = num_hands;
qsort (clocks, num_clocks, sizeof(*clocks), compare_clocks);
// count duplicates
repeat = 0;
for (c = 1 ; c != num_clocks ; c++)
{
if (!compare_clocks (&clocks[c-1], &clocks[c]))
{
pairs += ++repeat;
}
else repeat = 0;
}
return pairs;
}
Analysis
Code: 14:15:35 UTC,
c,
verify,
result: Passed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273
#include <stdlib.h>
static int compare_ints (const void * pa, const void * pb) { return *(int*)pa - *(int *)pb ; }
static int compare_clocks_M;
static int compare_clocks (const void * pa, const void * pb)
{
int i;
const int * a = *(const int **)pa;
const int * b = *(const int **)pb;
for (i = 0 ; i != compare_clocks_M ; i++)
{
if (a[i] != b[i]) return a[i] - b[i];
}
return 0;
}
int solution(int **clocks, int num_clocks, int num_hands, int positions)
{
int c;
int pairs = 0; // the result
int repeat = 0; // clock signature repetition counter
// put all clocks in canonical position
for (c = 0 ; c != num_clocks ; c++)
{
int i;
unsigned s_min = (unsigned)-1, o_min;
int * clock = clocks[c];
for (i = 0 ; i != num_hands ; i++)
{
// signature of positions with current hand rotated to 0
int j;
unsigned offset = positions - clock[i];
unsigned signature = 0;
for (j = 0 ; j != num_hands ; j++)
{
signature += (clock[j] + offset) % positions;
}
// retain position with minimal signature
if (signature < s_min)
{
s_min = signature;
o_min = offset;
}
}
// put clock in its canonical position
for (i = 0 ; i != num_hands ; i++)
{
clock[i] = (clock[i] + o_min) % positions;
}
qsort (clock, num_hands, sizeof(*clock), compare_ints);
}
// sort clocks
compare_clocks_M = num_hands;
qsort (clocks, num_clocks, sizeof(*clocks), compare_clocks);
// count duplicates
repeat = 0;
for (c = 1 ; c != num_clocks ; c++)
{
if (!compare_clocks (&clocks[c-1], &clocks[c]))
{
pairs += ++repeat;
}
else repeat = 0;
}
return pairs;
}
Analysis
Code: 14:16:01 UTC,
c,
verify,
result: Passed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273
#include <stdlib.h>
static int compare_ints (const void * pa, const void * pb) { return *(int*)pa - *(int *)pb ; }
static int compare_clocks_M;
static int compare_clocks (const void * pa, const void * pb)
{
int i;
const int * a = *(const int **)pa;
const int * b = *(const int **)pb;
for (i = 0 ; i != compare_clocks_M ; i++)
{
if (a[i] != b[i]) return a[i] - b[i];
}
return 0;
}
int solution(int **clocks, int num_clocks, int num_hands, int positions)
{
int c;
int pairs = 0; // the result
int repeat = 0; // clock signature repetition counter
// put all clocks in canonical position
for (c = 0 ; c != num_clocks ; c++)
{
int i;
unsigned s_min = (unsigned)-1, o_min=-1;
int * clock = clocks[c];
for (i = 0 ; i != num_hands ; i++)
{
// signature of positions with current hand rotated to 0
int j;
unsigned offset = positions - clock[i];
unsigned signature = 0;
for (j = 0 ; j != num_hands ; j++)
{
signature += (clock[j] + offset) % positions;
}
// retain position with minimal signature
if (signature < s_min)
{
s_min = signature;
o_min = offset;
}
}
// put clock in its canonical position
for (i = 0 ; i != num_hands ; i++)
{
clock[i] = (clock[i] + o_min) % positions;
}
qsort (clock, num_hands, sizeof(*clock), compare_ints);
}
// sort clocks
compare_clocks_M = num_hands;
qsort (clocks, num_clocks, sizeof(*clocks), compare_clocks);
// count duplicates
repeat = 0;
for (c = 1 ; c != num_clocks ; c++)
{
if (!compare_clocks (&clocks[c-1], &clocks[c]))
{
pairs += ++repeat;
}
else repeat = 0;
}
return pairs;
}
Analysis
Code: 14:16:37 UTC,
c,
verify,
result: Passed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273
#include <stdlib.h>
static int compare_ints (const void * pa, const void * pb) { return *(int*)pa - *(int *)pb ; }
static int compare_clocks_M;
static int compare_clocks (const void * pa, const void * pb)
{
int i;
const int * a = *(const int **)pa;
const int * b = *(const int **)pb;
for (i = 0 ; i != compare_clocks_M ; i++)
{
if (a[i] != b[i]) return a[i] - b[i];
}
return 0;
}
int solution(int **clocks, int num_clocks, int num_hands, int positions)
{
int c;
int pairs = 0; // the result
int repeat = 0; // clock signature repetition counter
// put all clocks in canonical position
for (c = 0 ; c != num_clocks ; c++)
{
int i;
unsigned s_min = (unsigned)-1, o_min=-1;
int * clock = clocks[c];
for (i = 0 ; i != num_hands ; i++)
{
// signature of positions with current hand rotated to 0
int j;
unsigned offset = positions - clock[i];
unsigned signature = 0;
for (j = 0 ; j != num_hands ; j++)
{
signature += (clock[j] + offset) % positions;
}
// retain position with minimal signature
if (signature < s_min)
{
s_min = signature;
o_min = offset;
}
}
// put clock in its canonical position
for (i = 0 ; i != num_hands ; i++)
{
clock[i] = (clock[i] + o_min) % positions;
}
qsort (clock, num_hands, sizeof(*clock), compare_ints);
}
// sort clocks
compare_clocks_M = num_hands;
qsort (clocks, num_clocks, sizeof(*clocks), compare_clocks);
// count duplicates
repeat = 0;
for (c = 1 ; c != num_clocks ; c++)
{
if (!compare_clocks (&clocks[c-1], &clocks[c]))
{
pairs += ++repeat;
}
else repeat = 0;
}
return pairs;
}
Analysis
Code: 14:16:39 UTC,
c,
final,
score:
90
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273
#include <stdlib.h>
static int compare_ints (const void * pa, const void * pb) { return *(int*)pa - *(int *)pb ; }
static int compare_clocks_M;
static int compare_clocks (const void * pa, const void * pb)
{
int i;
const int * a = *(const int **)pa;
const int * b = *(const int **)pb;
for (i = 0 ; i != compare_clocks_M ; i++)
{
if (a[i] != b[i]) return a[i] - b[i];
}
return 0;
}
int solution(int **clocks, int num_clocks, int num_hands, int positions)
{
int c;
int pairs = 0; // the result
int repeat = 0; // clock signature repetition counter
// put all clocks in canonical position
for (c = 0 ; c != num_clocks ; c++)
{
int i;
unsigned s_min = (unsigned)-1, o_min=-1;
int * clock = clocks[c];
for (i = 0 ; i != num_hands ; i++)
{
// signature of positions with current hand rotated to 0
int j;
unsigned offset = positions - clock[i];
unsigned signature = 0;
for (j = 0 ; j != num_hands ; j++)
{
signature += (clock[j] + offset) % positions;
}
// retain position with minimal signature
if (signature < s_min)
{
s_min = signature;
o_min = offset;
}
}
// put clock in its canonical position
for (i = 0 ; i != num_hands ; i++)
{
clock[i] = (clock[i] + o_min) % positions;
}
qsort (clock, num_hands, sizeof(*clock), compare_ints);
}
// sort clocks
compare_clocks_M = num_hands;
qsort (clocks, num_clocks, sizeof(*clocks), compare_clocks);
// count duplicates
repeat = 0;
for (c = 1 ; c != num_clocks ; c++)
{
if (!compare_clocks (&clocks[c-1], &clocks[c]))
{
pairs += ++repeat;
}
else repeat = 0;
}
return pairs;
}Analysis summary
The following issues have been detected: timeout errors.
Analysis
Detected time complexity:
O(N * M * log(M) + N * log(N))
expand all
Assessment tests
1.
0.020 s
OK
1.
0.020 s
OK
1.
0.020 s
OK
1.
0.020 s
OK
1.
0.020 s
OK
1.
0.020 s
OK
1.
0.020 s
OK
1.
0.020 s
OK
1.
0.020 s
OK
1.
0.020 s
OK
1.
0.020 s
OK
1.
0.030 s
OK
1.
0.020 s
OK
large_random_tinyDifferent
large random tests, number of clocks = 500 (different = 2)
large random tests, number of clocks = 500 (different = 2)
✘
TIMEOUT ERROR
running time: >0.61 sec., time limit: 0.56 sec.
running time: >0.61 sec., time limit: 0.56 sec.
1.
0.610 s
TIMEOUT ERROR,
running time: >0.61 sec., time limit: 0.56 sec.
1.
0.440 s
OK
1.
0.480 s
OK
1.
0.660 s
OK
1.
0.450 s
OK
1.
0.260 s
OK
1.
0.630 s
OK
extreme_maximal_pairs
all clocks looks the same
all clocks looks the same
✘
TIMEOUT ERROR
running time: >0.61 sec., time limit: 0.44 sec.
running time: >0.61 sec., time limit: 0.44 sec.
1.
0.610 s
TIMEOUT ERROR,
running time: >0.61 sec., time limit: 0.44 sec.