Connection Status:
Competition Arena > VotingBloc

VotingBloc

TCO07 Round 3 · 2007-03-07 · by dgoodman

TCO07 Round 3 · 2007-03-07 · by dgoodman · Graph Theory
Class Name: VotingBloc
Return Type: int[]
Method Name: abstainers
Arg Types: (vector<string>)
Problem Statement

Problem Statement

The members of a committee vote 'Yes' or 'No' on various issues. However, some pairs of committee members have formed alliances, promising never to cast opposite votes. No one is willing to vote contrary to her own opinion, so some of the members may need to abstain from voting in order to avoid conflict between allies.

We have devised a method to determine who should abstain. Before each issue is voted on, we randomly assign each committee member an identifying number, 1, 2, ..., n. The member will then indicate her opinion on the issue. Then we will calculate the smallest collection of abstentions that will avoid conflict.

The k-th element of the String[] voter contains the information about the k-th committee member -- the first element describes the member whose id is 1, the second describes the member whose id is 2, etc. Each element contains its member's opinion, either 'Y' or 'N', followed by the identifying number of each higher-numbered member who has formed an alliance with its member. Return a int[] containing, in ascending order, the identifying numbers of the minimal collection of members who must abstain from voting. If there is more than one minimal collection, return the one that is earliest lexicographically.

Constraints

  • voter will contain exactly n elements, where n is between 1 and 50, inclusive.
  • Each element of voter will contain between 1 and 50 characters, inclusive.
  • Each element of voter will be the character 'N' or 'Y' followed by a list of numbers.
  • Each number on a list (which may be empty) will be preceded by one space (' ').
  • The numbers on each list will be distinct, and will have no leading zeroes.
  • Each number on each list will be less than or equal to n.
  • Each number on the k-th list will be greater than the identifier of the k-th committee member.
Examples
0)
{"Y 2","N"}
Returns: {1 }

Here there are 2 members (1 and 2) and there is an alliance between them. Since they disagree on the issue, one of them must abstain. We choose 1 since it is earlier lexicographically.

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

Member 2 has an alliance with both 1 and 3. If member 3 abstains there will be no conflict since all the remaining members vote N. If member 1 abstains a conflict will remain since 2 and 3 are allies who disagree. If member 2 abstains, 1 and 3 are no longer in conflict. So there are two minimal sets of abstainers, and {2} is earlier lexicographically.

2)
{"N 2 3 4","N 3 4","Y 4","Y"}
Returns: {1, 2 }

Each member is allied with all the other members. The only way to avoid conflict is for all those whose opinion is 'Y' to abstain, or for all those whose opinion is 'N' to abstain. Either way it will take 2 abstentions.

3)
{"N 2 3 4","N 3 4","Y 4","N"}
Returns: {3 }

This is the same as the preceding case except that now 3 of the members agree on 'N', so it takes only 1 abstention to avoid conflict.

4)
{"Y 2 3 4","Y 3 4","Y 4","Y"}
Returns: { }

Everyone agrees, so no abstentions are needed.

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

Coding Area

Language: C++17 · define a public class VotingBloc with a public method vector<int> abstainers(vector<string> voter) · 61 test cases · 2 s / 256 MB per case

Submitting as anonymous