Connection Status:
Competition Arena > RerollCheater

RerollCheater

SRM 831 · 2022-06-06 · by misof

SRM 831 · 2022-06-06 · by misof · Greedy, Sorting
Class Name: RerollCheater
Return Type: int[]
Method Name: reroll
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

You are playing a computer game in which you roll some 20-sided dice.

You have just started one round of the game by taking some dice and rolling them. The numbers you got are given in the int[] currentDice.


Your ultimate goal is to maximize the sum of the numbers on your dice.

You are now allowed to make between zero and N consecutive rerolls. For each reroll, you choose one of the dice you have and you roll it again to get a new "randomly selected" value.

For each reroll you can select any one of the dice currently in front of you. You may reroll each die multiple times.


However, there's one big catch. As we said above, these are not real dice, this is just a computer simulation. You have discovered that the game uses a deterministic pseudorandom generator to simulate the dice rolls, and you can predict the values it's going to generate with 100 percent accuracy. The int[] futureRolls has exactly N elements: the values that will come up the next N times you'll roll a die. (The values are given in the correct order. I.e., the first die you'll reroll will give you the new value futureRolls[0], the one after that will give futureRolls[1], and so on.)


Find one way to maximize the final sum of the dice in front of you. If your solution has K rerolls, return a int[] with K elements: for each step, in order, the 0-based index of the element of currentDice you want to reroll in that step.

Notes

  • Any valid solution will be accepted.
  • It is not required to minimize the number of rerolls.

Constraints

  • currentDice will have between 1 and 100 elements, inclusive.
  • futureRolls will have between 1 and 1000 elements, inclusive.
  • Each number in the input will be between 1 and 20, inclusive.
Examples
0)
{1, 2, 1, 1, 1, 1}
{20, 20, 20}
Returns: {3, 4, 5 }

Your initial roll was really unlucky: you rolled five ones and a two. You can now make up to three rerolls. You know that each of those will give you a 20. The best strategy is to reroll any three distinct dice that show ones. The return value {3, 4, 5} corresponds to the following sequence of rerolls: currentDice[3] := futureRolls[0] currentDice[4] := futureRolls[1] currentDice[5] := futureRolls[2] In the end, we will have dice with the following values: {1, 2, 1, 20, 20, 20}.

1)
{4, 7, 13, 19}
{1, 1, 2, 3, 1, 4, 1, 3}
Returns: { }

The upcoming rolls are all quite low, so we cannot improve the dice we initially rolled. Thus, one of the optimal solutions for this test case is to do nothing.

2)
{18, 11, 15, 12}
{3, 14, 9}
Returns: {1, 1 }

Remember that you may reroll the same die in multiple (not necessarily consecutive) rounds. Here we reroll the 11 to get a 3, and then we reroll the 3 again to get a 14 instead.

3)
{10, 9, 20, 8}
{1, 2, 3, 4, 5, 6, 7, 10, 1, 2, 3, 4, 5, 6, 7, 11, 1, 2, 3, 4, 5, 6, 7}
Returns: {1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 3, 3, 3, 3, 3 }
4)
{3}
{1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 6, 1, 5, 1, 4, 1, 3}
Returns: {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

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

Coding Area

Language: C++17 · define a public class RerollCheater with a public method vector<int> reroll(vector<int> currentDice, vector<int> futureRolls) · 127 test cases · 2 s / 256 MB per case

Submitting as anonymous