SEATL - Editorial

PROBLEM LINK:

Practice
Contest

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).

Sample Solutions

Author
Tester
Editorialist

2 Likes

does the answer given in Subtask 1 give 10 pts, i can see there are large number of test cases and would result in TLE .

Yes, as long as we use arrays. Using hash tables or binary search trees could add overheads that induce TLE. Sample implementation - https://www.codechef.com/viewsolution/9426088

1 Like

Cannot access the Author, Tester, Editorial’s solutions. Otherwise, a very nice editorial. Thank you :smiley:

where is the sample solutions.when i click the link on Author or Tester, it is still at this link

Thanks i got it, i was trying a lot of that kind of approach and endded up in TLE , and the overall complexity would be more than O(NxM) ,doesnt it depend on the number of distinct characters

Exactly the same Approach…

https://www.codechef.com/viewsolution/9382592

Liked the problem

3 Likes

I think these will be available soon, my code is at https://www.codechef.com/viewsolution/9426114

1 Like

I think these will be available soon, my code is at https://www.codechef.com/viewsolution/9426114

Its written that sum of n*m <= 10^6 over all test cases, which means that ‘t’ should’ve been fairly large in smaller subtasks :stuck_out_tongue:

1 Like

Thanks for the question , would have better if question contains some good algorithm/logic than brute-force(kinda).

I got only 30 pts, could not figure out the reason.
I was using approach for 100 pts using (multisets of pair). I inserted each element with row number in “rows” multiset and with column number in “columns” multiset. Then iterated over all elements finding the row with the max frequency of each element, then storing these row numbers with max frequency in another vector.The same procedure for columns.

This is my solution
https://www.codechef.com/viewsolution/9366100

Any help would be appreciated

1 Like

I got only 30 pts, could not figure out the reason.
I was using approach for 100 pts using (multisets of pair). I inserted each element with row number in “rows” multiset and with column number in “columns” multiset. Then iterated over all elements finding the row with the max frequency of each element, then storing these row numbers with max frequency in another vector.The same procedure for columns.

This is my solution
https://www.codechef.com/viewsolution/9366100

Any help would be appreciated

2 Likes

Same approach :

Implementation

1 Like

Even a well implemented code with maps can pass for 100 points. AC Solution

Overall complexity is O(nm(logn+logm))

1 Like

i have used approx same approch with O[n*m] complexity but i dont know why i am getting wrong ans
please any one help to solve this 9427788

i think inserting in multiset would be taking larger time. Think for the case when all numbers are distinct and N*M is 10^6. This happened with me when i was using set.

1 Like

AC after 100+ submissions.
Really tough one though. :smiley:

Here’s how I cracked this problem : mysol

1 Like

how is it that the iterating over all max row and max column combinations of each number amounts to only NXM ? Isn’t it possible that a single row can be the max row for many numbers and similarly for columns? for example this 4X4 matrix:
{1 1 2 2},
{2 2 1 1},
{1 1 2 2},
{2 2 1 1}

Note I mentioned O(NM), so within a constant factor of N*M).
The key is that the more times a row/column is best for a specific number, the less distinct numbers we have. While in your example both 1 and 2 have 4 options for each row/column, there are only 2 numbers to consider.