CinderellaGirls
TCO19 SRM 756 · 2019-04-24 · by IH19980412
Problem Statement
There are N girls auditioning for an idol competition. You are a junior producer of the competition. During the auditions you have evaluated the talent and the skill of each candidate. The results of these evaluations are given in the
Your task is to decide which girls advance to the second stage of the selection process. In order to do this, you came up with a simple rule: girl A will advance if and only if there is no other girl B such that B has both strictly more talent and strictly more skill than A.
Please calculate and return the number of girls who advance to the second stage.
Constraints
- N will be between 2 and 50, inclusive.
- talent will contain exactly N elements.
- skill will contain exactly N elements.
- Each element in talent will be between 1 and 10,000, inclusive.
- Each element in skill will be between 1 and 10,000, inclusive.
{10,20,30}
{30,20,10}
Returns: 3
Every girl will be accepted.
{10,20,30}
{10,20,30}
Returns: 1
In this case, girls 0 and 1 will not be accepted because girl 2 has more talent and more skill than each of the other two.
{10,10,10}
{1,100,10000}
Returns: 3
Their skill scores differ significantly but their talent scores are the same so every girl will be invited to the second stage.
{46,70,39,53,10,47,73,95,95,27}
{81,47,64,65,34,55,75,16,80,69}
Returns: 3
{6271,40,2988,444,5004,5298,8607,9364,2810,2691,7346,1330,4727,8832,6106,5973,9126,8630,402,5497,2515,2794,7316,4329,4061,5414,3377,2296,8544,1387,924,1015,9634,7487,252,6411,2292,2490,1624,6015,5690,72,9291,7284,2257,3211,1267,8659,4744,8993}
{3359,2539,3712,6014,3838,5782,9174,3752,5545,6000,3929,1238,9336,7139,7606,3855,7239,3143,8385,3405,8253,6906,7119,4080,7865,9627,9891,4279,6867,9885,5009,9418,9234,5979,4994,7721,1759,4153,161,3704,766,6763,7597,9049,2270,6165,8111,8966,1163,6801}
Returns: 3
Submissions are judged against all 32 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CinderellaGirls with a public method int count(vector<int> talent, vector<int> skill) · 32 test cases · 2 s / 256 MB per case