Filtering
SRM 497 · 2010-11-01 · by ivan_metelsky
SRM 497 · 2010-11-01 · by ivan_metelsky · Simple Search, Iteration
Problem Statement
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 aint[] 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[] .
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
Constraints
- 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.
Examples
0)
{3, 4, 5, 6, 7}
"AAAAA"
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.
1)
{3, 4, 5, 6, 7}
"AARAA"
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.
2)
{3, 4, 5, 6, 7}
"RAAAA"
Returns: {4, 7 }
However, it's possible to reject only objects of size 3.
3)
{9}
"A"
Returns: {9, 9 }
4)
{11,42}
"AR"
Returns: {11, 11 }
Submissions are judged against all 144 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class Filtering with a public method vector<int> designFilter(vector<int> sizes, string outcome) · 144 test cases · 2 s / 256 MB per case