Test results - Codility

Tasks Details

hard

1. CountriesCount

Count the number of different countries that a map contains.

100%

A rectangular map consisting of N rows and M columns of square areas is given. Each area is painted with a certain color.

Two areas on the map belong to the same country if the following conditions are met:

they have the same color;

it is possible to travel from one area to the other orthogonally (that is, by moving only north, south, west or east) without moving over areas of a different color.

The map can be described by a zero-indexed matrix A consisting of N rows and M columns of integers. The color of each area is described by the corresponding element of the matrix. Two areas have the same color if and only if their corresponding matrix elements have the same value.

For example, consider the following matrix A consisting of seven rows and three columns:

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

Matrix A describes a map that is colored with five colors. The areas on the map belong to eleven different countries (C1−C11), as shown in the following figure:

Write a function

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

that, given a zero-indexed matrix A consisting of N rows and M columns of integers, returns the number of different countries to which the areas of the map described by matrix A belong.

For example, given matrix A consisting of seven rows and three columns corresponding to the example above, the function should return 11.

Write an efficient algorithm for the following assumptions:

N and M are integers within the range [1..300,000];

the number of elements in matrix A is within the range [1..300,000];

each element of matrix A is an integer within the range [−1,000,000,000..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: 01:15:10 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

#include <stack>
#include <list>

using namespace std;

void flood(vector<vector<int>> &A, stack<int> &stack, 
            vector<bool> &pendings, 
            const int height, const int width) {

    if (!stack.empty()) {

        int pointer = stack.top();
        stack.pop();

        if (pendings[pointer]) {

            pendings[pointer] = false;

            int i = pointer % height;
            int j = pointer / height;

            int color = A[i][j];

            if (i > 0) {
                if (A[i - 1][j] == color) {
                    int element_index = j*height + (i - 1);
                    if (pendings[element_index]) {
                        stack.push(element_index);
                    }
                }
            }
            
            if (i < height - 1) {
                if (A[i + 1][j] == color) {
                    int element_index = j*height + (i + 1);
                    if (pendings[element_index]) {
                        stack.push(element_index);
                    }
                }
            }

            if (j > 0) {
                if (A[i][j - 1] == color) {
                    int element_index = (j - 1) * height + i;
                    if (pendings[element_index]) {
                        stack.push(element_index);
                    }
                }
            }

            if (j < width - 1) {
                if (A[i][j + 1] == color) {
                    int element_index = (j + 1) * height + i;
                    if (pendings[element_index]) {
                        stack.push(element_index);
                    }
                }
            }
        }
        
    }

}

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

    stack<int> stack;

    int N = A.size(); // matrix height
    int M = A[0].size(); // matrix width

    int SIZE = N * M;

    vector<bool> pendings(SIZE, true);

    int result = 0;

    int pointer = 0;

    while (pointer < SIZE) {

        if (pendings[pointer]) {

            stack.push(pointer);

            while (!stack.empty())
                flood(A, stack, pendings, N, M);

            result++;
        }

        pointer++;

    }

    return result;

}

Analysis

▶

example

✔

Code: 01:15:16 UTC, cpp, verify, result: Passed

#include <stack>
#include <list>

using namespace std;

void flood(vector<vector<int>> &A, stack<int> &stack, 
            vector<bool> &pendings, 
            const int height, const int width) {

    if (!stack.empty()) {

        int pointer = stack.top();
        stack.pop();

        if (pendings[pointer]) {

            pendings[pointer] = false;

            int i = pointer % height;
            int j = pointer / height;

            int color = A[i][j];

            if (i > 0) {
                if (A[i - 1][j] == color) {
                    int element_index = j*height + (i - 1);
                    if (pendings[element_index]) {
                        stack.push(element_index);
                    }
                }
            }
            
            if (i < height - 1) {
                if (A[i + 1][j] == color) {
                    int element_index = j*height + (i + 1);
                    if (pendings[element_index]) {
                        stack.push(element_index);
                    }
                }
            }

            if (j > 0) {
                if (A[i][j - 1] == color) {
                    int element_index = (j - 1) * height + i;
                    if (pendings[element_index]) {
                        stack.push(element_index);
                    }
                }
            }

            if (j < width - 1) {
                if (A[i][j + 1] == color) {
                    int element_index = (j + 1) * height + i;
                    if (pendings[element_index]) {
                        stack.push(element_index);
                    }
                }
            }
        }
        
    }

}

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

    stack<int> stack;

    int N = A.size(); // matrix height
    int M = A[0].size(); // matrix width

    int SIZE = N * M;

    vector<bool> pendings(SIZE, true);

    int result = 0;

    int pointer = 0;

    while (pointer < SIZE) {

        if (pendings[pointer]) {

            stack.push(pointer);

            while (!stack.empty())
                flood(A, stack, pendings, N, M);

            result++;
        }

        pointer++;

    }

    return result;

}

Analysis

▶

example

✔

Code: 01:15:20 UTC, cpp, final, score: 100

#include <stack>
#include <list>

using namespace std;

void flood(vector<vector<int>> &A, stack<int> &stack, 
            vector<bool> &pendings, 
            const int height, const int width) {

    if (!stack.empty()) {

        int pointer = stack.top();
        stack.pop();

        if (pendings[pointer]) {

            pendings[pointer] = false;

            int i = pointer % height;
            int j = pointer / height;

            int color = A[i][j];

            if (i > 0) {
                if (A[i - 1][j] == color) {
                    int element_index = j*height + (i - 1);
                    if (pendings[element_index]) {
                        stack.push(element_index);
                    }
                }
            }
            
            if (i < height - 1) {
                if (A[i + 1][j] == color) {
                    int element_index = j*height + (i + 1);
                    if (pendings[element_index]) {
                        stack.push(element_index);
                    }
                }
            }

            if (j > 0) {
                if (A[i][j - 1] == color) {
                    int element_index = (j - 1) * height + i;
                    if (pendings[element_index]) {
                        stack.push(element_index);
                    }
                }
            }

            if (j < width - 1) {
                if (A[i][j + 1] == color) {
                    int element_index = (j + 1) * height + i;
                    if (pendings[element_index]) {
                        stack.push(element_index);
                    }
                }
            }
        }
        
    }

}

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

    stack<int> stack;

    int N = A.size(); // matrix height
    int M = A[0].size(); // matrix width

    int SIZE = N * M;

    vector<bool> pendings(SIZE, true);

    int result = 0;

    int pointer = 0;

    while (pointer < SIZE) {

        if (pendings[pointer]) {

            stack.push(pointer);

            while (!stack.empty())
                flood(A, stack, pendings, N, M);

            result++;
        }

        pointer++;

    }

    return result;

}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N*M)

▶

example

✔

▶

small_1x1

✔

▶

positive_negative_zeros

✔

▶

small_2x2

✔

▶

small_3x3

✔

▶

matrix_12x10

✔

▶

matrix_10x10_labyrinth

✔

▶

matrix_wide

✔

▶

large_numbers

✔

▶

anti_heuristics

✔

▶

medium_matrix

✔

▶

medium_square_matrix

✔

▶

medium_horizontal_matrix

✔

▶

large_square_one_country

✔

▶

max_matrix

✔

▶

max_one_country

✔