TopCoder problem "BalancedGame" used in SRM 254 (Division II Level One)

Problem Statement

You will be given a String[], conflicts, where each element represents a single player in a multiplayer game. Element i represents player i, and character j of element i represents whether player i will win ('W'), tie ('T'), or lose ('L') against player j.

Your task is to ensure that each player wins against at least p% of the other players, and loses against at least q% of the other players. You should return the 0-based index of the first player in the input (lowest index) that does not meet these requirements, or -1 if all players meet them. Note that if there are N players total, then at least ceil((N-1)*p/100) of the characters in element i must be 'W' for player i to meet the requirements. The formula for losses is analogous.

Definition

Class:	BalancedGame
Method:	result
Parameters:	String[], int, int
Returns:	int
Method signature:	int result(String[] conflicts, int p, int q)
(be sure your method is public)

Notes

The i-th character of the i-th element of conflicts will always be 'T' and can be ignored.

The function 'ceil' in ceil((N-1)*p/100) returns the least integer greater than or equal to its argument. For example, ceil(1.5)=2 and ceil(4)=4.

Constraints

p and q will be between 0 and 100, inclusive.

conflicts will have between 2 and 50 elements, inclusive.

Each element of conflicts will have the same number of characters ('W', 'L' and 'T') as the number of elements in conflicts.

If the j-th character of the i-th element of conflicts is 'W', 'L', or 'T' then the i-th character of the j-th element will be 'L', 'W' or 'T' respectively.

The i-th character of the i-th element of conflicts will always by 'T'.

Examples

{"TWWW",
 "LTWW",
 "LLTW",
 "LLLT"}

Returns: 0

Player 0 cannot lose and player 3 cannot win, so these players are not balanced. Return the lowest index of an unbalanced player.

{"TWWW",
 "LTWW",
 "LLTW",
 "LLLT"}

Returns: -1

Now there are no balancing constraints, so even though player 0 cannot lose and player 3 cannot win, the characters are balanced.

{"TTT",
 "TTT",
 "TTT"}

Returns: 0

Even with such lax balancing constraints, a perfectly matched set of characters is not balanced in the sense we are looking for.

{"TLLLLLTWWWWTLLWWWT",
 "WTTWTTLLWLLWWLTLWW",
 "WTTWWTLWTWLWWWWLTW",
 "WLLTLTWWWTWLWLLWLT",
 "WTLWTLWWWWLLWLLWTW",
 "WTTTWTWLLWTLLWWWLW",
 "TWWLLLTLLWTWWWLLWW",
 "LWLLLWWTWLLWWLLLWT",
 "LLTLLWWLTTWLTWTLWT",
 "LWLTLLLWTTTLLLLWTW",
 "LWWLWTTWLTTTLLWWLL",
 "TLLWWWLLWWTTLWTTLL",
 "WLLLLWLLTWWWTWLLWW",
 "WWLWWLLWLWWLLTTWLL",
 "LTLWWLWWTWLTWTTTWT",
 "LWWLLLWWWLLTWLTTLW",
 "LLTWTWLLLTWWLWLWTW",
 "TLLTLLLTTLWWLWTLLT"}

Returns: 17

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4617

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8006&pm=4617

Writer:

Enogipe

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Simple Math, Simple Search, Iteration