DEXTER - Dexter Rank
Dexter just participated in a coding contest and is now waiting for judge to give final result. He is very bored of waiting every time for result and now wants to find his expected rank based on current scoreboard and chances of failure for problems. Formally there are M problems in the contest and there are N coders in the contest. Dexter knows that coder i has submitted problem j with penalty of penalty[i][j]. Dexter knows that problem j will pass with probability prob[j] (this also applies for Dexter himself.) This is independent for each coder and problem. Now Dexter wants to know what would be his expected rank after system test.
Note: Coders are ranked based on number of correct solution, then total penalty for correct solutions. If there is tie even after that, all coders with same problems and penalty are given same rank.
Example: After system test if the score board is like this:
Coder 1: | 300 | -1 | -1 | Score: 1 | Penalty: 300 |
Coder 2: | 100 | -1 | 200 | Score: 2 | Penalty: 300 |
Coder 3: | -1 | 300 | -1 | Score: 1 | Penalty: 300 |
Coder 4: | -1 | -1 | 400 | Score: 1 | Penalty: 400 |
Ranks would be: 2 1 2 4
Input
The first line of input contains a single line T, which represents the number of test cases. For each test case first line contains two space separated integers N and M.
Then Next N lines contains M integers, jth integer on ith is penalty[i][j] which means penalty for ith coder on problem j, if he submitted jth problem, otherwise it is -1.
Dexter is first coder in the list.
Then next line contains M space separated integers, where ith integer denotes probability of passing problem i in system test, if submitted.
Output
Print the expected rank of the Dexter after system test with exactly 4 decimal places.
Constraints
1 <= T <= 16
2 <= N <= 256
1 <= M <= 12
1 <= penalty[i][j] <= 1000000 or penalty[i][j] = -1
0 <= prob[i] <= 100
Example
Input: 3 2 1 100 150 50 2 2 -1 -1 10 -1 0 100 3 2 100 200 -1 199 99 -1 50 50 Output: 1.2500 1.0000 1.6250
Explanation
For sample case 1, Dexter would have first rank if his solution passes or coder-2’s solution fails system test which has probability 0.75, otherwise he would have rank 2.answer = 1×0.75 + 0.25×2 = 1.2500
For sample case 2, all coders would be on rank 1 with 0 problem solved and 0 penalty in all cases, so answer = 1.0000.
hide comments
new_coder007:
2016-10-10 18:42:25
can u explain the third case ,ie the test case:
|
|
:D:
2013-02-25 21:35:52
Really nice problem. Made me remember why I like algorithmics so much :) |
Added by: | smit hinsu |
Date: | 2013-02-18 |
Time limit: | 4s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | CodeCraft 13 , own problem |