Connection Status:
Competition Arena > ICPCBalloons

ICPCBalloons

SRM 561 · 2012-06-05 · by ivan_metelsky

SRM 561 · 2012-06-05 · by ivan_metelsky · Brute Force, Greedy
Class Name: ICPCBalloons
Return Type: int
Method Name: minRepaintings
Arg Types: (vector<int>, string, vector<int>)
Problem Statement

Problem Statement

You are organizing a subregional ACM ICPC contest. The problemset at the contest will consist of M problems. According to an ACM ICPC tradition, when a team solves a problem, it gets awarded a balloon. To account for this, you've bought balloons of N different colors (conveniently numbered from 0 to N-1). The number of balloons of color i that you've bought is given by balloonCount[i]. Balloons come in two sizes: medium and large. All balloons of the same color have the same size. If the i-th character of balloonSize is 'M', then all balloons of color i have medium size, and if this character is 'L', then all balloons of color i have large size.

Today you've been at the meeting with the scientific committee of the contest. There, you learned that there are additional restrictions of which you were not aware. Here are those restrictions:
  • All balloons that get awarded for a particular problem must have the same color and size.
  • For any two problems, the colors of balloons awarded for solving them must be different. In other words, the color of balloons awarded for each problem must be unique.
These are definitely bad news, since you ordered balloons pretty much arbitrarily and it's possible that you won't be able to satisfy the restrictions with the balloons you currently have. However, the good news is that scientific committee members were able to evaluate the difficulty of each problem. More exactly, they told you that the maximum number of teams that can potentially solve the i-th problem is maxAccepted[i]. The scientific committee members are very clever and experienced, so their prediction is guaranteed to come true.

Your budget is limited and balloons are expensive, so buying more of them is not an option. Fortunately, there is a very cheap balloon repaint service at your city, so you are going to use it. The service offers repainting a given balloon into any other color. This can be one of the N colors you have, as well as any color that you don't have yet. However, it is not possible to change the size of a balloon.

You are given the int[]s balloonCount, maxAccepted and the String balloonSize. Return the minimum number of balloons that have to be repainted in order to guarantee that you will be able to award balloons to the teams properly. If it is impossible to achieve the goal using any number of balloon repaintings, return -1.

Constraints

  • balloonCount will contain between 1 and 50 elements, inclusive.
  • Each element of balloonCount will be between 1 and 100, inclusive.
  • balloonSize will contain the same number of characters as the number of elements in balloonCount.
  • Each character of balloonSize will be 'M' or 'L'.
  • maxAccepted will contain between 1 and 15 elements, inclusive.
  • Each element of maxAccepted will be between 1 and 100, inclusive.
Examples
0)
{100}
"L"
{1,2,3,4,5}
Returns: 10

You have 100 large balloons of the same color. 5 of them can be used for problem 4 and 1+2+3+4=10 balloons need to be repainted in order to be used for remaining problems.

1)
{100}
"M"
{10,20,30,40,50}
Returns: -1

We don't have enough balloons. Repainting is not going to help.

2)
{5,6,1,5,6,1,5,6,1}
"MLMMLMMLM"
{7,7,4,4,7,7}
Returns: 6

(Note that all of the indices in this annotation are 0-based.) Repaint one balloon of color 7 into color 1. Repaint one balloon of color 7 into color 4. Now large balloons can be awarded for problems 0, 1, and 2. Repaint two balloons of colors 2 and 5 into color 0. Repaint two balloons of colors 6 and 8 into color 3. Now medium balloons of colors 0, 3, and 6 can be awarded for problems 3, 4, and 5.

3)
{100,100}
"ML"
{50,51,51}
Returns: -1

Even though we have 200 balloons overall and only at most 152 accepted solutions, there is still no way of dividing and repainting the balloons that works.

4)
{19,25,19,34,8,33,12,12,8,2,36,14,30,11,13,32,15,30,11,27,30,4,6,17,21,13,10,28,14,10,35,10,26,15,11,34,13,13,23,27,7,9,3,34,29,27,2,15,11,25}
"LLMLLMLLMLLMLLLLLLLLLLLLLLMLLLLLLLLMMMLMLMLLLMMLML"
{43,1,27,12,48,43,26,17,46,32,49,50,1,19,15}
Returns: 73

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

Coding Area

Language: C++17 · define a public class ICPCBalloons with a public method int minRepaintings(vector<int> balloonCount, string balloonSize, vector<int> maxAccepted) · 165 test cases · 2 s / 256 MB per case

Submitting as anonymous