Editorial for COCI '23 Contest 1 #3 AN2DL

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Prepared by: Martina Licul

To solve the first subtask, you only needed to determine the largest number in the table of size $n \times m$ ~n \times m~.

To solve the second subtask, you could iterate through all subtables of size $r \times s$ ~r \times s~ and find the largest number in each of them by looping through all the elements in that subtable. The overall complexity of this approach is $\mathcal O(nmrs)$ ~\mathcal O(nmrs)~.

To solve the third subtask, you break the problem into two phases: in the first phase, you determine the table you would get if you considered a frame of size $1 \times s$ ~1 \times s~, and in the second phase, you create a new table using a frame of size $r \times 1$ ~r \times 1~ on the table created in the first phase. The result is the table you are looking for. Let's describe the process for each phase.

In the first phase, you can solve it row by row. The first number you would write in the $i$ ~i~-th row of the table is the largest number among the numbers $a_{i,1}, a_{i,2}, \dots, a_{i,s}$ ~a_{i,1}, a_{i,2}, \dots, a_{i,s}~. The second number you write is the largest number among the numbers $a_{i,2}, a_{i,3}, \dots, a_{i,s+1}$ ~a_{i,2}, a_{i,3}, \dots, a_{i,s+1}~. The set of numbers you consider for determining the first and second number differs only in the elements $a_{i,1}$ ~a_{i,1}~ and $a_{i,s+1}$ ~a_{i,s+1}~; all other elements are the same. Therefore, you can use a data structure like a multiset, where you can insert elements in $\mathcal O(\log n)$ ~\mathcal O(\log n)~ and find the largest element in $\mathcal O(1)$ ~\mathcal O(1)~. You insert the first $s$ ~s~ elements of the first row into the structure and write down the largest among them. Then, you remove $a_{1,1}$ ~a_{1,1}~ from the structure and add $a_{1,s+1}$ ~a_{1,s+1}~. Write down the largest among them as the second number in the first row of the new table. By repeating this process to the end of the row, for each row, you get the table for the first phase.

In the second phase, you repeat a similar process for the columns using a similar data structure. This process results in the final table. The overall complexity of this approach is $\mathcal O(nm \log n)$ ~\mathcal O(nm \log n)~.

To solve the fourth subtask, you need to speed up the approach from the third subtask. Instead of inserting an element into a structure in $\mathcal O(\log n)$ ~\mathcal O(\log n)~, you want to do it in $\mathcal O(1)$ ~\mathcal O(1)~. You can use a data structure called a monotonic queue, which allows you to do this in $\mathcal O(1)$ ~\mathcal O(1)~. You can learn more about it on this link. The overall complexity of this approach is $\mathcal O(nm)$ ~\mathcal O(nm)~.

Comments

There are no comments at the moment.