TransWikia.com

What is the minimum number of parts required to split the sequence S to in order to obtain sequence T?

Computer Science Asked by Powerful blaster on January 22, 2021

Suppose a person has a sequence (S) consisting of integer numbers and would like to split the sequence into a
number (possibly one) of continuous parts. For each part independently, I then choose any integer
value and removes all occurrences of this value in the corresponding part (note that there could be
no such occurrences). After that, the person will combine all parts in the same order to achieve a new
sequence (T).
How to find out the minimum number of parts needed to split the sequence in order to achieve this goal .

let n = size of sequence S and m = size of sequence T


  • Constraints:
    1 <= n,m <= 2000

  • Input Format: n m
    Sequence S
    Sequence T

  • Output Format: if it is not possible to transform S into T output -1
    otherwise, output min number of parts required.

  • Sample Input and Output:

Input Output
4 2
4 2 7 2
4 7
1
7 2
4 7 1 4 1 7 1
4 7
3
3 2
7 4 2
4 7
-1

My Attempt:
I did not understand how Sequence S={4,2,7,2} can be transformed to T = {4,7}. If I followed this procedure by splitting a sequence into parts such as {4} {2} {7} {2} and then iterate from 1st index and then the 2nd index until the end, and if I encounter the same value I delete all of its occurrences. When I do this, I get the sequence {4,2,7} and minpart is just 1.

And, for the sequence {4,7,1,4,1,7,1}, I am able to get {4,7,1} and minparts are 3.

But I do not understand, how both of these sequences: S = {4,2,7,2} and S = {4,7,1,4,1,7,1} can be transformed to the sequence T = {4,7}?

One Answer

  1. To get the sequence $T = {4,7}$ from $S = {4,2,7,2}$, you can take the entire set S as a minipart and remove $2$ from it. Therefore, there is just one minipart.

  2. To get the sequence $T = {4,7}$ from $S = {4,7,1,4,1,7,1}$, you can take three minimarts as follows:

    • $P1 = {4}$
    • $P2 = {7}$
    • $P3 = {1,4,1,7,1}$

    Now, remove $4$ from $P1$, remove $7$ from $P2$, and remove $1$ from $P3$. You will get the sequence $T = {4,7}$.

Answered by Inuyasha yagami on January 22, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP