ivplay's blog

By ivplay, history, 3 years ago, In English

Original Statement 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 need to find number of ways to pick such sub sequence in minimum move.
Examples
First line contains the integers. Second and third line contains value of low and high respectively.
(Case 0)
{2, 1, 3}
1
3
Returns: 1
The only way to choose the subset is to choose all animals.
(Case 1)
{3, 4, 1, 3, 4, 2}
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.
(Case 2)
{3, 4, 3, 1, 6, 2, 5, 7, 5, 2}
2
6
Returns: 2
(Case 3)
{3, 1, 4}
2
4
Returns: -1
(Case 4)
{2, 1, 3, 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.
(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
Returns: 3 I couldn't figure out the DP idea. Can anyone show me a direction in the problem? Thanks in advance.

 
 
 
 
  • Vote: I like it
  • -8
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ivplay (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Interesting problem, if the constraints were smaller e.g ( N = 20 ), it would be solvable using bitmasks, but with N >= 40 it looks like it needs a Meet-in-the-Middle solution. I can't come up with a correct approach, if anyone can help with this. It would be much appreciated!

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I looked at the solutions, and the solution was to compress every maximal continuous subarray that contains only elements in the range [low, high], and store them as bitmasks of the elements in that subarray. The key observation was in an array of size 44, there would be at most 22 relevant subarrays containing elements in range. After that we try all subsets of the relevant subarrays, and check which subsets contain all the elements, pick the subset with minimal size.