Please read the new rule regarding the restriction on the use of AI tools. ×

A DOUBT IN KONIG THEOREM PROBLEM

Revision en3, by Ritu_1149, 2024-10-03 13:16:43

Cole, volunteers as a shelver at the school library, where the encyclopedias need to be re- organized. After re-organizing all the encyclopedias, Cole realizes that some of the encyclopedias are shelved in the wrong order. To fix the mistake, Cole decides to remove all the encyclopedias from the n by m shelf. While reshelving the encyclopedias, Cole realizes that the most efficient way to reshelve the encyclopedias is to select one encyclopedia, remove it, and remove all the other encyclopedias in the same row and column that the author wrote of the encyclopedia Cole chose. Cole wants to determine the minimum number of encyclopedias that need to be selected to remove all the encyclopedias from the shelf.

Note: The encyclopedias shelf section contains k authors. Each author is represented by an integer from 1 to k.

Example Let there be k = 3 authors. Let the following matrix represent the encyclopedias shelf:

221 111 233

Cole can choose the encyclopedia at position (2,3) in the first operation and remove it. Then, the matrix looks like this:

22x xxx 233

Cole can choose the encyclopedia at position (1,1) in the second operation and remove it. Then, the matrix looks like this: XXX XXX x33

Cole can choose the encyclopedia at position (3,3) in the third operation and remove it. Then, the matrix looks like this:

XXX XXX XXX

So the answer for this sample is 3

1<=n,m<=1000, k<=50

Can anyone help me with its solution?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English Ritu_1149 2024-10-03 13:33:41 2 Tiny change: ' answer.\n3 3 3\n2' -> ' answer.\n\n3 3 3\n2'
en5 English Ritu_1149 2024-10-03 13:32:19 842
en4 English Ritu_1149 2024-10-03 13:17:25 10
en3 English Ritu_1149 2024-10-03 13:16:43 15 Tiny change: 'ias shelf: Confidential\n221\n111' -> 'ias shelf:\n\n221\n111'
en2 English Ritu_1149 2024-10-03 13:16:02 59
en1 English Ritu_1149 2024-10-03 13:12:51 1464 Initial revision (published)