RabbitProgramming

SRM 475 · 2009-11-12 · by lyrically

SRM 475 · 2009-11-12 · by lyrically · Dynamic Programming, Math

Show categories

Class Name: RabbitProgramming

Return Type: long

Method Name: getTeams

Arg Types: (vector<int>, vector<string>, int, int)

Problem Statement

Rabbits often feel lonely, so they enjoy participating in programming contests together.

Rabbit Iris is the head coach of her university's programming team. The big annual contest is going to be held next month, so she decided to hold a preliminary contest to help her decide who to put in the team.

The preliminary contest is now over, and the submissions are being reviewed. You are given a int[] points, and a String[] standings. Each element of points represents a single problem from the contest. For the j-th problem:

If points[j] is positive, then all submissions for this problem have been reviewed, and the point value of the problem is points[j]. The j-th character of the i-th element of standings is 'Y' if rabbit i correctly solved the problem, or 'N' if he did not.
If points[j] is negative, then none of the submissions for this problem have been reviewed yet, and the point value of the problem is -points[j]. The j-th character of the i-th element of standings is 'Y' if rabbit i submitted a solution (which may or may not be correct) for this problem, or 'N' if he did not.

A rabbit's score is the sum of the point values for the problems which he solved correctly. Once all the submissions are reviewed, the rabbits will be ranked according to their scores. Rabbits with higher scores will be ranked higher than rabbits with lower scores. If two rabbits have the same score, then the lower-numbered rabbit will be ranked higher. The top qualified ranking rabbits will be qualified to be members of the team. Among them, Iris will arbitrarily select selected rabbits to actually be in the team. If you consider all the possible scenarios for the problems which have not yet been reviewed, how many different teams are possible?

Notes

Two teams are considered different if and only if at least one rabbit belongs to exactly one of the teams.

Constraints

points will contain between 1 and 50 elements, inclusive.
Each element of points will be between -100,000 and 100,000, inclusive.
No element of points will be 0.
standings will contain between 1 and 50 elements, inclusive.
Each element of standings will contain exactly N characters, where N is the number of elements in points.
Each character in standings will be either 'Y' or 'N'.
qualified will be between 1 and the number of elements in standings, inclusive.
selected will be between 1 and qualified, inclusive.

Examples

{ 1, -10 }
{ "NY", 
  "YN", 
  "YN",
  "YN" }
3
2
Returns: 5

If rabbit 0's submission for problem 1 is correct, rabbits 0, 1, and 2 are qualified, and teams { 0, 1 }, { 0, 2 }, { 1, 2 } are possible. If it is incorrect, rabbits 1, 2, and 3 are qualified, and teams { 1, 2 }, { 1, 3 }, { 2, 3 } are possible.

{ -250, -500, -1000 }
{ "YYY", 
  "YNY", 
  "YYN", 
  "YYN", 
  "YNN" }
4
2
Returns: 10

Any pairs of rabbits can be chosen.

{ 5, -12, 5, -15, 10, -20, 3, -25, 7, -32, 21, -45 }
{ "YYYYYYYYYNYY", 
  "YYYNYYYYYNNN", 
  "YYYNYNYYNNYN", 
  "YYYYYNYYYYNN", 
  "YYNNYNYNYYNN", 
  "YYYNNNYYNNNN", 
  "YYNNNNYYNNNN", 
  "NNYNYYYNYNNN", 
  "NNNNNNYYYNNN", 
  "YYYNNNYYYNNN" }
4
3
Returns: 99

Example from a real programming contest.

{1}
{ "Y", "Y", "Y", "Y", "Y" }
3
2
Returns: 3

