PREDICT - Editorial

editorial
, , , ,
1

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

3 Likes
2

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;
}
3

Why to add 10,000 in the last step?

4

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