Test results - Codility

Tasks Details

hard

1. MaxNotPresent

You have a deck of cards in which each card has two numbers: one on the front and one on the back. Flip some cards over so as to maximize the smallest integer that's not present on any card's front.

Task Score

100%

Correctness

100%

Performance

100%

You are playing a game with N cards. On both sides of each card there is a positive integer. The cards are laid on the table. The score of the game is the smallest positive integer that does not occur on the face-up cards. You may flip some cards over. Having flipped them, you then read the numbers facing up and recalculate the score. What is the maximum score you can achieve?

Write a function:

def solution(A, B)

that, given two arrays of integers A and B, both of length N, describing the numbers written on both sides of the cards, facing up and down respectively, returns the maximum possible score.

For example, given A = [1, 2, 4, 3] and B = [1, 3, 2, 3], your function should return 5, as without flipping any card the smallest positive integer excluded from this sequence is 5.

Given A = [4, 2, 1, 6, 5] and B = [3, 2, 1, 7, 7], your function should return 4, as we could flip the first card so that the numbers facing up are [3, 2, 1, 6, 5] and it is impossible to have both numbers 3 and 4 facing up.

Given A = [2, 3] and B = [2, 3] your function should return 1, as no matter how the cards are flipped, the numbers facing up are [2, 3].

Write an efficient algorithm for the following assumptions:

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

each element of arrays A and B is an integer within the range [1..100,000,000];

input arrays are of equal size.

Solution

Programming language used Python

Time spent on task 8 minutes

Notes

not defined yet

Code: 20:47:55 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A, int[] B) {
        // write your code in Java SE 8
    }
}

Code: 20:54:19 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A, B):
    # write your code in Python 3.6
    pass

Code: 20:54:35 UTC, py, autosave

show code in pop-up

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

coin,maximum,visited= [],[],[]

def find (x): #finding maximum and marking 
    if (x!=coin[x]): coin[x]=find(coin[x])
    return (coin[x])

def solution(A, B):
    n=len(A) #initialization and filling arrays
    for x in range(0,n+1):
        coin.append(x)
        maximum.append(x)
        visited.append(False)

    for x in range(0,n):
        if A[x]>n and B[x]>n: continue #pass if front and back side of card value too big
        elif A[x]>n or B[x]>n or (B[x]==A[x]): #if only one side of card fits
            f=b=find(min(A[x],B[x]))
        else: f,b=find(A[x]),find(B[x]) #both sides of card fits
        #main part that make changes    
        if (f==b): visited[f]=True
        else:
            coin[f]=b
            if visited[f]==True: visited[b]=True 
            maximum[b]=max(maximum[f],maximum[b])
    
    #finding final result
    result = n+1;
    for i in range (1,n+1): 
        if visited[find(i)]==False: result =min(result, maximum[find(i)])

    return (result)

Code: 20:54:54 UTC, py, autosave

show code in pop-up

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

card,maximum,visited= [],[],[]

def find (x): #finding maximum and marking 
    if (x!=card[x]): card[x]=find(coin[x])
    return (card[x])

def solution(A, B):
    n=len(A) #initialization and filling arrays
    for x in range(0,n+1):
        coin.append(x)
        maximum.append(x)
        visited.append(False)

    for x in range(0,n):
        if A[x]>n and B[x]>n: continue #pass if front and back side of card value too big
        elif A[x]>n or B[x]>n or (B[x]==A[x]): #if only one side of card fits
            f=b=find(min(A[x],B[x]))
        else: f,b=find(A[x]),find(B[x]) #both sides of card fits
        #main part that make changes    
        if (f==b): visited[f]=True
        else:
            coin[f]=b
            if visited[f]==True: visited[b]=True 
            maximum[b]=max(maximum[f],maximum[b])
    
    #finding final result
    result = n+1;
    for i in range (1,n+1): 
        if visited[find(i)]==False: result =min(result, maximum[find(i)])

    return (result)

Code: 20:55:05 UTC, py, autosave

show code in pop-up

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

card,maximum,visited= [],[],[]

def find (x): #finding maximum and marking 
    if (x!=card[x]): card[x]=find(coin[x])
    return (card[x])

