Is Information Consistent?

Description:

Court is in session. We got a group of witnesses who have all taken an oath to tell the truth. The prosecutor is pointing at the defendants one by one and asking each witnesses a simple question – “guilty or not?”. The witnesses are allowed to respond in one of the following three ways:

  • I am sure he/she is guilty.
  • I am sure he/she is innocent.
  • I have no idea.

The prosecutor has a hunch that one of the witnesses might not be telling the truth so she decides to cross-check all of their testimonies and see if the information gathered is consistent, i.e. there are no two witnesses A and B and a defendant C such that Asays C is guilty while B says C is innocent.

Example

  • For
    evidences = [[ 0, 1, 0, 1], 
                 [-1, 1, 0, 0], 
                 [-1, 0, 0, 1]]
    

    the output should be
    isInformationConsistent(evidences) = true;

  • For
    evidences = [[ 1, 0], 
                 [-1, 0], 
                 [ 1, 1],
                 [ 1, 1]]
    

    the output should be
    isInformationConsistent(evidences) = false.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] array.array.integer evidences

    2-dimensional array of integers representing the set of testimonials. evidences[i][j] is the testimonial of the ith witness on the jth defendant. -1 means “innocent”, 0 means “no idea”, and 1 means “guilty”.

    Constraints:
    2 ≤ evidences.length ≤ 5,
    2 ≤ evidences[0].length ≤ 10.

  • [output] boolean

    true if the evidence is consistent, false otherwise.

Tests:
Solution(Java):

boolean isInformationConsistent(int[][] evidences) {
    for (int j = 0; j < evidences[0].length; j++) {
        boolean innocent = false,
                guilty = false;
        for (int i = 0; i < evidences.length; i++) {
            switch (evidences[i][j]) {
                case -1:
                    innocent = true;
                    break;
                case 1:
                    guilty = true;
                    break;
            }
        }

        if (innocent && guilty) {
            return false;
        }
    }

    return true;
}

Gravitation

Description:

You are given a vertical box divided into equal columns. Someone dropped several stones from its top through the columns. Stones are falling straight down at a constant speed (equal for all stones) while possible (i.e. while they haven’t reached the ground or they are not blocked by another motionless stone). Given the state of the box at some moment in time, find out which columns become motionless first.

Example

For

rows = ["#..##",
        ".##.#",
        ".#.##",
        "....."]

the output should be gravitation(rows) = [1, 4].

Check out the image below for better understanding:

Input/Output

  • [time limit] 3000ms (java)
  • [input] array.string rows

    A non-empty array of strings of equal length consisting only of #-s and .-s describing the box at a specific moment in time. Sharps represent stones, and dots represent empty cells. row[0] corresponds to the upper row. Last element of rowscorresponds to the ground level.

    Constraints:
    2 ≤ rows.length ≤ 10,
    2 ≤ rows[i].length ≤ 10.

  • [output] array.integer

    A sorted array containing numbers of all columns (leftmost column’s number is 0) in which movements will stop at the same second and earlier than in any other column. Assume that if there are no stones in a column then movement stops immediately, i.e. after 0 seconds.

Tests:
Solution(Java):

ArrayList<Integer> gravitation(String[] rows) {
    int minTimer = rows.length;
    ArrayList<Integer> answer = new ArrayList<>();
    for (int i = 0; i < rows[0].length(); i++) {
        int finish = rows.length - 1,
                timer = 0;
        for (int j = rows.length - 1; j >= 0; j--) {
            if (rows[j].charAt(i) == '#') {
                timer = finish - j;
                finish--;
            }
        }
        if (timer == minTimer) {
            answer.add(i);
        }
        if (timer < minTimer) {
            minTimer = timer;
            answer = new ArrayList<>();
            answer.add(i);
        }
    }

    return answer;
}

 

Polygon Perimeter

Description:

You have a rectangular white board with some black cells. The black cells create a connected black figure, i.e. it is possible to get from any black cell to any other one through connected adjacent (sharing a common side) black cells.

Find the perimeter of the black figure assuming that a single cell has unit length.

It’s guaranteed that there is at least one black cell on the table.

