### alex_ita's blog

By alex_ita, history, 3 days ago, ,

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, # |   0 Auto comment: topic has been updated by alex_ita (previous revision, new revision, compare).
 » 3 days ago, # |   0 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, # ^ |   0 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.