Connection Status:
Competition Arena > DoraemonPuzzleGame

DoraemonPuzzleGame

SRM 628 · 2014-06-16 · by dreamoon

SRM 628 · 2014-06-16 · by dreamoon · Dynamic Programming, Math
Class Name: DoraemonPuzzleGame
Return Type: double
Method Name: solve
Arg Types: (vector<int>, vector<int>, int)
Problem Statement

Problem Statement

Doraemon is fond of playing puzzle games. Today he found a new puzzle game. This problem is about the first episode of this game.

The episode is divided into N levels, numbered 0 through N-1. You are allowed to play the levels in any order you like. Each time you play a level it takes you one minute. There are three possible outcomes: you either fail the level, or you clear it and get one star, or you clear it and get two stars. If you play the same level multiple times, only the best result is stored by the game. (Clearing is better than not clearing, and two stars are better than one.)

In order to advance to the next episode, you must clear all N levels, and the total number of stars you received must be at least m. (If you have enough stars but you did not clear some levels, you do not advance yet.)

You already know how good Doraemon is in each of the levels. You are given this information as int[]s X and Y. For each i, the values X[i] and Y[i] describe what happens when Doraemon plays level i:

  • With probability (1000 - X[i] - Y[i])*0.001, Doraemon will not clear the level.
  • With probability X[i]*0.001, Doraemon will clear the level and get one star.
  • With probability Y[i]*0.001, Doraemon will clear the level and get two stars.

You are also given the int m: the number of stars Doraemon needs to collect. Doraemon is trying to minimize the expected time he will need to finish the current episode. Assume that he always picks the next level to play optimally. Compute and return the expected number of minutes from the beginning to the episode to the moment when Doraemon finishes it.

Notes

  • When Doraemon plays the same level multiple times, we assume that the outcomes are mutually independent.
  • Your return value must have an absolute or relative error smaller than 1e-9.

Constraints

  • N will be between 1 and 2000, inclusive.
  • X and Y will each contain exactly N elements.
  • Each element of X and Y will between 1 and 1000, inclusive.
  • For each i, X[i] + Y[i] will not exceed 1000.
  • m will be between N and 2*N, inclusive.
Examples
0)
{800}
{200}
2
Returns: 5.0

There is only one level. Doraemon needs two stars to finish the episode. The only strategy is to play level 0 until he gets two stars. As that happens with probability 0.2, the expected time is 5 minutes.

1)
{1,999,999}
{999,1,1}
3
Returns: 3.0

In this episode, Doraemon will surely clear each level he plays. Thus, he needs to play each level at least once. The optimal strategy is to play each level exactly once, in any order. Once he clears all of them, he will also have enough stars. Note that for example after playing levels 0 and 1 Doraemon will almost certainly have enough stars. However, that is not enough - he is also required to clear all levels.

2)
{500,500}
{500,500}
3
Returns: 2.5

Here is one optimal strategy: Doraemon will start by playing each level once. With probability 0.75 he will collect enough stars and finish the episode. With probability 0.25 he will clear both levels but he will have only two stars. In this unlucky case, he can now play level 0 again and again, until he clears it for two stars.

3)
{250,250,250,250}
{250,250,250,250}
5
Returns: 8.25
4)
{250,500,250}
{500,250,500}
5
Returns: 4.962962962962963

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

Coding Area

Language: C++17 · define a public class DoraemonPuzzleGame with a public method double solve(vector<int> X, vector<int> Y, int m) · 55 test cases · 2 s / 256 MB per case

Submitting as anonymous