Example

  • For
    matrix = [[false, true,  true ],
              [true,  true,  false],
              [true,  false, false]]
    

    the output should be
    polygonPerimeter(matrix) = 12.

  • For
    matrix = [[true, true,  true],
              [true, false, true],
              [true, true,  true]]
    

    the output should be
    polygonPerimeter(matrix) = 16.

Input/Output

  • [time limit] 3000ms (java)
  • [input] array.array.boolean matrix

    A matrix of booleans representing the rectangular board where true means a blackcell and false means a white one.

    Constraints:
    2 ≤ matrix.length ≤ 5,
    2 ≤ matrix[0].length ≤ 5.

  • [output] integer

Tests:
Solution(Java):

int polygonPerimeter(boolean[][] matrix) {
    int perimeter = 0;
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            if (i - 1 < 0 && matrix[i][j]) {
                perimeter++;
            }
            if (i + 1 == matrix.length && matrix[i][j]) {
                perimeter++;
            }
            if (j - 1 < 0 && matrix[i][j]) {
                perimeter++;
            }
            if (j + 1 == matrix[0].length && matrix[i][j]) {
                perimeter++;
            }
            if (matrix[i][j] && 0 <= i - 1) {
                if (!matrix[i - 1][j]) {
                    perimeter++;
                }
            }
            if (matrix[i][j] && i + 1 < matrix.length) {
                if (!matrix[i + 1][j]) {
                    perimeter++;
                }
            }
            if (matrix[i][j] && 0 <= j - 1) {
                if (!matrix[i][j - 1]) {
                    perimeter++;
                }
            }
            if (matrix[i][j] && j + 1 < matrix[0].length) {
                if (!matrix[i][j + 1]) {
                    perimeter++;
                }
            }
        }
    }
    return perimeter;
}

 

Contours Shifting

Description:

Mark got a rectangular array matrix for his birthday, and now he’s thinking about all the fun things he can do with it. He likes shifting a lot, so he decides to shift all of its i-contours in a clockwise direction if i is even, and counterclockwise if i is odd.

Here is how Mark defines i-contours:

  • the 0-contour of a rectangular array as the union of left and right columns as well as top and bottom rows;
  • consider the initial matrix without the 0-contour: its 0-contour is the 1-contour of the initial matrix;
  • define 2-contour, 3-contour, etc. in the same manner by removing 0-contours from the obtained arrays.

Implement a function that does exactly what Mark wants to do to his matrix.

Example

  • For
    matrix = [[ 1,  2,  3,  4],
               [ 5,  6,  7,  8],
               [ 9, 10, 11, 12],
               [13, 14, 15, 16],
               [17, 18, 19, 20]]
    

    the output should be

    contoursShifting(matrix) = [[ 5,  1,  2,  3],
                                 [ 9,  7, 11,  4],
                                 [13,  6, 15,  8],
                                 [17, 10, 14, 12],
                                 [18, 19, 20, 16]]
    
  • For matrix = [[238, 239, 240, 241, 242, 243, 244, 245]],
    the output should be
    contoursShifting(matrix) = [[245, 238, 239, 240, 241, 242, 243, 244]].

    Note, that if a contour is represented by a 1 × n array, its center is considered to be below it.

  • For
    matrix = [[238],
               [239],
               [240],
               [241],
               [242],
               [243],
               [244],
               [245]]
    

    the output should be

    contoursShifting(matrix) = [[245],
                                 [238],
                                 [239],
                                 [240],
                                 [241],
                                 [242],
                                 [243],
                                 [244]]
    

    If a contour is represented by an n × 1 array, its center is considered to be to the leftof it.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] array.array.integer matrix

    Constraints:
    1 ≤ matrix.length ≤ 100,
    1 ≤ matrix[i].length ≤ 100,
    1 ≤ matrix[i][j] ≤ 1000.

  • [output] array.array.integer

    The given matrix with its contours shifted.

