Editorial for COCI '07 Contest 5 #4 Avogadro
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.
Submitting an official solution before solving the problem yourself is a bannable offence.
The algorithm we use is:
- If all three rows contain the same numbers, we are finished. If not, there is at least one number
which does not occur in every row.
- Find all columns that contain
- Return to step 1.
Although the algorithm is conceptually simple, efficiently implementing it is not.
We maintain a set of numbers that need to be removed from the table. First we put into the set all numbers not occurring in all three rows. Then we pick the elements from the set one by one and delete columns that contain the chosen elements.
To quickly locate all columns containing a number, we preprocess the table, writing for each number the columns it occurs in. We also keep track of how many times a number occurs in each row.
When deleting a column, we decrease the occurrences of each number in the three rows and, when one of those counters becomes zero for any number and any row, mark that number for deletion.
Comments