alex_ita's blog

By alex_ita, history, 3 days ago, In English,

Hello everyone! I'm given a problem but can't come up with the solution, so I hope someone can help me.

This is the problem statement:

-You are given a matrix consisting of 3 rows and N columns. The first row contains a permutation of numbers in range [1, N]. Second and third row also contain numbers in range [1, N], but some of the numbers are missing, and some are appearing a few times. What is the minimum number of columns you should delete so, after sorting all rows, rows become identical?

INPUT: First line contains T (1 <= T <= 10), number of test cases. First line of every test case contains N (1 <= N <= 40000), number of columns.

OUTPUT: Single line for every test case which is the answer.

input example:
2
4
3 2 1 4
2 3 4 4
3 2 2 4
7
4 1 5 7 6 3 2
7 5 3 2 6 1 4
5 3 5 7 4 1 1
output:
1
4

In the first matrix, column 2 (counting from 0) is deleted. For me, it looks like a DP problem, or maybe something can be done by hashing, map in C++. Any hints?

 
 
 
 

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by alex_ita (previous revision, new revision, compare).

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

It seems like we need to remove each item that is not included in every row once. Do yo have a link on this problem?

  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, you're correct! Unfortunately, this is a task my professor created and gave me printed on paper. I'm not sure if the complexity would be something like O(T*nlogn) if we use sets to store numbers per rows, and then look which numbers are not represented in every row.