TopCoder problem "Filtering" used in SRM 497 (Division II Level One)

Problem Statement

    You recently got a job at a company that designs various kinds of filters, and today, you've been given your first task. A client needs a filter that accepts some objects and rejects some other objects based on their size. The requirements are described in the int[] sizes and the String outcome. If character i in outcome is 'A', then all objects of size sizes[i] must be accepted, and if character i is 'R', then all objects of size sizes[i] must be rejected. If an object's size does not appear in sizes, then it doesn't matter if it is accepted or rejected.

Unfortunately, your knowledge of filters is very limited, and you can only design filters of one specific kind called (A, B)-filters. Each such filter is characterized by two integers A and B. It accepts an object if and only if its size is between A and B, inclusive. You have excellent (A, B)-filter construction skills, so you can construct any such filter where 1 <= A <= B.

If it is possible to construct an (A, B)-filter that fulfills all the requirements described in sizes and outcome, return a int[] containing the filter's parameters, where element 0 is A and element 1 is B. If there are several appropriate filters, choose the one that minimizes B - A. If there are no suitable filters, return an empty int[].


Parameters:int[], String
Method signature:int[] designFilter(int[] sizes, String outcome)
(be sure your method is public)


-sizes will contain between 1 and 50 elements, inclusive.
-Each element of sizes will be between 1 and 100, inclusive.
-All elements of sizes will be distinct.
-outcome will contain the same number of characters as the number of elements in sizes.
-Each character in outcome will be 'A' or 'R'.
-outcome will contain at least one 'A' character.


{3, 4, 5, 6, 7}
Returns: {3, 7 }
Any filter with A <= 3 and B >= 7 will work in this case. Among them, A = 3 and B = 7 gives the minimal difference of B - A.
{3, 4, 5, 6, 7}
Returns: { }
This is similar to the previous example, but objects of size 5 need to be rejected. It's impossible to achieve this using a single (A, B)-filter.
{3, 4, 5, 6, 7}
Returns: {4, 7 }
However, it's possible to reject only objects of size 3.
Returns: {48, 57 }
Returns: { }

Problem url:

Problem stats url:




PabloGilberto , Chmel_Tolstiy

Problem categories:

Simple Search, Iteration