ScoringSystems
TCO13 Championship Round · 2013-02-19 · by rng_58
TCO13 Championship Round · 2013-02-19 · by rng_58 · Dynamic Programming
Problem Statement
Problem Statement
Fox Ciel and Cat Snuke decided to organize a programming contest. They are discussing the scoring system of the contest now.
They prepared N problems for the contest. Each contestant will solve a subset of these problems, and total score of the contestant will be the sum of the point values assigned to the problems solved by the contestant. Ciel thinks the i-th problem should be worth c[i] points. Snuke thinks the i-th problem should be worth s[i] points. For example, suppose that Ciel chose the point values c = {30, 50, 20}. Let X = {0, 2} be the 0-based indices of problems a contestant solved. Then Ciel's scoring system would assign the score 30 + 20 = 50 to this contestant. We will denote this as follows: C(X) = 50. Similarly S(X) is defined by Snuke's scoring system.
Check whether these scoring systems are equivalent, and return "Equivalent" or "Not Equivalent".
Formally, these two scoring systems are equivalent if for any two sets of problem indices X, Y one of the following three conditions holds:
They prepared N problems for the contest. Each contestant will solve a subset of these problems, and total score of the contestant will be the sum of the point values assigned to the problems solved by the contestant. Ciel thinks the i-th problem should be worth c[i] points. Snuke thinks the i-th problem should be worth s[i] points. For example, suppose that Ciel chose the point values c = {30, 50, 20}. Let X = {0, 2} be the 0-based indices of problems a contestant solved. Then Ciel's scoring system would assign the score 30 + 20 = 50 to this contestant. We will denote this as follows: C(X) = 50. Similarly S(X) is defined by Snuke's scoring system.
Check whether these scoring systems are equivalent, and return "Equivalent" or "Not Equivalent".
Formally, these two scoring systems are equivalent if for any two sets of problem indices X, Y one of the following three conditions holds:
- C(X) < C(Y) and S(X) < S(Y)
- C(X) = C(Y) and S(X) = S(Y)
- C(X) > C(Y) and S(X) > S(Y)
Constraints
- c and s will contain the same number of elements.
- c and s will contain between 1 and 50 elements, inclusive.
- Each element of c and s will be between 1 and 10,000, inclusive.
Examples
0)
{1, 2}
{2, 3}
Returns: "Equivalent"
1)
{1, 2}
{2, 2}
Returns: "Not Equivalent"
According to Ciel's system, a contestant who only solved problem 0 is worse than a contestant who only solved problem 1. According to Snuke's system these two contestants would be equally good. Formally, for X={0} and Y={1} we have C(X) < C(Y) but S(X)=S(Y).
2)
{30, 50, 20}
{49, 50, 1}
Returns: "Equivalent"
3)
{250, 500, 1000}
{300, 600, 900}
Returns: "Not Equivalent"
Consider the sets X={0,1} and Y={2}.
4)
{6, 6, 6, 6, 6, 8, 8, 8, 8, 8}
{5, 5, 5, 5, 5, 7, 7, 7, 7, 7}
Returns: "Not Equivalent"
Submissions are judged against all 112 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ScoringSystems with a public method string isEquivalent(vector<int> c, vector<int> s) · 112 test cases · 2 s / 256 MB per case