{ 124, 123, -1, 257, 1, -29, 871, 20, 897, 1, -25, 71, 9261, -9, 2, 63, 10, 82, 614, -9, 26, 7, 1, -9, 256, 1, 10, 2, 936, 1, -2, 52, 9, 56, 1, -2, 95, 17, 2, 61, -2, 30, 7, 51, 9, 23, 60, 1, 2, 4 }
{ "NNYNYNYNYNYNNYNNNNNYNYNYYNYNYNYNYNYNYNYNYNYYNYNYNY", "YNYNYNYNYNYYNYNYNYNYNYYNYNYNYNYNYNYNYNYNYNYNYYNYNY", "NYNYNYNYNYNYNYYNYNYNYNYNYNYYNYNYNYYNYNYNYNYNYNNYNN", "NNNYNYNYYNYNYNYNYNYNYNYNYNYYNYNYNYYNYNYNYNYNYYNYNY", "NYNYNYYNYNYNYNYNYNYNYNYNYNYNYYNYNYNYNYNYNYNYNYNYYN", "YNYNYNYNYNYYNYNYNYYNYNYNYNYNYNNYNNNNNYNYNYYNYNYNYN", "YNYNYNYNYNYYNYNYNYYNYNYNYNYNYYNYNYNYNYNYYNYNYNYNYN", "YNYNYNYNYNYNYYNYNYNYNYNYNYNYNYNYYNYNYNYNYNYNYYNYNY", "NYYNYNYNYNYNYNNYNNNNNYNYNYYNYNYNYNYNYNYNYNYNYYNYNY", "NYYNYNYNYNYNYYNYNYNYNYNYYNYNYNYNYNYNYNYNYNYNYNYYNY", "NYNYNYNYNYNYNYNYYNYNYNYNYNYNYYNYNYNYYNYNYNYNYNYNNY", "NNNNNYNYNYYNYNYNYNYNYNYNYNYNYYNYNYNYYNYNYNYNYNYYNY", "NYNYNYNYYNYNYNYNYNYNYNYNYNYNYNYYNYNYNYNYNYNYNYNYNY", "YNYNYNYNYNYNYYNYNYNYYNYNYNYNYNYNNYNNNNNYNYNYYNYNYN", "YNYNYNYNYNYNYYNYNYNYYNYNYNYNYNYYNYNYNYNYNYYNYNYNYN", "YNYNYNYNYNYNYNYYNYNYNYNYNYNYNYNYNYYNYNYNYNYNYNYYNY", "NYNYYNYNYNYNYNYNNYNNNNNYNYNYYNYNYNYNYNYNYNYNYNYYNY", "NYNYYNYNYNYNYNYYNYNYNYNYNYYNYNYNYNYNYNYNYNYNYNYNYY", "NYNYNYNYNYNYNYNYNYYNYNYNYNYNYNYYNYNYNYNYNYNYNNYNNN", "NNYNYNYYNYNYNYNYNYNYNYNYNYYNYNYNYYNYNYNYNYNYYNYNYN", "YNYNYYNYNYNYNYNYNYNYNYNYNYNYYNYNYNYNYNYNYNYNYNYYNY", "NYNYNYNYNYYNYNYNYYNYNYNYNYNYNNYNNNNNYNYNYYNYNYNYNY", "NYNYNYNYNYYNYNYNYYNYNYNYNYNYYNYNYNYNYNYYNYNYNYNYNY", "NYNYNYNYNYNYYNYNYNYNYNYNYNYNYNYYNYNYNYNYNYNYYNYNYN", "YYNYNYNYNYNYNNYNNNNNYNYNYYNYNYNYNYNYNYNYNYNYYNYNYN", "YYNYNYNYNYNYYNYNYNYNYNYYNYNYNYNYNYNYNYNYNYNYNYYNYN", "YNYNYNYNYNYNYNYYNYNYNYNYNYNYYNYNYNYYNYNYNYNYNYNNYN", "NNNNYNYNYYNYNYNYNYNYNYNYNYNYYNYNYNYYNYNYNYNYNYYNYN", "YNYNYNYYNYNYNYNYNYNYNYNYNYNYNYYNYNYNYNYNYNYNYNYNYY", "NYNYNYNYNYNYYNYNYNYYNYNYNYNYNYNNYNNNNNYNYNYYNYNYNY", "NYNYNYNYNYNYYNYNYNYYNYNYNYNYNYYNYNYNYNYNYYNYNYNYNY", "NYNYNYNYNYNYNYYNYNYNYNYNYNYNYNYNYYNYNYNYNYNYNYYNYN", "YNYYNYNYNYNYNYNNYNNNNNYNYNYYNYNYNYNYNYNYNYNYNYYNYN", "YNYYNYNYNYNYNYYNYNYNYNYNYYNYNYNYNYNYNYNYNYNYNYNYYN", "YNYNYNYNYNYNYNYNYYNYNYNYNYNYNYYNYNYNYYNYNYNYNYNYNN", "YNNNNNYNYNYYNYNYNYNYNYNYNYNYNYYNYNYNYYNYNYNYNYNYYN", "YNYNYNYNYYNYNYNYNYNYNYNYNYNYNYNYYNYNYNYNYNYNYNYNYN", "YYNYNYNYNYNYNYYNYNYNYNYNYNYNNYNNNNNYNYNYYNYNYNYNYN", "YNYNYNYNYYNYNYNYYNYNYNYNYNYYNYNYNYNYNYYNYNYNYNYNYN", "YNYNYNYNYNYYNYNYNYNYNYNYNYNYNYYNYNYNYNYNYNYYNYNYNY", "YNYNYNYNYNYNNYNNNNNYNYNYYNYNYNYNYNYNYNYNYNYYNYNYNY", "YNYNYNYNYNYYNYNYNYNYNYYNYNYNYNYNYNYNYNYNYNYNYYNYNY", "NYNYNYNYNYNYNYYNYNYNYNYNYNYYNYNYNYYNYNYNYNYNYNNYNN", "NNNYNYNYYNYNYNYNYNYNYNYNYNYYNYNYNYYNYNYNYNYNYYNYNY", "NYNYNYYNYNYNYNYNYNYNYNYNYNYNYYNYNYNYNYNYNYNYNYNYYN", "YNYNYNYNYNYYNYNYNYYNYNYNYNYNYNNYNNNNNYNYNYYNYNYNYN", "YNYNYNYNYNYYNYNYNYYNYNYNYNYNYYNYNYNYNYNYYNYNYNYNYN", "YNYNYNYNYNYNYYNYNYNYNYNYNYNYNYNYYNYNYNYNYNYNYYNYNY", "NYYNYNYNYNYNYNNYNNNNNYNYNYYNYNYNYNYNYNYNYNYNYYNYNY", "NYYNYNYNYNYNYYNYNYNYNYNYYNYNYNYNYNYNYNYNYNYNYNYYNY" }
48
45
Returns: 17296

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

Coding Area

Language: C++17 · define a public class RabbitProgramming with a public method long long getTeams(vector<int> points, vector<string> standings, int qualified, int selected) · 100 test cases · 2 s / 256 MB per case