DistinctGridEasy

SRM 720 · 2017-07-25 · by lg5293

SRM 720 · 2017-07-25 · by lg5293 · Brute Force

Show categories

Class Name: DistinctGridEasy

Return Type: String

Method Name: checkGrid

Arg Types: (int, int, vector<int>)

Problem Statement

You are given ints n,k and a int[] grid.

Cat Noku has constructed a 2d matrix of integers with dimensions n by n. Each element of the matrix is between 0 and k-1, inclusive. You are given the 2d matrix in a special format, in the int[] grid. grid has exactly n * n elements. The value grid[ i*n+j ] corresponds to the entry in the i-th row and j-th column of Cat Noku's matrix for all 0 ≤ i,j ≤ n-1. You would like to check if each row and column has exactly k distinct integers. If this is the case, return the String "Good", otherwise, return "Bad". (Note that the return value is case-sensitive.)

Constraints

n will be between 1 and 50, inclusive.
k will be between 1 and n, inclusive.
grid will contain exactly n*n elements.
Each element of grid will be between 0 and k-1, inclusive.

Examples

3
3
{
0,1,2,
1,2,0,
2,0,1
}
Returns: "Good"

Here, Cat Noku has a 3 by 3 grid, and he wants to check whether each row and column has 3 distinct integers. In this case, the condition is satisfied, so we return "Good".

3
3
{
0,1,2,
1,2,0,
2,0,0
}
Returns: "Bad"

In this case, this grid is not good because the last column only has 2 distinct integers.

5
2
{
0,0,0,0,1,
0,1,0,0,0,
0,0,1,0,0,
1,0,0,0,0,
0,0,0,1,0
}
Returns: "Good"

5
3
{
2,2,0,0,1,
0,1,2,2,0,
0,2,1,0,0,
1,0,0,0,2,
0,0,2,1,0
}
Returns: "Good"

7
4
{
3,2,1,0,3,2,1,
3,2,1,3,2,1,2,
2,0,3,1,1,0,3,
1,3,0,2,0,3,0,
0,3,1,2,3,2,1,
1,1,1,2,1,0,3,
3,1,2,0,3,2,3
}
Returns: "Bad"

Submissions are judged against all 67 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class DistinctGridEasy with a public method string checkGrid(int n, int k, vector<int> grid) · 67 test cases · 2 s / 256 MB per case