BiddingWars
TCO20 Wildcard Parallel · 2020-10-06 · by lg5293
Problem Statement
Alice and Bob are playing a game on a directed acyclic graph with n nodes and m edges.
The nodes are labeled from 0 to n-1.
The edges are provided in the
Initially, there is a single token on node 0. Alice would like to move the token to node n-2, while Bob would like to move the token to node n-1. Nodes n-1 and n-2 will be the only nodes with outdegree zero in the graph, so it is guaranteed that the game will end on the token on one of these two nodes.
To move the token, Alice and Bob will play the game in turns. On each turn, they each will bid for the right to move the token along a single directed edge. Whoever wins the bid will be allowed to move the token after paying their bid. Both players know exactly how much money the other player has at any given moment, and can adjust their bid sizes based on that knowledge. Players can bid any fraction of their money (any non-negative real number less than or equal to their current amount of money). If bids are tied, they will be resolved randomly.
It can be shown that the winner of the game only depends only on the ratio of Alice's initial money to Bob's initial money. Suppose Alice starts with 1 dollar. She is wondering what is the largest non-negative real number r such that if Bob starts with strictly less than r dollars, Alice can force a win. If this value is unbounded (e.g. no matter how much money Bob starts with, Alice can win), then return -1. Otherwise, return the double r as the answer.
Notes
- - Your answer will be accepted if it has absolute or relative error at most 1e-9.
Constraints
- n will be between 3 and 100, inclusive.
- f,t will have the same length, and each will contain between 1 and 2,500 elements, inclusive.
- 0 ≤ f[i] < t[i] ≤ n-1 for all valid i.
- Nodes n-2 and n-1 will be the only nodes with outdegree zero.
3
{0,0}
{1,2}
Returns: 1.0
If Alice has 1 dollar, and Bob has less than 1 dollar, Alice can always win the bid. Otherwise, if Bob has at least one dollar, there is a possibility Alice won't be able to win.
4
{0,1}
{3,2}
Returns: 0.0
Alice can't win no matter what, so the correct return value in this case is 0.
4
{0,1}
{2,3}
Returns: -1.0
Alice can win no matter what in this case.
9
{0,0,1,1,2,2,3,3,4,4,5,5,6,6}
{1,8,2,8,3,8,4,8,5,8,6,8,7,8}
Returns: 0.14285714285714288
If Bob starts with less than 1/7 of a dollar, then Alice can guarnatee a win.
9
{0,0,1,1,2,2,3,3,4,4,5,5,6,6}
{1,7,2,7,3,7,4,7,5,7,6,7,7,8}
Returns: 7.0
3
{0,0,0,0,0}
{1,2,1,2,1}
Returns: 1.0
This test case has the same answer as Example 0.
Submissions are judged against all 112 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BiddingWars with a public method double findMax(int n, vector<int> f, vector<int> t) · 112 test cases · 2 s / 256 MB per case