QuestionOrder
SRM 829 · 2022-05-10 · by misof
Problem Statement
You are taking part in a game show.
The host has just shown you a board with multiple question subjects. For each subject you can see the amount in dollars it is worth. The amount for subject i is A[i]. You have practiced a lot and so you know that you will answer a question about subject i correctly with probability exactly P[i] percent.
The game will be played in turns. In each turn you select a subject, a question about that subject is revealed and you have to give an answer. Then, one of two things will happen: If you answered correctly, the amount for that subject is added to your bank. But if you answered incorrectly, you lose all money currently in your bank.
During the game you must select each subject exactly once. After you selected the last subject and (correctly or incorrectly) answered the last question, the amount in your bank are your winnings.
Your goal is to maximize the value E = the expected value of your winnings. Find out the optimal order in which you should select the subjects.
Clearly, if there are N questions, E * 100^N is always an integer. Return this integer modulo (10^9 + 7).
Constraints
- A will have between 1 and 500 elements, inclusive.
- Each element of A will be between 1 and 1000, inclusive.
- P will have the same number of elements as A.
- Each element of P will be between 0 and 100, inclusive.
{100, 100, 100}
{50, 50, 50}
Returns: 87500000
Three equivalent questions. You will get each of them right with probability 50 percent, and if you do, the question will contribute 100 dollars to your bank. There are eight equally likely sequences of correct and incorrect answers. We can compute your expected winnings as the average of your winnings in those eight cases. (The actual expected value is E = 87.5)
{50, 1000}
{10, 0}
Returns: 50000
You have no chance with the second question, and it's clearly a dumb idea to take it second - it will just empty your bank. If you do the impossible question first and the hard question next, in 90% of cases you still get nothing but in 10% of cases you get 50 dollars. Thus, the better strategy gives you an expected profit E = 0.1 * 50 = 5 dollars.
{100, 200, 500, 1000}
{90, 80, 40, 20}
Returns: 559999699
In this particular example the harder questions happen to be worth more money. When following the optimal strategy, your expected score will be E = 435.6; then the actual return value is (43,560,000,000 mod 1,000,000,007).
{50, 50, 100, 100, 250, 250}
{90, 85, 50, 45, 60, 10}
Returns: 373328337
{47}
{0}
Returns: 0
Submissions are judged against all 101 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class QuestionOrder with a public method int maxExpProfit(vector<int> A, vector<int> P) · 101 test cases · 2 s / 256 MB per case