Tests:
Solution(C#):

int[][] contoursShifting(int[][] matrix) {
    int[][] temp = matrix.Select(x => x.ToArray()).ToArray();
    int len = Math.Min(matrix.Length,matrix[0].Length);
    for(int i=0;i<(int)(Math.Ceiling((double)len/2));i++){
        matrix = shifting(matrix, temp, i, i*2==matrix[0].Length-1||i*2==matrix.Length-1, i%2==1, matrix.Length<matrix[0].Length);
    }
    return matrix;
}
int[][] shifting(int[][] matrix, int[][] temp, int i, bool single, bool inversed, bool forward) {
    if(single){
        if(forward){            
            if(inversed){
                for(int j=i;j<matrix[0].Length-i-1;j++){
                   matrix[i][j]=temp[i][j+1];
                }
                matrix[i][matrix[0].Length-i-1]=temp[i][i];
            }else{
                for(int j=i;j<matrix[0].Length-i-1;j++){
                   matrix[i][j+1]=temp[i][j];
                }
                matrix[i][i]=temp[i][matrix[0].Length-i-1];
            }
        }else{
            if(inversed){                
                for(int j=i;j<matrix.Length-i-1;j++){
                   matrix[j][i]=temp[j+1][i];
                }
                matrix[matrix.Length-i-1][i]=temp[i][i];
            }else{
                for(int j=i;j<matrix.Length-i-1;j++){
                   matrix[j+1][i]=temp[j][i];
                }
                matrix[i][i]=temp[matrix.Length-i-1][i];
            }
        }        
    }else{
        if(inversed){
            for(int j=i;j<matrix[0].Length-i-1;j++){
                matrix[i][j]=temp[i][j+1];
            }
            for(int j=i;j<matrix.Length-i;j++){
                matrix[j][matrix[0].Length-i-1]=temp[j+1][matrix[0].Length-i-1];
            }
            for(int j=i;j<matrix[0].Length-i-1;j++){
                matrix[matrix.Length-i-1][j+1]=temp[matrix.Length-i-1][j];
            }
            for(int j=i;j<matrix.Length-i-1;j++){
                matrix[j+1][i]=temp[j][i];
            }
        }else{
            for(int j=i;j<matrix[0].Length-i-1;j++){
                matrix[i][j+1]=temp[i][j];
            }
            for(int j=i+1;j<matrix.Length-i;j++){
                matrix[j][matrix[0].Length-i-1]=temp[j-1][matrix[0].Length-i-1];
            }
            for(int j=i;j<matrix[0].Length-i-1;j++){
                matrix[matrix.Length-i-1][j]=temp[matrix.Length-i-1][j+1];
            }
            for(int j=i;j<matrix.Length-i-1;j++){
                matrix[j][i]=temp[j+1][i];
            }
        }
    }
    return matrix;
}

 

Box Blur

Description:

Last night you had to study, but decided to party instead. Now there is a black and white photo of you that is about to go viral. You cannot let this ruin your reputation, so you want to apply box blur algorithm to the photo to hide its content.

The algorithm works as follows: each pixel x in the resulting image has a value equal to the average value of the input image pixels’ values from the 3 × 3 square with the center at x. All pixels at the edges are cropped.

As pixel’s value is an integer, all fractions should be rounded down.

Example

For

image = [[1, 1, 1], 
         [1, 7, 1], 
         [1, 1, 1]]

the output should be boxBlur(image) = [[1]].

In the given example all boundary pixels were cropped, and the value of the pixel in the middle was obtained as (1 + 1 + 1 + 1 + 7 + 1 + 1 + 1 + 1) / 9 = 15 / 9 = ~rounded down~ = 1.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] array.array.integer image

    An image is stored as a rectangular matrix of non-negative integers.

    Constraints:
    3 ≤ image.length ≤ 10,
    3 ≤ image[0].length ≤ 10,
    0 ≤ image[i][j] ≤ 255.

  • [output] array.array.integer

    A blurred image.

