Connection Status:
Competition Arena > Cascade

Cascade

SRM 793 · 2020-11-03 · by misof

SRM 793 · 2020-11-03 · by misof · Dynamic Programming, Math
Class Name: Cascade
Return Type: int
Method Name: expectedPower
Arg Types: (int, vector<int>, vector<int>, string, int, int, int, int)
Problem Statement

Problem Statement

In Magic: the Gathering, some cards have the ability "cascade" that allows the player to play another cheaper card for free. Without using too many terms specific to this card game, we can rephrase this ability as follows:

  • When you play a card X with 'cascade', reveal cards from the top of your deck of cards until you either reveal a card C with a strictly smaller cost than card X, or reveal the entire deck.
  • If you revealed the entire deck without finding a card cheaper than card X, terminate the process.
  • Shuffle all the revealed cards other than card C, and place them onto the bottom of the deck.
  • Play card C. (This card can also have cascade. If it does, resolve it in the same way.)

Your deck contains N cards. Each of those cards has three properties: it has some non-negative integer cost cost[i], it has some non-negative integer power power[i], and it may have cascade (cascade[i] is either true or false). In the beginning, the entire deck is shuffled and you know nothing about the order of cards in the deck.

(Note that already after you resolve the first cascade you know which cards were put to the bottom of the deck and thus the order of the cards in the deck is no longer completely random. E.g., if there is a second cascade, the cards revealed first will be the cards that weren't revealed during the first cascade.)


You have just played another card (not from your deck). The cost of this card is greater than the cost of any card in your deck, the power of this card is 0, and it does have cascade. Calculate and return the expected total power of cards you will play. More precisely, the answer is a rational number P/Q. Return PQ^(-1), where Q^(-1) is the inverse element to Q modulo 10^9 + 7.


Please use the following pseudocode to generate the arrays cost, power, cascade: 


L = len(costPrefix)
for i = 0 .. L-1:
    cost[i] = costPrefix[i]
    power[i] = powerPrefix[i]
    cascade[i] = (cascadePrefix[i] == 'Y')

state = seed
for i = L .. N-1:
    state = (state * 1103515245 + 12345) modulo 2^31
    cost[i] = state mod CM
    state = (state * 1103515245 + 12345) modulo 2^31
    power[i] = state mod PM
    state = (state * 1103515245 + 12345) modulo 2^31
    cascade[i] = (state < CT)

Notes

  • "Shuffle" means "rearrange into a permutation chosen uniformly at random from all possible permutations". All shuffles are mutually independent.
  • It can be shown that for each valid test case the answer P/Q (as a reduced fraction) has the property that Q and 10^9 + 7 are relatively prime.

Constraints

  • N will be between 1 and 100,000, inclusive.
  • L will be between 0 and min(N, 500), inclusive.
  • costPrefix, powerPrefix and cascadePrefix will each have length L.
  • seed will be between 0 and 2^31 - 1, inclusive.
  • CM will be between 1 and 10^6, inclusive.
  • PM will be between 1 and 10^6, inclusive.
  • CT will be between 0 and 2^31 - 1, inclusive.
  • Each element of costPrefix will be between 0 and 10^6 - 1, inclusive.
  • Each element of powerPrefix will be between 0 and 10^6 - 1, inclusive.
  • Each character of cascadePrefix will be either 'Y' or 'N'.
Examples
0)
2
{10, 20}
{100, 200}
"NN"
0
1
1
0
Returns: 150

Two cards: one has cost 10 and power 100, the other has cost 20 and power 200, neither has cascade. When we resolve the initial cascade, we will reveal the top card of the deck and play it, and that's all. The expected total power of the cards played is therefore (100 + 200) / 2 = 150.

1)
2
{10, 20}
{100, 201}
"NN"
0
1
1
0
Returns: 500000154

The same test case as before, but now the expected total power of the cards played is 301/2, which is not an integer. The returned value is (301 * 2^(-1)) mod (10^9 + 7) = (301 * 500,000,004) mod (10^9 + 7) = 500,000,154.

2)
2
{10, 20}
{100, 200}
"NY"
0
1
1
0
Returns: 200

The same test case as Example 0, but now the more expensive card has cascade. If we reveal that one first, we will also cascade into the cheaper one. Thus, with probability 1/2 we will just play the cheaper card (power 100) and with probability 1/2 we will play both cards (total power 100+200 = 300).

3)
6
{1, 1, 1, 2, 1, 0}
{10, 20, 30, 40, 50, 60}
"NNNYNY"
0
1
1
0
Returns: 666666712

The fact that the last card (cost 0, power 60) has cascade does not matter - if we play this card and resolve its cascade, it certainly won't do anything because there are no cards cheaper than this one. The exact answer as a reduced fraction is 122/3.

4)
10
{4, 7}
{47, 42}
"YN"
474747
10
100
1250000000
Returns: 487500069

The full test case should look as follows: cost: 4, 7, 0, 9, 0, 5, 8, 5, 6, 5, power: 47, 42, 49, 60, 15, 22, 85, 32, 87, 34, cascade: true, false, true, false, false, false, true, true, true, false, The exact answer as a fraction is 5247/80

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

Coding Area

Language: C++17 · define a public class Cascade with a public method int expectedPower(int N, vector<int> costPrefix, vector<int> powerPrefix, string cascadePrefix, int seed, int CM, int PM, int CT) · 105 test cases · 2 s / 256 MB per case

Submitting as anonymous