Connection Status:
Competition Arena > Pareto

Pareto

TCCC '03 Int'l Regional · 2003-02-22 · by dgoodman

TCCC '03 Int'l Regional · 2003-02-22 · by dgoodman · Simple Search, Iteration, String Manipulation
Class Name: Pareto
Return Type: int
Method Name: optima
Arg Types: (vector<string>)
Problem Statement

Problem Statement

A government policy will lead to a particular outcome for each person involved. A policy is "suboptimal" if there exists an alternative policy that will not worsen the outcome for anyone and that will provide a better outcome for at least one person. A policy that is not suboptimal is called a "Pareto Optimum". There may be many Pareto Optima.

Create a class Pareto that contains a method optima that takes a String[] policy as input. Each element of policy gives the outcome from one policy choice. Your method should return the number of policy choices that are Pareto Optimal.

Each element of policy will be formatted as "[feeling] [feeling] [feeling] ..." where each [feeling] describes the outcome for the corresponding person. There will be no leading or trailing spaces, and there will be exactly one space between each pair of adjacent [feeling].

Each [feeling] is one of the following strings, (given in order of increasing satisfaction)

  • "awful", "bad", "fair", "fairly-happy", "happy", "ecstatic"

Notes

  • two policies with identical outcomes may both be Pareto Optimal

Constraints

  • policy will contain between 1 and 50 elements inclusive
  • each element of policy will contain between 3 and 50 characters, inclusive
  • each element of policy will be formatted as described above
  • each element of policy will contain the same number of [feeling] elements as does every other element of policy.
Examples
0)
{"bad bad fairly-happy awful",
"bad bad bad awful",
"ecstatic awful ecstatic ecstatic"}
Returns: 2

There are four people affected by our choice of policy. The second policy is suboptimal when compared to the first policy. Neither the first nor the third policy is suboptimal (the second person would prefer the first policy over the third policy, while the first person would prefer the third policy). So the first and third policies are Pareto Optimal.

1)
{"bad ecstatic","bad bad", "awful ecstatic",
 "fair happy", "fairly-happy fair",
"fairly-happy fairly-happy", "fair happy"}
Returns: 4

The first, fourth, sixth, and seventh are Pareto Optimal. The second is worse than the first, the third is worse than the first, and the fifth is worse than the sixth. The fourth and seventh policies lead to the same outcome, and neither is suboptimal.

2)
{"happy","bad","fairly-happy","bad","happy"}
Returns: 2

Only 1 person is affected by these 5 policy choices, and the first and last choices both leave him feeling "happy", while the other 3 policies are clearly worse.

3)
{"bad bad bad bad bad happy fairly-happy"}
Returns: 1

When there is only one policy choice, it must be Pareto Optimal.

4)
{"fair fair fair fair fair fair fair fair",
"bad fair fair fair fair fair fair fair",
"fairly-happy fair fair fair fair fair fair fair",
"happy bad bad bad bad bad bad bad",
"bad happy happy happy happy happy happy happy"}
Returns: 3

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

Coding Area

Language: C++17 · define a public class Pareto with a public method int optima(vector<string> policy) · 19 test cases · 2 s / 256 MB per case

Submitting as anonymous