HackerRank : Moody’s Analytics University Hackathon – Small Risk Trading

By | September 29, 2016

A company can make at most of available trades. Each available trade has the following properties:

  • : A floating-point number denoting the trade’s probability of being profitable.
  • : A floating-point number denoting the trade’s potential profit.
  • : A floating-point number denoting the trade’s potential loss, which has a probability of .

Given the values of , , and , , and for each trade , find and print the maximum expected amount of money the company can make by performing at most of the trades.

Input Format

The first line contains two space-separated integers denoting the respective values of (the number of trades available) and (the maximum number of trades allowed).
The second line contains space-separated floating-point numbers describing the respective values of , where each denotes the probability that the transaction will result in a profit.
The third line contains space-separated floating-point numbers describing the respective values of , where each denotes the possible profit of the transaction.
The fourth line contains space-separated floating-point numbers describing the respective values of , where each denotes the possible loss of the transaction.

Constraints

  • All , , and are floating-point numbers scaled to exactly one decimal place (i.e., format).

Output Format

Print the maximum expected amount of money that can be made by performing at most of the available trades. Scale your answer to exactly decimal places (i.e., format).

Sample Input 0

4 2
0.5 0.5 0.5 0.5
4.0 1.0 2.0 3.0
4.0 0.5 1.0 1.0  

Sample Output 0

1.50

Explanation 0
There are transactions available and we can perform at most of them. We also know that the probability that each transaction results in a profit is . If the third and the fourth transactions are performed, the expected amount of money made from these transactions is: ; because this is greater than all the other possibilities we could calculate, we print as our answer (recall that we must scale our answer to two decimal places).

Sample Input 1

2 2
0.9 0.5
1.0 0.5
100.0 0.4

Sample Output 1

0.05

Explanation 1
There are transactions available and we can perform at most of them. The probability that the first transaction is profitable is , while the probability that the second transaction is profitable is . We can maximize our potential profit by only performing the second transaction, which has an expected value of ; thus, we print as our answer.

Solution

Thanks to Maxxy for suggesting the approach here.
The approach to solution is :

Store probability of profits(p) in a List.
Similarly store potential profits(x) and potential loss(y) in two other array 
lists.

Now traverse the lists and store corresponding profits ( calculated as per the 
formula given 
in description).
profitInEachTrade = P.get(i)*X.get(i)-(1-P.get(i))*Y.get(i);

Add the profits in another array List.
Sort this array List in reverse order.

Now we need all the profits ( i.e, if the value of final array List is greater 
than zero) and we have to add trades at most k only.

So we traverse the list and check if value is greater than zero and count is 
less than k, we add the values to get the final profit.

Using Decimal format or other methods, you can print the value to two decimal 
places finally.