Test results - Codility

Tasks Details

medium

1. RectangleBuilderGreaterArea

Count the distinct rectangle sizes, of area greater than or equal to X, that can be built out of a given set of segments.

100%

Halfling Woolly Proudhoof is an eminent sheep herder. He wants to build a pen (enclosure) for his new flock of sheep. The pen will be rectangular and built from exactly four pieces of fence (so, the pieces of fence forming the opposite sides of the pen must be of equal length). Woolly can choose these pieces out of N pieces of fence that are stored in his barn. To hold the entire flock, the area of the pen must be greater than or equal to a given threshold X.

Woolly is interested in the number of different ways in which he can build a pen. Pens are considered different if the sets of lengths of their sides are different. For example, a pen of size 1×4 is different from a pen of size 2×2 (although both have an area of 4), but pens of sizes 1×2 and 2×1 are considered the same.

Write a function:

int solution(vector<int> &A, int X);

that, given an array A of N integers (containing the lengths of the available pieces of fence) and an integer X, returns the number of different ways of building a rectangular pen satisfying the above conditions. The function should return −1 if the result exceeds 1,000,000,000.

For example, given X = 5 and the following array A:

A[0] = 1 A[1] = 2 A[2] = 5 A[3] = 1 A[4] = 1 A[5] = 2 A[6] = 3 A[7] = 5 A[8] = 1

the function should return 2. The figure above shows available pieces of fence (on the left) and possible to build pens (on the right). The pens are of sizes 1x5 and 2x5. Pens of sizes 1×1 and 1×2 can be built, but are too small in area. It is not possible to build pens of sizes 2×3 or 3×5, as there is only one piece of fence of length 3.

Write an efficient algorithm for the following assumptions:

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

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

each element of array A is an integer within the range [1..1,000,000,000].

Solution

Programming language used C++

Total time used 1 minutes

Effective time used 1 minutes

Notes

not defined yet

Task timeline

Code: 18:38:53 UTC, cpp, 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 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177

#include <unordered_map>
#include <cmath>
#include <algorithm>

using namespace std;

// helper function to avoid integer overflow when multiplying large ints
bool is_greater_or_equal(int v, int w, int X) {
    long long prod = v;
    prod *= w;
    return prod >= X;
}

// binary search to find the smaller suitable fence
int binary_search(int back, vector<int> &fences, int begin, int end, int X) {

    if (begin < end) {
        int mid = (begin + end) / 2;
        if (is_greater_or_equal(back, fences[mid], X)) {
            return binary_search(back, fences, begin, mid, X);
        } else {
            return binary_search(back, fences, mid + 1, end, X);
        }
    } else {
        return begin;
    }

}