def solution(A, B):
    n=len(A) #initialization and filling arrays
    for x in range(0,n+1):
        card.append(x)
        maximum.append(x)
        visited.append(False)

    for x in range(0,n):
        if A[x]>n and B[x]>n: continue #pass if front and back side of card value too big
        elif A[x]>n or B[x]>n or (B[x]==A[x]): #if only one side of card fits
            f=b=find(min(A[x],B[x]))
        else: f,b=find(A[x]),find(B[x]) #both sides of card fits
        #main part that make changes    
        if (f==b): visited[f]=True
        else:
            coin[f]=b
            if visited[f]==True: visited[b]=True 
            maximum[b]=max(maximum[f],maximum[b])
    
    #finding final result
    result = n+1;
    for i in range (1,n+1): 
        if visited[find(i)]==False: result =min(result, maximum[find(i)])

    return (result)

Code: 20:55:15 UTC, py, verify, result: Failed

show code in pop-up

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

card,maximum,visited= [],[],[]

def find (x): #finding maximum and marking 
    if (x!=card[x]): card[x]=find(coin[x])
    return (card[x])

def solution(A, B):
    n=len(A) #initialization and filling arrays
    for x in range(0,n+1):
        card.append(x)
        maximum.append(x)
        visited.append(False)

    for x in range(0,n):
        if A[x]>n and B[x]>n: continue #pass if front and back side of card value too big
        elif A[x]>n or B[x]>n or (B[x]==A[x]): #if only one side of card fits
            f=b=find(min(A[x],B[x]))
        else: f,b=find(A[x]),find(B[x]) #both sides of card fits
        #main part that make changes    
        if (f==b): visited[f]=True
        else:
            card[f]=b
            if visited[f]==True: visited[b]=True 
            maximum[b]=max(maximum[f],maximum[b])
    
    #finding final result
    result = n+1;
    for i in range (1,n+1): 
        if visited[find(i)]==False: result =min(result, maximum[find(i)])

    return (result)

Analysis

expand all Example tests

▶

example1
first example test from problem statement

✘

RUNTIME ERROR
tested program terminated with exit code 1

0.040 s

RUNTIME ERROR, tested program terminated with exit code 1

stderr:

Traceback (most recent call last):
  File "exec.py", line 139, in <module>
    main()
  File "exec.py", line 101, in main
    result = solution( A, B )
  File "/tmp/solution.py", line 18, in solution
    else: f,b=find(A[x]),find(B[x]) #both sides of card fits
  File "/tmp/solution.py", line 4, in find
    if (x!=card[x]): card[x]=find(coin[x])
NameError: name 'coin' is not defined

▶

example2
second example test from problem statement

✘

RUNTIME ERROR
tested program terminated with exit code 1

0.036 s

RUNTIME ERROR, tested program terminated with exit code 1

stderr:

Traceback (most recent call last):
  File "exec.py", line 139, in <module>
    main()
  File "exec.py", line 101, in main
    result = solution( A, B )
  File "/tmp/solution.py", line 29, in solution
    if visited[find(i)]==False: result =min(result, maximum[find(i)])
  File "/tmp/solution.py", line 4, in find
    if (x!=card[x]): card[x]=find(coin[x])
NameError: name 'coin' is not defined

▶

example3
third example test from problem statement

✔

0.036 s

Code: 20:55:35 UTC, py, autosave

show code in pop-up

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

card,maximum,visited= [],[],[]

def find (x): #finding maximum and marking 
    if (x!=card[x]): card[x]=find(cra[x])
    return (card[x])

def solution(A, B):
    n=len(A) #initialization and filling arrays
    for x in range(0,n+1):
        card.append(x)
        maximum.append(x)
        visited.append(False)

    for x in range(0,n):
        if A[x]>n and B[x]>n: continue #pass if front and back side of card value too big
        elif A[x]>n or B[x]>n or (B[x]==A[x]): #if only one side of card fits
            f=b=find(min(A[x],B[x]))
        else: f,b=find(A[x]),find(B[x]) #both sides of card fits
        #main part that make changes    
        if (f==b): visited[f]=True
        else:
            card[f]=b
            if visited[f]==True: visited[b]=True 
            maximum[b]=max(maximum[f],maximum[b])
    
    #finding final result
    result = n+1;
    for i in range (1,n+1): 
        if visited[find(i)]==False: result =min(result, maximum[find(i)])

    return (result)

Code: 20:55:39 UTC, py, verify, result: Passed

show code in pop-up

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

card,maximum,visited= [],[],[]

def find (x): #finding maximum and marking 
    if (x!=card[x]): card[x]=find(card[x])
    return (card[x])

