SRM 720, D2, 250-Pointer (DistinctGridEasy)

James S. Plank

Tue Oct 15 16:12:35 EDT 2019

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: September, 2017
Competitors who opened the problem: 311
Competitors who submitted a solution: 267
Number of correct solutions: 188
Accuracy (percentage correct vs those who opened): 60.4%
Average Correct Time: 15 minutes, 28 seconds.

In case Topcoder's servers are down

(Please use the workflow in the problem Cryptography). There is a tests.sh program which, when you run it, should create output equal to answers.txt. Mine ran in 3 seconds.

Here is a summary of the problem:

You are given two numbers, n and k and a vector grid, which contains n*n numbers which between 0 and k-1.
You are to treat grid as an n by n grid, where the number in row i and column j is in index (i*n+j) of grid.
If every row and column of the grid contains exactly k distinct numbers, return the string "Good".
To be more precise, a row like { 0, 1, 1, 1, 1, 3 } has three distinct numbers: 0, 1 and 3.
Otherwise, return "Bad".
Topcoder has n and k limited to 50. My testing program goes up to 150.

The examples

Example	n	k	grid	Answer
0	3	3	{ 0,1,2, 1,2,0, 2,0,1 }	"Good"
1	3	3	{ 0,1,2, 1,2,0, 2,0,0 }	"Bad"
2	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 }	"Good"
3	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 }	"Good"
4	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 }	"Bad"

Given a collection of n values, how do you determine how many of them are distinct? If I wanted a solution that's easy to program, I'd use a set: Insert each value into the set. Then the size of the set is the number of distinct elements.

Armed with that knowledge, you should have two doubly-nested for loops. Here is the first:

For every row of grid:
Clear the set.
Insert each element in the row into the set.
Check the set's size. If it doesn't equal k return "Bad."

The second set of loops does the same thing, but with columns instead of rows.

If you complete both sets of loops, then the answer is "Good".

The running time of this is O(n² log n). That's because you loop n times for each row and each column, and on each iteration, you create a set of n elements -- that's O(n log n) for each iteration, and there are 2n iterations: O(n² log n).

You can make this faster by using a vector with k elements. On each iteration, zero the vector, and then for each row, increment the vector for each element in the row. If the vector has any zero's then return "Bad". If you successfully look at every row and column, then return "Good."

This is now O(n²), because again, you have 2n iterations, but now each iteration is doing O(n) work.

(I'll point out that you can also achieve O(n²) by using an unordered_set instead of a set in the description above. Although both are O(n²), which of the solutions do you think will be faster: vector or unordered_set?).