PREDICT - Editorial

Problem Link:

Practice

Contest

Difficulty:

Easy

Pre-requisites:

Probability

Problem:

In a game between team A and team B, you are given the probability that team A will win. If you bet M rupees on team X, and team X wins, then you gain 2 * (1-PX) * M rupees, whereas if team X loses, then you lose this M rupees. Starting out with 10000 rupees, what is the expected maximum value you can have, if you place your bets optimally?

Explanation:

We are given PA, and PB (= 1-PA). Let us bet M rupees on A and N rupees on B. Then, the expected gain/loss we will have is:

PA * (Payoff for team A winning) + PB * (Payoff for team B winning)
= PA * (2 * PB * M - N) + PB * (2 * PA * N - M)
= M * PB * (2 * PA - 1) + N * PA * (2 * PB - 1).

Note that, M * PB >= 0, and N * PA >= 0. Therefore, if PA > 1/2, the above is monotonically increasing in M, and decreasing in N. Thus, it is best if we bet M = 10000, and N = 0 in this case. If PA < 1/2, we have it monotonically decreasing in M, and increasing in N. Thus, in this case, it is best we bet M = 0, N = 10000.

Thus, final answer is as follows:


f(PA):
	if(PA >= 0.5):
		return 10000 + 10000 * (1 - PA) * (2 * PA - 1)
	else:
		return 10000 + 10000 * PA * (1 - 2 * PA)

Setter’s Solution:

Will be updated soon.

Tester’s Solution:

Can be found here

4 Likes

Well, it’s amazing when my solution is EXACTLY as the editorials one…

After all, there also some successes :smiley:

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <stdio.h>
using namespace std;

int main()
{
	int t;
	scanf("%d",&t);
	for(int i = 0; i < t; i++)
	{
		double pa;
		scanf("%lf",&pa);
		if(pa >= 0.50000)
			printf("%.10lf\n",2*10000*pa+10000.0*pa - 20000*pa*pa);
		else
			printf("%.10lf\n",10000+(10000.0*pa - 20000*pa*pa));
		}
	return 0;
}

Why to add 10,000 in the last step?

We add 10000 in last step as we have to return the total money he would have and not what he would earn.