https://community.topcoder.com/stat?c=problem_statement&pm=13268&rd=16187 ↵
Problem Summary : Given an array of 1<=N<=47 integers. All the integers are in range [1,47]. Given two number low,high(1<=low<=high<=47). We have pick a sub sequence of the given array in **minimum move** that contains only the numbers in range [low,high] and all the numbers in range[low,high]. In a single move we can pick a continuous sequence of numbers from the given array. We to find number of ways to pick such sub sequence in minimum move. ↵
Examples↵
0) ↵
↵
First line contains the integers. Second and third line contains value of low and high respectively. ↵
(Case 0) ↵
{2, 1, 3}↵
1↵
3 ↵
1 ↵
3 ↵
Returns: 1 ↵
The only way to choose the subset is to choose all animals.↵
1) ↵
↵
(Case 1) ↵
{3, 4, 1, 3, 4, 2}↵
1↵
3 ↵
1 ↵
3 ↵
Returns: 2 ↵
In the optimal solution we send away animals #2, #3, and #5 (0-based indices). Animals #2 and #3 form one group, animal #5 forms the other.↵
2) ↵
↵
(Case 2) ↵
{3, 4, 3, 1, 6, 2, 5, 7, 5, 2}↵
2↵
6↵
Returns: 2↵
3) ↵
↵
2 ↵
6 ↵
Returns: 2 ↵
(Case 3) ↵
{3, 1, 4}↵
2↵
4↵
Returns: -1↵
4) ↵
↵
2 ↵
4 ↵
Returns: -1 ↵
(Case 4) ↵
{2, 1, 3, 1, 4}↵
1↵
4 ↵
1 ↵
4 ↵
Returns: 1 ↵
Note that we are not required to minimize the number of animals we send. Here, we could select just four of these five animals but that would create two groups. A better solution is to select all five animals, then they all form a single group.↵
5) ↵
↵
(Case 5) ↵
{7, 12, 2, 12, 10, 13, 6, 5, 3, 3, 4, 11, 12, 4, 3, 1, 8, 11, 4, 7, 6, 5, 47}↵
2↵
7 ↵
2 ↵
7 ↵
Returns: 3 Don't figure out the DP idea. Can anyone show me a direction in the problem? Thanks in advance.
Problem Summary : Given an array of 1<=N<=47 integers. All the integers are in range [1,47]. Given two number low,high(1<=low<=high<=47). We have pick a sub sequence of the given array in **minimum move** that contains only the numbers in range [low,high] and all the numbers in range[low,high]. In a single move we can pick a continuous sequence of numbers from the given array. We to find number of ways to pick such sub sequence in minimum move. ↵
Examples
0) ↵
First line contains the integers. Second and third line contains value of low and high respectively. ↵
(Case 0)
{2, 1, 3}
1↵
3
1 ↵
3 ↵
Returns: 1 ↵
The only way to choose the subset is to choose all animals.
1) ↵
(Case 1)
{3, 4, 1, 3, 4, 2}
1↵
3
1 ↵
3 ↵
Returns: 2 ↵
In the optimal solution we send away animals #2, #3, and #5 (0-based indices). Animals #2 and #3 form one group, animal #5 forms the other.
2) ↵
(Case 2)
{3, 4, 3, 1, 6, 2, 5, 7, 5, 2}
2↵
6↵
Returns: 2↵
3) ↵
2 ↵
6 ↵
Returns: 2 ↵
(Case 3)
{3, 1, 4}
2↵
4↵
Returns: -1↵
4) ↵
2 ↵
4 ↵
Returns: -1 ↵
(Case 4)
{2, 1, 3, 1, 4}
1↵
4
1 ↵
4 ↵
Returns: 1 ↵
Note that we are not required to minimize the number of animals we send. Here, we could select just four of these five animals but that would create two groups. A better solution is to select all five animals, then they all form a single group.
5) ↵
(Case 5)
{7, 12, 2, 12, 10, 13, 6, 5, 3, 3, 4, 11, 12, 4, 3, 1, 8, 11, 4, 7, 6, 5, 47}
2↵
7
2 ↵
7 ↵
Returns: 3 Don't figure out the DP idea. Can anyone show me a direction in the problem? Thanks in advance.
