Connection Status:
Competition Arena > CreateGroups

CreateGroups

SRM 430 · 2008-12-20 · by Janq

SRM 430 · 2008-12-20 · by Janq · Greedy, Simple Math
Class Name: CreateGroups
Return Type: int
Method Name: minChanges
Arg Types: (vector<int>, int, int)
Problem Statement

Problem Statement

Your language school is starting a new semester, and each student must select a time schedule. You are given a int[] groups, where the i-th element is the number of students who selected the i-th schedule. Your school has a rule stating that the number of students assigned to each schedule must be between minSize and maxSize, inclusive. However, this rule was not enforced properly during the sign up phase. It is your job to reassign students in such a way that the rule is satisfied. A reassignment is defined as removing a student from one time schedule and placing him in a different time schedule. Return the minimal number of students you must reassign, or return -1 if it is impossible to satisfy the rule. Note that you may not create new schedules or delete existing schedules.

Constraints

  • groups will contain between 1 and 50 elements, inclusive.
  • Each element of groups will be between 1 and 1,000,000, inclusive.
  • maxSize will be between 1 and 1,000,000, inclusive.
  • minSize will be between 1 and maxSize, inclusive.
Examples
0)
{10,20}
10
15
Returns: 5

We can move 5 students from the second time schedule to the first. Both schedules will then have a size of 15, which is the maximum allowed size.

1)
{20,8,6}
10
15
Returns: 6

We can move 2 students from the first schedule to the second, and another 4 students from the first schedule to the third. The sizes of the resulting schedules will be 14, 10 and 10.

2)
{10,20,30}
1
18
Returns: -1

There is no solution possible here. We have 60 students in 3 time schedules, so it is impossible to have at most 18 students per schedule.

3)
{50,10,20,20,5}
15
30
Returns: 20
4)
{100,200,301}
200
200
Returns: -1

Submissions are judged against all 95 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class CreateGroups with a public method int minChanges(vector<int> groups, int minSize, int maxSize) · 95 test cases · 2 s / 256 MB per case

Submitting as anonymous