PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Evgeniy Artemov
Tester: Xiuhan Wang
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Pigeonhole principle, Constructive algorithms and Case-based Analysis.
PROBLEM:
Given two integers N and M, find out any matrix with N rows and M columns using as less distinct numbers as possible, such that for all cell, all values of neighbors of that cell are pairwise distinct.
SUPER QUICK EXPLANATION
- In all cases, it can be seen that if K is the maximum number of neighbors for any cell, It is not possible to have any valid table using less than K distinct numbers due to Pigeonhole principle.
- Turns out, it is always possible to make a valid table using K numbers. One possible construction is noticing that ith position in the row should have values different than (i-2)th position and (i+2)th position in the same row. Same goes for columns. Constructions exist based on this condition only.
EXPLANATION
Considering a N*M table, we can see that if the maximum number of neighbors any cell has in a table is K, there cannot exist any valid table using less than K distinct values. The reason is, that if we take K values out of distinct < K values, It is guaranteed to have at least one value occurring more than once, which means that the values of neighbors of that particular cell are not pairwise distinct. Hence, the table is invalid. Refer Pigeonhole principle for proof.
Thus, we need to find a way to fill the table using K values.
General case
In general case where we have K = 4, occurs when both N, M \geq 3.
Here, in every row or column, we need the first element to differ from the third element in the row, the second element should differ from the fourth element, the third element should differ from the fifth element and so on. If we choose the fifth element to be the same as the first element, it shall make no difference.
It is recommended to try a few ways to fill a 4*4 table and then trying to extend it either way.
Here, it is possible to have different constructions than the one mentioned here, so feel free to share yours.
One possible way to fill a 4*4 table is
1 1 2 2
3 4 4 3
2 2 1 1
4 3 3 4
Now, it can be easily seen, that we can just keep appending rows and columns without causing any conflict for any cell, thus efficiently generating our table.
Click to view
A valid 6*8 table.
1 1 2 2 1 1 2 2
3 4 4 3 3 4 4 3
2 2 1 1 2 2 1 1
4 3 3 4 4 3 3 4
1 1 2 2 1 1 2 2
3 4 4 3 3 4 4 3
Special cases
Assuming N \leq M. Values N and M can be swapped if otherwise.
-
If N equals one.
Here, if M \leq 2 each cell has at most one neighbor, and thus, we can just assign 1 to both cells.
If M > 2, we need the first element to differ from third, second from fourth and so on. So, we can just assign the first four values as1 1 2 2and from the fifth element, ith value is assigned same value as (i-4)th element. -
If N equals two.
Here too, if M == 2, valid table exist with K = 2.
Otherwise, we need at least three distinct values. A simple construction being ith element in both rows being assigned as (i-3)th element, first three elements being1 2 3.
This covers all cases where K < 4. All other case have N, M \geq 3 which implies K == 4 as seen above.
Time Complexity
Time complexity is O(N*M) per test case.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 