int solution(vector<int> &A, int X) {

    const int N = A.size();

    if (N < 4) {
        return 0;
    }

    unordered_map<int, int> not_used_fences_map;
    for (int v : A) {
        if (not_used_fences_map.find(v) == not_used_fences_map.end())
            not_used_fences_map[v] = 1;
        else {
            not_used_fences_map[v]++;
        }
    }
    
    std::vector<int> not_used_fences;

    int max_fence = 0;
    for (const auto & elem : not_used_fences_map) {
        if (elem.second > 1) {
            max_fence = std::max(max_fence, elem.first);
            not_used_fences.push_back(elem.first);
        }
    }

    int result = 0;

    //make sense to check if a suitable solution even exists
    if (is_greater_or_equal(max_fence, max_fence, X)) {

        double x = X;

        // what is the min possible fence size given X and the max lenghty fence?
        int min_fances = static_cast<int>(std::ceil(x / max_fence));

        // filtering only viable fences
        vector<int> fences;
        for (int v : not_used_fences) {
            if (v >= min_fances) {
                fences.push_back(v);
            }
        }
        //sort fences (sure captain obvious)
        sort(fences.begin(), fences.end());

        const int SIZE = fences.size();

        for(int i = 0; i < SIZE; ++i) {

            int fence = fences[i];

            int smaller_suitable_fence_index = binary_search(fence, fences, i, SIZE - 1, X);

            result += SIZE - smaller_suitable_fence_index;

            // wait! wait! WTF is this sum above?
            // Okay, let me explain.
            // suppose we have 4 fences: 12, 13, 16 and 19 to build a greater or equal to 200 pen.
            // The table of combinations is:
            //       12	 13	 16	 19
            // 12	144	156	192	228
            // 13	156	169	208	247
            // 15	180	195	240	285
            // 16	192	208	256	304
            // 19	228	247	304	361

            // for first row where fence is 12 the smaller suitable fence is 19 because of 12x19 = 228.
            // for fence = 12, we cannot use a smaller fence like 16 because 12x16 is 192 which
            // is less than 200. So, we choose 19 as pair to 12 and sum 1 to result
            // the next row, fence = 13, the smaller suitable fence is 16 (13x16 is 208) and make result += 2
            // note that we start searching from the current fence index to avoid duplicates such (X, Y) and (Y, X) 

            // combinations such as (X, X) are only allowed if there are at least 4 fences available
            if (i == smaller_suitable_fence_index and not_used_fences_map[fences[i]] < 4) 
                result--;

            if (result >= 1'000'000'000) return -1;
            
        }

    }

    return result;

}

// solution achieves 100% correctness but only O(N**2) time complexity
int solution_brute_force(vector<int> &A, int X) {

    const int N = A.size();

    if (N < 4) {
        return 0;
    }

    unordered_map<int, int> not_used_fences_map;
    for (int v : A) {
        if (not_used_fences_map.find(v) == not_used_fences_map.end())
            not_used_fences_map[v] = 1;
        else {
            not_used_fences_map[v]++;
        }
    }
    
    std::vector<int> not_used_fences;

    int max_fence = 0;
    for (const auto & elem : not_used_fences_map) {
        if (elem.second > 1) {
            max_fence = std::max(max_fence, elem.first);
            not_used_fences.push_back(elem.first);
        }
    }

    int result = 0;

    double x = X;

    int min_fances = static_cast<int>(std::ceil(x / max_fence));
    
    std::vector<int> fences;

    for (int v : not_used_fences) {
        if (v >= min_fances) {
            fences.push_back(v);
        }
    }

    for (long long v : fences) {
        for (long long w : fences) {
            if (v == w && (not_used_fences_map[v] < 4 || not_used_fences_map[w] < 4)) {
                continue;
            }
            if (v < w) {
                continue;
            }
            if (v * w >= X) {
                result++;
                if (result >= 1'000'000'000) return -1;
            }
        }
    }

    return result;

}

Analysis

▶

example1
example test

✔

Code: 18:39:01 UTC, cpp, verify, result: Passed

#include <unordered_map>
#include <cmath>
#include <algorithm>

using namespace std;

// helper function to avoid integer overflow when multiplying large ints
bool is_greater_or_equal(int v, int w, int X) {
    long long prod = v;
    prod *= w;
    return prod >= X;
}

// binary search to find the smaller suitable fence
int binary_search(int back, vector<int> &fences, int begin, int end, int X) {

    if (begin < end) {
        int mid = (begin + end) / 2;
        if (is_greater_or_equal(back, fences[mid], X)) {
            return binary_search(back, fences, begin, mid, X);
        } else {
            return binary_search(back, fences, mid + 1, end, X);
        }
    } else {
        return begin;
    }

}

int solution(vector<int> &A, int X) {

    const int N = A.size();

    if (N < 4) {
        return 0;
    }

    unordered_map<int, int> not_used_fences_map;
    for (int v : A) {
        if (not_used_fences_map.find(v) == not_used_fences_map.end())
            not_used_fences_map[v] = 1;
        else {
            not_used_fences_map[v]++;
        }
    }
    
    std::vector<int> not_used_fences;

    int max_fence = 0;
    for (const auto & elem : not_used_fences_map) {
        if (elem.second > 1) {
            max_fence = std::max(max_fence, elem.first);
            not_used_fences.push_back(elem.first);
        }
    }

    int result = 0;

    //make sense to check if a suitable solution even exists
    if (is_greater_or_equal(max_fence, max_fence, X)) {

        double x = X;

        // what is the min possible fence size given X and the max lenghty fence?
        int min_fances = static_cast<int>(std::ceil(x / max_fence));

        // filtering only viable fences
        vector<int> fences;
        for (int v : not_used_fences) {
            if (v >= min_fances) {
                fences.push_back(v);
            }
        }
        //sort fences (sure captain obvious)
        sort(fences.begin(), fences.end());

        const int SIZE = fences.size();

        for(int i = 0; i < SIZE; ++i) {

            int fence = fences[i];

            int smaller_suitable_fence_index = binary_search(fence, fences, i, SIZE - 1, X);

            result += SIZE - smaller_suitable_fence_index;

            // wait! wait! WTF is this sum above?
            // Okay, let me explain.
            // suppose we have 4 fences: 12, 13, 16 and 19 to build a greater or equal to 200 pen.
            // The table of combinations is:
            //       12	 13	 16	 19
            // 12	144	156	192	228
            // 13	156	169	208	247
            // 15	180	195	240	285
            // 16	192	208	256	304
            // 19	228	247	304	361

            // for first row where fence is 12 the smaller suitable fence is 19 because of 12x19 = 228.
            // for fence = 12, we cannot use a smaller fence like 16 because 12x16 is 192 which
            // is less than 200. So, we choose 19 as pair to 12 and sum 1 to result
            // the next row, fence = 13, the smaller suitable fence is 16 (13x16 is 208) and make result += 2
            // note that we start searching from the current fence index to avoid duplicates such (X, Y) and (Y, X) 

            // combinations such as (X, X) are only allowed if there are at least 4 fences available
            if (i == smaller_suitable_fence_index and not_used_fences_map[fences[i]] < 4) 
                result--;

            if (result >= 1'000'000'000) return -1;
            
        }

    }

    return result;

}

// solution achieves 100% correctness but only O(N**2) time complexity
int solution_brute_force(vector<int> &A, int X) {

    const int N = A.size();

    if (N < 4) {
        return 0;
    }

    unordered_map<int, int> not_used_fences_map;
    for (int v : A) {
        if (not_used_fences_map.find(v) == not_used_fences_map.end())
            not_used_fences_map[v] = 1;
        else {
            not_used_fences_map[v]++;
        }
    }
    
    std::vector<int> not_used_fences;

    int max_fence = 0;
    for (const auto & elem : not_used_fences_map) {
        if (elem.second > 1) {
            max_fence = std::max(max_fence, elem.first);
            not_used_fences.push_back(elem.first);
        }
    }

    int result = 0;

    double x = X;

    int min_fances = static_cast<int>(std::ceil(x / max_fence));
    
    std::vector<int> fences;

    for (int v : not_used_fences) {
        if (v >= min_fances) {
            fences.push_back(v);
        }
    }

    for (long long v : fences) {
        for (long long w : fences) {
            if (v == w && (not_used_fences_map[v] < 4 || not_used_fences_map[w] < 4)) {
                continue;
            }
            if (v < w) {
                continue;
            }
            if (v * w >= X) {
                result++;
                if (result >= 1'000'000'000) return -1;
            }
        }
    }

    return result;

}

Analysis

▶

example1
example test

✔

Code: 18:39:05 UTC, cpp, final, score: 100

#include <unordered_map>
#include <cmath>
#include <algorithm>

using namespace std;

// helper function to avoid integer overflow when multiplying large ints
bool is_greater_or_equal(int v, int w, int X) {
    long long prod = v;
    prod *= w;
    return prod >= X;
}

// binary search to find the smaller suitable fence
int binary_search(int back, vector<int> &fences, int begin, int end, int X) {

    if (begin < end) {
        int mid = (begin + end) / 2;
        if (is_greater_or_equal(back, fences[mid], X)) {
            return binary_search(back, fences, begin, mid, X);
        } else {
            return binary_search(back, fences, mid + 1, end, X);
        }
    } else {
        return begin;
    }

}

int solution(vector<int> &A, int X) {

    const int N = A.size();

    if (N < 4) {
        return 0;
    }

    unordered_map<int, int> not_used_fences_map;
    for (int v : A) {
        if (not_used_fences_map.find(v) == not_used_fences_map.end())
            not_used_fences_map[v] = 1;
        else {
            not_used_fences_map[v]++;
        }
    }
    
    std::vector<int> not_used_fences;

    int max_fence = 0;
    for (const auto & elem : not_used_fences_map) {
        if (elem.second > 1) {
            max_fence = std::max(max_fence, elem.first);
            not_used_fences.push_back(elem.first);
        }
    }

    int result = 0;

    //make sense to check if a suitable solution even exists
    if (is_greater_or_equal(max_fence, max_fence, X)) {

        double x = X;

        // what is the min possible fence size given X and the max lenghty fence?
        int min_fances = static_cast<int>(std::ceil(x / max_fence));

        // filtering only viable fences
        vector<int> fences;
        for (int v : not_used_fences) {
            if (v >= min_fances) {
                fences.push_back(v);
            }
        }
        //sort fences (sure captain obvious)
        sort(fences.begin(), fences.end());

        const int SIZE = fences.size();

        for(int i = 0; i < SIZE; ++i) {

            int fence = fences[i];

            int smaller_suitable_fence_index = binary_search(fence, fences, i, SIZE - 1, X);

            result += SIZE - smaller_suitable_fence_index;

            // wait! wait! WTF is this sum above?
            // Okay, let me explain.
            // suppose we have 4 fences: 12, 13, 16 and 19 to build a greater or equal to 200 pen.
            // The table of combinations is:
            //       12	 13	 16	 19
            // 12	144	156	192	228
            // 13	156	169	208	247
            // 15	180	195	240	285
            // 16	192	208	256	304
            // 19	228	247	304	361

            // for first row where fence is 12 the smaller suitable fence is 19 because of 12x19 = 228.
            // for fence = 12, we cannot use a smaller fence like 16 because 12x16 is 192 which
            // is less than 200. So, we choose 19 as pair to 12 and sum 1 to result
            // the next row, fence = 13, the smaller suitable fence is 16 (13x16 is 208) and make result += 2
            // note that we start searching from the current fence index to avoid duplicates such (X, Y) and (Y, X) 

            // combinations such as (X, X) are only allowed if there are at least 4 fences available
            if (i == smaller_suitable_fence_index and not_used_fences_map[fences[i]] < 4) 
                result--;

            if (result >= 1'000'000'000) return -1;
            
        }

    }

    return result;

}

// solution achieves 100% correctness but only O(N**2) time complexity
int solution_brute_force(vector<int> &A, int X) {

    const int N = A.size();

    if (N < 4) {
        return 0;
    }

    unordered_map<int, int> not_used_fences_map;
    for (int v : A) {
        if (not_used_fences_map.find(v) == not_used_fences_map.end())
            not_used_fences_map[v] = 1;
        else {
            not_used_fences_map[v]++;
        }
    }
    
    std::vector<int> not_used_fences;

    int max_fence = 0;
    for (const auto & elem : not_used_fences_map) {
        if (elem.second > 1) {
            max_fence = std::max(max_fence, elem.first);
            not_used_fences.push_back(elem.first);
        }
    }

    int result = 0;

    double x = X;

    int min_fances = static_cast<int>(std::ceil(x / max_fence));
    
    std::vector<int> fences;

    for (int v : not_used_fences) {
        if (v >= min_fances) {
            fences.push_back(v);
        }
    }

    for (long long v : fences) {
        for (long long w : fences) {
            if (v == w && (not_used_fences_map[v] < 4 || not_used_fences_map[w] < 4)) {
                continue;
            }
            if (v < w) {
                continue;
            }
            if (v * w >= X) {
                result++;
                if (result >= 1'000'000'000) return -1;
            }
        }
    }

    return result;

}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N * log(N))

▶

example1
example test

✔

▶

extreme
corner cases, N <= 5

✔

▶

squares
includes squares, N <= 20

✔

▶

simple
simple tests, N <= 20

✔

▶

fib
Fibonacci numbers, N <= 20

✔

▶

small_repetitions
a few repeated values, N <= 50

✔

▶

small_random
random values, N <= 50

✔

▶

geometric_sequence
powers of 2, N <= 100

✔

▶

medium_continuous
continuous values, each appears 4 times, N <= 2,000

✔

▶

large_repetitions
many repeated values, N <= 100,000

✔

▶

max
continuous values, N <= 100,000

✔

▶

medium_random
random values, N <= 20,000

✔

▶

large_continuous
continuous values, each appears 4 times, N <= 80,000

✔

▶

large_random
random values, N <= 100,000

✔