TeamContestEasy
SRM 573 · 2012-12-13 · by rng_58
SRM 573 · 2012-12-13 · by rng_58 · Greedy
Problem Statement
Problem Statement
Your university is holding a programming competition and your team is going to compete.
There are 3*N students in the university. They are numbered from 0 to 3*N-1. Each student has a certain strength which is a positive number that characterizes his/her programming skills. You are given aint[] strength. The strength of student i is equal to strength[i].
Your team will consist of students 0, 1 and 2. Other 3*N-3 students will form N-1 more teams so that each team has exactly 3 members. The exact composition of other teams is not known yet. Each team has a strength that is calculated as follows: if it consists of members with strengths X, Y and Z, then the team's strength is equal to X + Y + Z - min{X, Y, Z}, i.e., the strength of a team is the total strength of its two strongest members.
You are interested how your team will rank by strength among the other teams. Formally, the rank of your team is defined as 1 + (the number of other teams that have a strictly greater strength than the strength of your team).
Return the maximum possible rank that your team may have after all students split into teams.
There are 3*N students in the university. They are numbered from 0 to 3*N-1. Each student has a certain strength which is a positive number that characterizes his/her programming skills. You are given a
Your team will consist of students 0, 1 and 2. Other 3*N-3 students will form N-1 more teams so that each team has exactly 3 members. The exact composition of other teams is not known yet. Each team has a strength that is calculated as follows: if it consists of members with strengths X, Y and Z, then the team's strength is equal to X + Y + Z - min{X, Y, Z}, i.e., the strength of a team is the total strength of its two strongest members.
You are interested how your team will rank by strength among the other teams. Formally, the rank of your team is defined as 1 + (the number of other teams that have a strictly greater strength than the strength of your team).
Return the maximum possible rank that your team may have after all students split into teams.
Constraints
- strength will contain between 3 and 48 elements, inclusive.
- The number of elements in strength will be divisible by 3.
- Each element of strength will be between 1 and 1,000,000, inclusive.
Examples
0)
{5, 7, 3, 5, 7, 3, 5, 7, 3}
Returns: 2
The strength of your team is 5 + 7 + 3 - min{5, 7, 3} = 12. It is possible that one of the other teams will be stronger than your team. For example, if it consists of students with strengths 5, 7 and 7, then its strength will be 14. However, it is not possible that both other teams will be stronger than your team.
1)
{5, 7, 3}
Returns: 1
Just your team. No rivals.
2)
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
Returns: 1
All teams (including yours) will have the same strength: 2.
3)
{2,2,1,1,3,1,3,2,1,3,1,2,1,2,1}
Returns: 4
4)
{45,72,10,42,67,51,33,21,8,51,17,72}
Returns: 3
Submissions are judged against all 213 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TeamContestEasy with a public method int worstRank(vector<int> strength) · 213 test cases · 2 s / 256 MB per case