PROBLEM LINK:
Author: Sergey Nagin
Tester: Istvan Nagy
Editorialist: Miguel Oliveira
DIFFICULTY:
Medium
PREREQUISITES:
None
PROBLEM:
Given a matrix A of N * M integers, find the maximum number of times any integer appears repeated in the intersection of a line and column.
EXPLANATION:
Subtask1
In the first subtask, we have N, M \leq 10. So, we can just compute the function F for all cells. For every combination of rows and columns, we check what is the maximum number of repetitions of any integer.
A naive approach to count the number of repetitions is to do the following algorithm:
for every row R do
for every column C do:
numbers <- array with all numbers in R and C without duplicating the common element
for each value in numbers do:
count = 0
for each value2 in numbers do:
if value == value2 then
count = count + 1
result = max(count) over all combinations R, C
The numbers array contains N+M-1 integers. Considering N=M, this approach has a O(N^4) time complexity.
Subtask 2
In the second subtask, N, M \leq 100 and the above approach would be too slow. However, we can easily improve the counting part. We know that all integers are positive and up to 10^6, so we can use an array to count the number of times each integer appears. This brings down the time complexity to O(N^3) which was fast enough for this subtask.
Subtask 3
The original constraints are N \times M \leq 10^6 which means we need a faster approach.
The key insight is to note that we can process the rows and columns independently. For each integer in the matrix, we want to know the maximum number of times it appears in a row and in a column. In case it appears in the intersection of a row and column with maximum number of repetitions, we need to subtract 1 to the result.
We will process each distinct integer in the matrix once and find what are the rows and the columns where each integer appears the most. To do this, we can process matrix A and fill the positions (rows and columns) where each in integer appears. Save this information in lists lines and columns for each integer.
If we process each line at a time, the lines list will be automatically sorted in increasing order.
for i in 1..N
for j in 1..M
lines[ A[i][j] ].add(i)
Similarly, if we process each column at a time, the columns list will also be sorted.
for j in 1..M
for i in 1..N
columns[ A[i][j] ].add(j)
Then, to count the number of times an integer appears in a row or columns, we can just count the repeated consecutive elements in these lists. Note that the total size of these lists is N \times M.
The last step is to check if the row and column with maximum repetitions have this number in their intersection. To do this, we keep track of all rows and columns with maximum number of repetitions. Finally, we check if any combination of these best rows and columns do not have it in the intersection. If any combination does not, then the number of repetitions is maxR + maxC, otherwise it is maxR + maxC - 1.
Over all distinct numbers, count the maximum repetitions in O(N \times M). Also, we only check O(N \times M) combinations of best rows and columns. So the total time complexity is O(N \times M).