def solution(A, B):
    n=len(A) #initialization and filling arrays
    for x in range(0,n+1):
        card.append(x)
        maximum.append(x)
        visited.append(False)

    for x in range(0,n):
        if A[x]>n and B[x]>n: continue #pass if front and back side of card value too big
        elif A[x]>n or B[x]>n or (B[x]==A[x]): #if only one side of card fits
            f=b=find(min(A[x],B[x]))
        else: f,b=find(A[x]),find(B[x]) #both sides of card fits
        #main part that make changes    
        if (f==b): visited[f]=True
        else:
            card[f]=b
            if visited[f]==True: visited[b]=True 
            maximum[b]=max(maximum[f],maximum[b])
    
    #finding final result
    result = n+1;
    for i in range (1,n+1): 
        if visited[find(i)]==False: result =min(result, maximum[find(i)])

    return (result)

Analysis

expand all Example tests

▶

example1
first example test from problem statement

✔

0.036 s

▶

example2
second example test from problem statement

✔

0.036 s

▶

example3
third example test from problem statement

✔

0.036 s

Code: 20:55:45 UTC, py, verify, result: Passed

show code in pop-up

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

card,maximum,visited= [],[],[]

def find (x): #finding maximum and marking 
    if (x!=card[x]): card[x]=find(card[x])
    return (card[x])

def solution(A, B):
    n=len(A) #initialization and filling arrays
    for x in range(0,n+1):
        card.append(x)
        maximum.append(x)
        visited.append(False)

    for x in range(0,n):
        if A[x]>n and B[x]>n: continue #pass if front and back side of card value too big
        elif A[x]>n or B[x]>n or (B[x]==A[x]): #if only one side of card fits
            f=b=find(min(A[x],B[x]))
        else: f,b=find(A[x]),find(B[x]) #both sides of card fits
        #main part that make changes    
        if (f==b): visited[f]=True
        else:
            card[f]=b
            if visited[f]==True: visited[b]=True 
            maximum[b]=max(maximum[f],maximum[b])
    
    #finding final result
    result = n+1;
    for i in range (1,n+1): 
        if visited[find(i)]==False: result =min(result, maximum[find(i)])

    return (result)

Analysis

expand all Example tests

▶

example1
first example test from problem statement

✔

0.036 s

▶

example2
second example test from problem statement

✔

0.036 s

▶

example3
third example test from problem statement

✔

0.036 s

Code: 20:55:47 UTC, py, final, score: 100

show code in pop-up

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

card,maximum,visited= [],[],[]

def find (x): #finding maximum and marking 
    if (x!=card[x]): card[x]=find(card[x])
    return (card[x])

def solution(A, B):
    n=len(A) #initialization and filling arrays
    for x in range(0,n+1):
        card.append(x)
        maximum.append(x)
        visited.append(False)

    for x in range(0,n):
        if A[x]>n and B[x]>n: continue #pass if front and back side of card value too big
        elif A[x]>n or B[x]>n or (B[x]==A[x]): #if only one side of card fits
            f=b=find(min(A[x],B[x]))
        else: f,b=find(A[x]),find(B[x]) #both sides of card fits
        #main part that make changes    
        if (f==b): visited[f]=True
        else:
            card[f]=b
            if visited[f]==True: visited[b]=True 
            maximum[b]=max(maximum[f],maximum[b])
    
    #finding final result
    result = n+1;
    for i in range (1,n+1): 
        if visited[find(i)]==False: result =min(result, maximum[find(i)])

    return (result)

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N)

expand all Example tests

▶

example1
first example test from problem statement

✔

0.036 s

▶

example2
second example test from problem statement

✔

0.036 s

▶

example3
third example test from problem statement

✔

0.036 s

expand all Correctness tests

▶

tiny_hand
tiny tests generated by hand

✔

0.036 s

▶

tiny_random
small random tests, N ~ 20

✔

0.036 s

▶

tiny_corner
corner cases

✔

0.036 s

▶

tiny_special
small special cases, N ~ 20

✔

0.036 s

▶

small_large_number
small tests with large numbers in arrays

✔

0.036 s

expand all Correctness/performance tests

▶

small_special
special cases, N ~ 40

✔

0.036 s

expand all Performance tests

▶

medium_random
medium random cases

✔

0.044 s

0.040 s

0.044 s

▶

medium_special
medium special cases

✔

0.040 s

▶

large_random
large random tests

✔

0.560 s

0.588 s

0.632 s

0.620 s

0.656 s

0.644 s

0.680 s

0.668 s

0.676 s

10.

0.648 s

11.

0.644 s

12.

0.380 s

▶

large_special
large special cases

✔

0.176 s

0.280 s

0.644 s

0.640 s