TopCoder problem "BasketballStrategy" used in SRM 313 (Division I Level Three)



Problem Statement

    

This problem statement contains images, subscripts and superscripts that may appear incorrectly or not appear at all in some plugins. In that case, use the standard view in the arena to see it correctly.

In a simplified version of basketball the goal is to score by getting the ball in a special scoring place. There are two teams, and each team contains the same number of players. When a player has possession of the ball, he has two choices: take a shot, or pass the ball to a teammate. When taking a shot, the player throws the ball in a straight line to the scoring place. When passing the ball, he throws the ball in a straight line to the target teammate. In both cases, at most one of the rival players will try to intercept the shot or pass.

The probability of a pass being successful is:

Cp * (1 - (ls / 150)2) * dr / (dr + 1)

And the probability of a shot being successful (score) is:

(Cs * dr / (dr + 1))ln(ls)

Where Cp and Cs are constants defined for the problem instance, ls is the length of the shot or pass, dr is the distance between the intercepting rival and the ball trajectory and ln is the natural logarithm (logarithm in base e).

When trying to intercept a shot or a pass, only the best suitable player of the other team to do so (i.e., the one that produces the lowest dr) will try. If no player on the other team can do it, the factor dr/(dr+1) in the formula is considered to have a value of 1 (i.e., it is ignored). A player of the rival team is only allowed to try to intercept the ball if the line that passes through him and is perpendicular to the ball trajectory intersects the trajectory at some point between the two endpoints of the trajectory, inclusive.

For example, in this picture:



There are 3 players in each team, green players are your team and red players are rivals. Player 0 has the ball and has 3 options marked as blue lines, 2 passes and taking a shot. The shot, if taken, can be intercepted by any of the rivals, but only number 2 will try because he is clearly the nearest. The pass to player 1 is impossible to intercept for the rivals, because any player that can intercept that pass should be inside the gray area. The pass to player 2 can be intercepted by rivals 1 or 2. Rival player 0 is not on an intersecting perpendicular line, so he cannot try to intercept it. In this last case, rival 1 will try to intercept because he is nearer than rival 2.

You will be given two String[]s team and rivals with the same number of elements representing the members of each team. Each element of team and rivals will be in the format "X Y" where X and Y will be positive integers with no leading zeroes representing the x and y coordinates of that player in the field. You will also be given Cp and Cs, the constants for the probability calculations of each type of movement. When the game starts, the ball is in possession of the player on your team with index 0. The scoring place is at X=50, Y=0. Your team is only allowed to take one shot, and you are to determine and return the probability that your team will score if it follows the best strategy. A strategy consists of zero or more passes followed by a shot. If your team loses the ball at any point during the strategy, you will not score. See examples for further clarification.

 

Definition

    
Class:BasketballStrategy
Method:scoreProbability
Parameters:String[], String[], double, double
Returns:double
Method signature:double scoreProbability(String[] team, String[] rivals, double Cp, double Cs)
(be sure your method is public)
    
 

Notes

-The returned value must be accurate to within a relative or absolute value of 1E-9.
-Pictures are just approximations. The players are considered to be perfect points with 0 surface and 0 length and trajectories and other lines are perfect lines with 0 surface.
-The same rival may try to intercept many passes along the game (see example 3 for further clarification).
 

Constraints

-team and rivals will each contain exactly N elements, where N is between 1 and 50, inclusive.
-Each element of team and rivals will be two integers between 1 and 99, inclusive, with no leading zeroes, separated with exactly one space character, with no leading or trailing spaces.
-All elements of team and rivals together will be distinct.
-Cp and Cs will each be greater than 0 and less than or equal to 1.
 

Examples

0)
    
{"50 50","35 60","70 15"}
{"75 5","72 25","45 17"}
1
1
Returns: 0.6100612919616956
This is the example from the problem statement. The best strategy is to pass the ball to player 2 and make him shoot.
1)
    
{"50 4"}
{"50 5"}
0.99
0.5
Returns: 0.3825461314703953
There's no teammate to pass the ball to, so you must take the shot directly. Since the only rival player is not in a position to intercept, the probability of making the shot is 0.5ln(4).
2)
    
{"50 4"}
{"50 3"}
0.5
0.5
Returns: 0.0
You can't pass the ball and your rival can perfectly block you; therefore it's impossible to score.
3)
    
{"50 50","40 50","40 40","40 30","50 20"}
{"50 41","44 29","48 27","45 41","48 64"}
0.999999
0.8
Returns: 0.25546407305110735
This picture illustrates the locations. The best strategy is marked in blue and the pink lines show possible interception lines from a nearest rival. Note that passes 2-3 and the shot taken by player 4 cannot be intercepted.



Here player 0 cannot take a shot because he will always be blocked. You should try to get the ball to player 4 so he can take the shot instead. Note that in this case it is better to make more passes and get to player 4 for the shot because the difficulty of longer passes and shots makes other strategies less likely to succeed.
4)
    
{"50 50","50 25"}
{"40 40","60 20"}
1
0.7
Returns: 0.20631213370921644
Note that getting closer can be better even if you are good at taking shots.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9993&pm=6546

Writer:

soul-net

Testers:

PabloGilberto , brett1479 , legakis , Olexiy

Problem categories:

Geometry, Graph Theory, Math