AutoMarket
SRM 233 · 2005-03-03 · by ValD
SRM 233 · 2005-03-03 · by ValD · Dynamic Programming, Graph Theory, Sorting
Problem Statement
Problem Statement
It is expected that the more expensive the automobile, the more features are included and the less often it breaks down. While expected, this is not always true. Given a set of automobile specs, find the largest subset where the condition is reversed.
Write a class AutoMarket that contains a method maxSet, which accepts a int[] cost, int [] features and int[] fixTimes and returns the size of the largest subset that can be ordered such that each succeeding automobile costs more, has less features and must be fixed more often. All conditions are strict. The ith element in cost, features and fixTimes represents the ith car, which costs cost[i] dollars, has features[i] features and must be fixed fixTimes[i] times per year.
Write a class AutoMarket that contains a method maxSet, which accepts a int[] cost, int [] features and int[] fixTimes and returns the size of the largest subset that can be ordered such that each succeeding automobile costs more, has less features and must be fixed more often. All conditions are strict. The ith element in cost, features and fixTimes represents the ith car, which costs cost[i] dollars, has features[i] features and must be fixed fixTimes[i] times per year.
Constraints
- cost, features and fixTimes will each have between 1 and 50 elements, inclusive.
- cost, features and fixTimes will have the same number of elements.
- Each element of cost will be between 1 and 100000, inclusive.
- Each element of features and fixTimes will be between 1 and 100, inclusive.
Examples
0)
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50}
{50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1}
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50}
Returns: 50
Largest test result
1)
{10000, 14000, 8000, 12000}
{1, 2, 4, 3}
{17, 15, 8, 11}
Returns: 3
The largest set contains all elements except the first.
2)
{1,2,3,4,5}
{1,2,3,4,5}
{1,2,3,4,5}
Returns: 1
3)
{9000, 6000, 5000, 5000, 7000}
{1, 3, 4, 5, 2}
{10, 6, 6, 5, 9}
Returns: 4
4)
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
{20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1}
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
Returns: 20
Submissions are judged against all 34 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class AutoMarket with a public method int maxSet(vector<int> cost, vector<int> features, vector<int> fixTimes) · 34 test cases · 2 s / 256 MB per case