вторник, 14 января 2014 г.

Codility. Train. Brackets ★

A string S consisting of N characters is considered to be properly nested if any of the following conditions is true:
  • S is empty;
  • S has the form "(U)" or "[U]" or "{U}" where U is a properly nested string;
  • S has the form "VW" where V and W are properly nested strings.
For example, the string "{[()()]}" is properly nested but "([)()]" is not.
Write a function:
int solution(char *S);
that, given a string S consisting of N characters, returns 1 if S is properly nested and 0 otherwise.
For example, given S = "{[()()]}", the function should return 1 and given S = "([)()]", the function should return 0, as explained above.
Assume that:
  • N is an integer within the range [0..200,000];
  • string S consists only of the following characters: "(", "{", "[", "]", "}" and/or ")".
Complexity:
  • expected worst-case time complexity is O(N);
  • expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

понедельник, 13 января 2014 г.

Codility. Train. Number-of-disc-intersections ★★★

Given an array A of N integers, we draw N discs in a 2D plane such that the I-th disc is centered on (0,I) and has a radius of A[I]. We say that the J-th disc and K-th disc intersect if J ≠ K and J-th and K-th discs have at least one common point.
Write a function:
def solution(A)
that, given an array A describing N discs as explained above, returns the number of pairs of intersecting discs. For example, given N=6 and:
A[0] = 1  A[1] = 5  A[2] = 2 
A[3] = 1  A[4] = 4  A[5] = 0  
intersecting discs appear in eleven pairs of elements:
  • 0 and 1,
  • 0 and 2,
  • 0 and 4,
  • 1 and 2,
  • 1 and 3,
  • 1 and 4,
  • 1 and 5,
  • 2 and 3,
  • 2 and 4,
  • 3 and 4,
  • 4 and 5.
so the function should return 11.
The function should return −1 if the number of intersecting pairs exceeds 10,000,000.
Assume that:
  • N is an integer within the range [0..100,000];
  • each element of array A is an integer within the range [0..2147483647].
Complexity:
  • expected worst-case time complexity is O(N*log(N));
  • expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.

Codility. Train. Max-product-of-three ★★

A non-empty zero-indexed array A consisting of N integers is given. The product of triplet (P, Q, R) equates to A[P] * A[Q] * A[R] (0 ≤ P < Q < R < N).
For example, array A such that:
  A[0] = -3
  A[1] = 1
  A[2] = 2
  A[3] = -2
  A[4] = 5
  A[5] = 6
contains the following example triplets:
  • (0, 1, 2), product is −3 * 1 * 2 = −6
  • (1, 2, 4), product is 1 * 2 * 5 = 10
  • (2, 4, 5), product is 2 * 5 * 6 = 60
Your goal is to find the maximal product of any triplet.
Write a function:
def solution(A)
that, given a non-empty zero-indexed array A, returns the value of the maximal product of any triplet.
For example, given array A such that:
  A[0] = -3
  A[1] = 1
  A[2] = 2
  A[3] = -2
  A[4] = 5
  A[5] = 6
the function should return 60, as the product of triplet (2, 4, 5) is maximal.
Assume that:
  • N is an integer within the range [3..100,000];
  • each element of array A is an integer within the range [−1,000..1,000].
Complexity:
  • expected worst-case time complexity is O(N*log(N));
  • expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.

Codility. Train. Triangle ★

A zero-indexed array A consisting of N integers is given. A triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N and:
  • A[P] + A[Q] > A[R],
  • A[Q] + A[R] > A[P],
  • A[R] + A[P] > A[Q].
For example, consider array A such that:
  A[0] = 10    A[1] = 2    A[2] = 5
  A[3] = 1     A[4] = 8    A[5] = 20
Triplet (0, 2, 4) is triangular.
Write a function:
def solution(A)
that, given a zero-indexed array A consisting of N integers, returns 1 if there exists a triangular triplet for this array and returns 0 otherwise. For example, given array A such that:
  A[0] = 10    A[1] = 2    A[2] = 5
  A[3] = 1     A[4] = 8    A[5] = 20
the function should return 1, as explained above. Given array A such that:
  A[0] = 10    A[1] = 50    A[2] = 5
  A[3] = 1
the function should return 0.
Assume that:
  • N is an integer within the range [0..1,000,000];
  • each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].
Complexity:
  • expected worst-case time complexity is O(N*log(N));
  • expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.

пятница, 10 января 2014 г.

Codility. Train. Genomic-range-query ★★★

A non-empty zero-indexed string S is given. String S consists of N characters from the set of upper-case English letters A, C, G, T.
This string actually represents a DNA sequence, and the upper-case letters represent single nucleotides.
You are also given non-empty zero-indexed arrays P and Q consisting of M integers. These arrays represent queries about minimal nucleotides. We represent the letters of string S as integers 1, 2, 3, 4 in arrays P and Q, where A = 1, C = 2, G = 3, T = 4, and we assume that A < C < G < T.
Query K requires you to find the minimal nucleotide from the range (P[K], Q[K]), 0 ≤ P[i] ≤ Q[i] < N.
For example, consider string S = GACACCATA and arrays P, Q such that:
    P[0] = 0    Q[0] = 8
    P[1] = 0    Q[1] = 2
    P[2] = 4    Q[2] = 5
    P[3] = 7    Q[3] = 7
The minimal nucleotides from these ranges are as follows:
  • (0, 8) is A identified by 1,
  • (0, 2) is A identified by 1,
  • (4, 5) is C identified by 2,
  • (7, 7) is T identified by 4.
Write a function:
def solution(S, P, Q)
that, given a non-empty zero-indexed string S consisting of N characters and two non-empty zero-indexed arrays P and Q consisting of M integers, returns an array consisting of M characters specifying the consecutive answers to all queries.
The sequence should be returned as:
  • a Results structure (in C), or
  • a vector of integers (in C++), or
  • a Results record (in Pascal), or
  • an array of integers (in any other programming language).
For example, given the string S = GACACCATA and arrays P, Q such that:
    P[0] = 0    Q[0] = 8
    P[1] = 0    Q[1] = 2
    P[2] = 4    Q[2] = 5
    P[3] = 7    Q[3] = 7
the function should return the values [1, 1, 2, 4], as explained above.
Assume that:
  • N is an integer within the range [1..100,000];
  • M is an integer within the range [1..50,000];
  • each element of array P, Q is an integer within the range [0..N − 1];
  • P[i] ≤ Q[i];
  • string S consists only of upper-case English letters A, C, G, T.
Complexity:
  • expected worst-case time complexity is O(N+M);
  • expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.