Connection Status:
Competition Arena > SlightlyBigger

SlightlyBigger

TCO19 Round 2B · 2019-04-15 · by misof

TCO19 Round 2B · 2019-04-15 · by misof · Advanced Math
Class Name: SlightlyBigger
Return Type: double
Method Name: getProbability
Arg Types: (int, int, int, int)
Problem Statement

Problem Statement

Yvonne and Zara are playing a game again. In this game their simultaneously choose a positive integer. (The chosen numbers can be arbitrarily large.) The goal of the game is to choose a number that is slightly larger than your opponent's number. More precisely:

  • If the numbers are equal, the game is a draw and there is no payment.
  • If the bigger number minus the smaller number is at most maxDiff, the person with the bigger number wins and gets ifNear dollars from the loser.
  • If the difference is larger, the person with the bigger number loses and pays ifFar dollars to the winner. The ifFar payoff is at least as big as the ifNear payoff.

You are given the values mentioned above and an int query. Consider the optimal strategy for the above game. If there are multiple strategies, pick the lexicographically largest one. (I.e., one that maximizes the probability of choosing 1, then the probability of choosing 2, and so on.) Return the probability with which Yvonne should choose the integer query.

Notes

  • Your return value will be accepted if it has an absolute or a relative error at most 1e-9.
  • The constraint "ifFar <= 2*ifNear" has no significance in terms of the solution idea, it was just added to (hopefully) avoid precision issues with numbers getting too close to zero.

Constraints

  • maxDiff will be between 1 and 25, inclusive.
  • ifNear will be between 1 and 50, inclusive.
  • ifFar will be between ifNear and 2*ifNear, inclusive.
  • query will be between 1 and 1000, inclusive.
Examples
0)
1
1
1
1
Returns: 0.3333333333333334

If your number is exactly one bigger than your opponent's, you win $1. If your number is bigger than that, you lose $1. In this setting, Yvonne should choose the integer 1 with probability 1/3.

1)
1
1
1
470
Returns: 0.0

In the same setting as before, the probability with which Yvonne should choose the integer 470 is either zero or negligibly small.

2)
1
1
2
1
Returns: 0.25

In the new setting you pay $2 if you exceed your opponent's number by more than 1 (and, symmetrically, you get paid $2 when your opponent's number exceeds yours by two or more). Perhaps surprisingly, in the new setting the optimal probability for the choice of the smallest possible integer is lower than before.

3)
3
4
7
3
Returns: 0.08005718370264478
4)
1
1
2
2
Returns: 0.5

Submissions are judged against all 91 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SlightlyBigger with a public method double getProbability(int maxDiff, int ifNear, int ifFar, int query) · 91 test cases · 2 s / 256 MB per case

Submitting as anonymous