Update appNew update is available. Click here to update.

Sequence Reconstruction

Posted: 1 Apr, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given a sequence ‘primary’ and a sequence of sequences ‘secondary.’ The sequence ‘primary’ is a permutation of numbers from 1 to N. You need to find if the sequence ‘primary’ is the only shortest common supersequence of sequences in ‘secondary’.

The shortest common supersequence of two sequences, ‘A’ and ‘B’, is the shortest sequence such that ‘A’ and ‘B’ are subsequences of it.

Note :
The range of elements in the ‘secondary’ sequence varies from 1 to N.
For Example :
If primary = [ 1, 2, 3 ] and secondary = [ [ 1, 2 ], [ 1, 3 ] ]
[ 1, 2, 3 ] is shortest common supersequence of [ 1, 2 ] and [ 1, 3 ]. But [ 1, 3, 2 ] is also a shortest common super sequence of [ 1, 2 ] and [ 1, 3 ]. As [ 1, 2, 3 ] is not the only shortest supersequence, you need to return false.
Input Format :
The first line contains ‘ T ‘, denoting the number of test cases.

The first line of each test case contains three space-separated integers, N - number of elements in ‘primary’ sequence, ‘ X ‘ - number of sequences in ‘secondary’ sequence, and ‘ Y ‘ - number of elements in each sequence of ‘secondary’ sequence.

Each test case’s second line contains ‘ N ’ space-separated integers denoting elements of the ‘primary’ sequence.

The following ‘ X ‘ lines of each test case contain ‘ Y ‘ space-separated integers.
Output Format :
For each test case, return “ True “ if ‘primary’ is the only shortest supersequence of all the sequences in the ‘secondary’ sequence. Otherwise, return “ False “.

Print the output of each test case in a separate line.
Constraints :
1 <= T <= 10
1 <= N <= 10^5
1 <= primary[ i ] <= N
1 <= X, Y <= 10^3

Time Limit: 1 sec