RabbitProgramming | Topcoder Archive

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?

Definition

Class:: RabbitProgramming
Method:: getTeams
Parameters:: int[], String[], int, int
Returns:: long
Method signature:: long getTeams(int[] points, String[] standings, int qualified, int selected)
(be sure your method is public)

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" }

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" }

Returns: 99

Example from a real programming contest.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.