1
$\begingroup$

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}?

$\endgroup$
1
  • 1
    $\begingroup$ Can you tell us where you encountered this task? $\endgroup$
    – D.W.
    Jan 19 at 6:34
1
$\begingroup$
  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\}$.

$\endgroup$
11
  • $\begingroup$ There is a simple Dynamic Programming algorithm for this problem. You can first think on that by yourself and then ask if you are facing any difficulties. $\endgroup$ Jan 19 at 7:16
  • $\begingroup$ But how can I decide the length of each minpart?? $\endgroup$ Jan 19 at 10:18
  • $\begingroup$ @Powerfulblaster You are asking about the algorithm or you have some doubt in the above explanation of sample inputs/outputs. $\endgroup$ Jan 19 at 10:30
  • $\begingroup$ Why you did not take the 1st one also as a minpart? so you have {4} {7} {1} {4,1,7,1}?? Or The numbers deleted from each minpart should be different? $\endgroup$ Jan 20 at 19:49
  • 1
    $\begingroup$ @Powerfulblaster You can not remove more than one type of number from any partition. And it is always better to remove a number from a partition rather than not removing any number because you want to minimize the number of partitions. And, for the sequence {4,7,3,6,8} there would be three partitions: {4,7,3} {6} {8} $\endgroup$ Jan 21 at 10:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.