Test results - Codility

Tasks Details

hard

1. CuttingTheCake

Find the K-th piece of a cake in terms of size.

100%

You are presented with a rectangular cake whose sides are of length X and Y. The cake has been cut into (N + 1)² pieces by making N straight cuts along the first side and N straight cuts along the second side.

The cuts are represented by two non-empty arrays A and B consisting of N integers. More precisely, A[I] such that 0 ≤ I < N represents the position of a cut along the first side, and B[I] such that 0 ≤ I < N represents the position of a cut along the second side.

The goal is to find the K-th piece of cake in order of size, starting with the largest piece first. We will consider the size of a piece to be its area.

For example, a cake with sides X = 6, Y = 7 and arrays A and B such that:

A[0] = 1 B[0] = 1 A[1] = 3 B[1] = 5

is represented by the figure below.

There are nine pieces of cake, and their consecutive sizes are: 12, 8, 6, 4, 4, 3, 2, 2, 1. In the figure above, the third piece of cake is highlighted; its size equals 6.

Write a function:

def solution(X, Y, K, A, B)

that, given three integers X, Y, K and two non-empty arrays A and B of N integers, returns the size of the K-th piece of cake.

For example, given:

X = 6 Y = 7 K = 3 A[0] = 1 B[0] = 1 A[1] = 3 B[1] = 5

the function should return 6, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..40,000];

X and Y are integers within the range [2..400,000,000];

K is an integer within the range [1..(N+1)*(N+1)];

each element of array A is an integer within the range [1..X-1];

each element of array B is an integer within the range [1..Y-1];

A[I − 1] < A[I] and B[I − 1] < B[I], for every I such that 0 < I < N;

1 ≤ A[I] − A[I − 1], B[I] − B[I − 1] ≤ 10,000, for every I such that 0 < I < N;

1 ≤ A[0], B[0], X − A[N − 1], Y − B[N − 1] ≤ 10,000.

Solution

Programming language used Python

Total time used 102 minutes

Effective time used 102 minutes

Notes

not defined yet

Task timeline

Code: 18:21:49 UTC, py, verify, result: Failed

1 2 3 4 5 6

# you can use print for debugging purposes, e.g.
# print "this is a debug message"

def solution(X, Y, K, A, B):
    # write your code in Python 2.7
    pass

Analysis

▶

example
example test

✘

RUNTIME ERROR
tested program terminated unexpectedly

Code: 19:48:05 UTC, py, verify, result: Passed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

# you can use print for debugging purposes, e.g.
# print "this is a debug message"

def solution(X, Y, K, A, B):
    # write your code in Python 2.7
    xSizes = [0 for i in range(len(A) + 1)]
    
    prevX = 0
    for i in range(0, len(A), 1):
        xSizes[i] = A[i] - prevX;
        prevX = A[i]
    
    xSizes[len(A)] = X - prevX
    
    xSizes.sort()
        


    ySizes = [0 for i in range(len(B) + 1)]
    
    prevY = 0
    for i in range(0, len(B), 1):
        ySizes[i] = B[i] - prevY;
        prevY = B[i]
    
    ySizes[len(B)] = Y - prevY
    
    ySizes.sort()
    max = xSizes[len(A)] * ySizes[len(A)]
    min = xSizes[0] * ySizes[0]
    
    left = min
    right = max
      
    while(left <= right):
        mid = (right - left) // 2 + left
        result = larger(xSizes, ySizes, mid)
        if(result[0] > K - 1):
            left = mid + 1
        elif result[0] + result[1] < K:
            right = mid - 1;
        else:
            return mid

    return -1

def larger(xSizes, ySizes, N):
    
    larger = 0
    equal = 0
    
    i = len(xSizes) - 1
    j = 0
    while (i >= 0 and j < len(ySizes)):
        
        x = xSizes[i]
        y = ySizes[j]
        
        area = x * y
        if(area == N):
            
            tempi = i
            
            while(tempi >= 0 and xSizes[tempi] == xSizes[i]):
                tempi = tempi - 1
            
            tempj = j
            while(tempj < len(ySizes) and ySizes[tempj] == ySizes[j]):
                tempj = tempj + 1
            equal += (i - tempi) * (tempj - j)
            j = tempj
            pass
        elif (area > N):
            larger += (len(ySizes) - j)
            i = i - 1
            pass
        else:
            j = j + 1
            pass

        pass
       
    
    return (larger, equal)

Analysis

▶

example
example test

✔

Code: 19:49:41 UTC, py, verify, result: Passed

# you can use print for debugging purposes, e.g.
# print "this is a debug message"

def solution(X, Y, K, A, B):
    # write your code in Python 2.7
    xSizes = [0 for i in range(len(A) + 1)]
    
    prevX = 0
    for i in range(0, len(A), 1):
        xSizes[i] = A[i] - prevX;
        prevX = A[i]
    
    xSizes[len(A)] = X - prevX
    
    xSizes.sort()
    ySizes = [0 for i in range(len(B) + 1)]
    
    prevY = 0
    for i in range(0, len(B), 1):
        ySizes[i] = B[i] - prevY;
        prevY = B[i]
    
    ySizes[len(B)] = Y - prevY
    
    ySizes.sort()
    max = xSizes[len(A)] * ySizes[len(A)]
    min = xSizes[0] * ySizes[0]
    
    left = min
    right = max
      
    while(left <= right):
        mid = (right - left) // 2 + left
        result = larger(xSizes, ySizes, mid)
        if(result[0] > K - 1):
            left = mid + 1
        elif result[0] + result[1] < K:
            right = mid - 1;
        else:
            return mid

    return -1

def larger(xSizes, ySizes, N):
    
    larger = 0
    equal = 0
    
    i = len(xSizes) - 1
    j = 0
    while (i >= 0 and j < len(ySizes)):
        
        x = xSizes[i]
        y = ySizes[j]
        
        area = x * y
        if(area == N):
            
            tempi = i
            
            while(tempi >= 0 and xSizes[tempi] == xSizes[i]):
                tempi = tempi - 1
            
            tempj = j
            while(tempj < len(ySizes) and ySizes[tempj] == ySizes[j]):
                tempj = tempj + 1
            equal += (i - tempi) * (tempj - j)
            j = tempj
            pass
        elif (area > N):
            larger += (len(ySizes) - j)
            i = i - 1
            pass
        else:
            j = j + 1
            pass

        pass
       
    
    return (larger, equal)

Analysis

▶

example
example test

✔

Code: 19:49:45 UTC, py, final, score: 100

# you can use print for debugging purposes, e.g.
# print "this is a debug message"

def solution(X, Y, K, A, B):
    # write your code in Python 2.7
    xSizes = [0 for i in range(len(A) + 1)]
    
    prevX = 0
    for i in range(0, len(A), 1):
        xSizes[i] = A[i] - prevX;
        prevX = A[i]
    
    xSizes[len(A)] = X - prevX
    
    xSizes.sort()
    ySizes = [0 for i in range(len(B) + 1)]
    
    prevY = 0
    for i in range(0, len(B), 1):
        ySizes[i] = B[i] - prevY;
        prevY = B[i]
    
    ySizes[len(B)] = Y - prevY
    
    ySizes.sort()
    max = xSizes[len(A)] * ySizes[len(A)]
    min = xSizes[0] * ySizes[0]
    
    left = min
    right = max
      
    while(left <= right):
        mid = (right - left) // 2 + left
        result = larger(xSizes, ySizes, mid)
        if(result[0] > K - 1):
            left = mid + 1
        elif result[0] + result[1] < K:
            right = mid - 1;
        else:
            return mid

    return -1

def larger(xSizes, ySizes, N):
    
    larger = 0
    equal = 0
    
    i = len(xSizes) - 1
    j = 0
    while (i >= 0 and j < len(ySizes)):
        
        x = xSizes[i]
        y = ySizes[j]
        
        area = x * y
        if(area == N):
            
            tempi = i
            
            while(tempi >= 0 and xSizes[tempi] == xSizes[i]):
                tempi = tempi - 1
            
            tempj = j
            while(tempj < len(ySizes) and ySizes[tempj] == ySizes[j]):
                tempj = tempj + 1
            equal += (i - tempi) * (tempj - j)
            j = tempj
            pass
        elif (area > N):
            larger += (len(ySizes) - j)
            i = i - 1
            pass
        else:
            j = j + 1
            pass

        pass
       
    
    return (larger, equal)

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N*log(N+X+Y))

▶

example
example test

✔

▶

extreme_one_cut
only one cut

✔

0.067 s

0.066 s

▶

two_cuts
only two cuts

✔

▶

simple1
first simple test, every K-th size for 1 <= K <= 16

✔

0.067 s

0.068 s

0.066 s

0.067 s

0.066 s

10.

0.067 s

11.

0.067 s

12.

0.065 s

13.

0.066 s

14.

0.067 s

15.

0.068 s

16.

0.066 s

▶

simple2
second simple test, every K-th size for 1 <= K <= 16

✔

0.067 s

0.066 s

0.067 s

0.066 s

10.

0.066 s

11.

0.068 s

12.

0.067 s

13.

0.068 s

14.

0.068 s

15.

0.068 s

16.

0.068 s

▶

small_random
random test with ~50 cuts

✔

▶

medium_random
random test with ~400 cuts

✔

▶

large_range
range distances

✔

▶

large_random
random test with ~100,000 cuts

✔

▶

fail_heur
regular test with a large number of items between A[p]B[p] and A[p+1]B[p+1]

✔

▶

extreme_cake
extreme size of cake and the biggest distances

✔