Tests:
Solution(C#):

int[][] boxBlur(int[][] image) {
    int[][] result = new int[image.length-2][image[0].length-2];
    for (int i =1; i < image.length-1; i++)
        for (int j = 1; j < image[0].length-1; j++) {
            int sum=0;
            for(int ii=i-1;ii<=i+1;ii++) {
                for(int jj=j-1;jj<=j+1;jj++) {
                    sum+=image[ii][jj];
                }               
            }
            result[i-1][j-1]=sum/9;
        }
    return result;
}


 

Minesweeper

Description:

In the popular Minesweeper game you have a board with some mines and those cells that don’t contain a mine have a number in it that indicates the total number of mines in the neighboring cells. Starting off with some arrangement of mines we want to create a Minesweeper game setup.

Example

For

matrix = [[true, false, false],
          [false, true, false],
          [false, false, false]]

the output should be

minesweeper(matrix) = [[1, 2, 1],
                       [2, 1, 1],
                       [1, 1, 1]]       

Check out the image below for better understanding:

Input/Output

  • [time limit] 3000ms (cs)
  • [input] array.array.boolean matrix

    A non-empty rectangular matrix consisting of boolean values – true if the corresponding cell contains a mine, false otherwise.

    Constraints:
    2 ≤ matrix.length ≤ 5,
    2 ≤ matrix[0].length ≤ 5.

  • [output] array.array.integer

    Rectangular matrix of the same size as matrix each cell of which contains an integer equal to the number of mines in the neighboring cells. Two cells are called neighboring if they share at least one corner.

Tests:
Solution(Java):

int[][] minesweeper(boolean[][] matrix) {
    int[][] sol = new int[matrix.length][matrix[0].length];
    for (int i = 0; i < matrix.length; i++)
        for (int j = 0; j < matrix[0].length; j++)
            for (int ii = Math.max(0,i - 1); ii <= Math.min(i + 1,matrix.length-1) ; ii++)
                for (int jj = Math.max(0,j - 1); jj <= Math.min(j + 1,matrix[0].length-1); jj++) {
                    if (matrix[ii][jj] && (i!=ii || jj!=j)) {
                        sol[i][j]++;                        
                    }
                }

    return sol;
}

 

Sudoku

Description:

Sudoku is a number-placement puzzle. The objective is to fill a 9 × 9 grid with digits so that each column, each row, and each of the nine 3 × 3 sub-grids that compose the grid contains all of the digits from 1 to 9.

This algorithm should check if the given grid of numbers represents a correct solution to Sudoku.

Example

For the first example below, the output should be true. For the other grid, the output should be false: each of the nine 3 × 3 sub-grids should contain all of the digits from 1 to 9.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] array.array.integer grid

    A matrix representing 9 × 9 grid already filled with numbers.

  • [output] boolean

    true if the given grid represents a correct solution to Sudoku, false otherwise.

Tests:
Solution(Java):

boolean sudoku(int[][] grid) {
    class Helper {
        boolean checkBlock(ArrayList<Integer> block) {
            ArrayList<Integer> sample = new ArrayList<>();
            for (int i = 1; i < 10; i++) {
                sample.add(i);
            }
            Collections.sort(block);
            if (block.equals(sample)) {
                return  true ;
            }
            return false;
        }
    };
    Helper h = new Helper();

    ArrayList<ArrayList<ArrayList<Integer>>> subgrids = new ArrayList<>();

    for (int i = 0; i < 3; i++) {
        ArrayList<ArrayList<Integer>> tmp = new ArrayList<>();
        subgrids.add(tmp);
        for (int j = 0; j < 3; j++) {
            ArrayList<Integer> tmp2 = new ArrayList<>();
            subgrids.get(i).add(tmp2);
        }
    }

    for (int i = 0; i < 9; i++) {
        ArrayList<Integer> horizontal = new ArrayList<>(),
                           vertical = new ArrayList<>();
        for (int j = 0; j < 9; j++) {
            horizontal.add(grid[i][j]);
            vertical.add(grid[j][i]);
            subgrids.get(i / 3).get(j / 3).add(grid[i][j]);
        }
        if (!h.checkBlock(horizontal)) {
            return false;
        }
        if (!h.checkBlock(vertical)) {
            return false;
        }
    }

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (!h.checkBlock(subgrids.get(i).get(j))) {
                return false;
            }
        }
    }

    return true;
}