Expected Matches
Practice
3.8 (40 votes)
Dynamic programming
Exception handling
Approved
Medium
Ready
Open
Probability and statistics
Problem
49% Success 255 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

A competition is being held between two teams: A and B. Team A has N players numbered from 1 to N. Team B has M players numbered from 1 to M.

The competition requires certain number of matches to be played. In each match, one person from each of the teams goes against one another, until one of them is defeated. The loser is then replaced by another player from his/her team. The team that fails to replace its player (means all players have already lost), loses the competition and no more matches are held.

To be more clear, the players in each team line up to play in their order. That means the first match will be always between the player number 1 in team A and the player number 1 in team B. After the first match, if the player number 1 in team A loses, then he/she will be replaced by the player number 2 in his team, i.e, the second match will be between player number 2 in team A and player number 1 in team B (in case team A has more than one player). Otherwise, the second match will be between player number 1 in team A and player number 2 in team B (in case team B has more than one player). And the two teams keep competing based on that rule until one team has all its players lost.

Given the probability of a player beating another, can you find the expected number of matches that will be played?

Input:

The first line of input file contains T, the number of test cases.
Each test case starts with two space-separated integers, N and M, denoting the number of players on team A and team B, respectively.
Each of the next N lines contains M decimal numbers, separated by a single space. The jth decimal number on ith line denotes the probability that the player number i of team A shall defeat the player number j of team B. All the decimal numbers only contain up to 2 digits after the decimal point.

Output:

Output exactly T numbers, each denoting the expected number of matches to be held in scenario of the corresponding test case. Print the answer upto 6 digits after decimal point. As, Hacker-Earth uses exact matching, you should ensure to print exactly 6 places.

Constraints:

1 ≤ T ≤ 3
1 ≤ N, M ≤ 1000

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
3 votes
Tags:
MathematicsMediumOpenApprovedProbability and Statistics
Points:30
Tags:
Dynamic ProgrammingApprovedMediumProbability and Statistics
Points:30
3 votes
Tags:
Dynamic ProgrammingMatrixProbability spacesAlgorithmsProbablityModular exponentiation