Hello,

Here is the problem: https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff48/00000000003f4dea
Here is my solution: https://ideone.com/pazUnT It passed the first testset successfully.

My solution is a simple DP with 2 parameters.
$$$have$$$ is a vector of size $$$M$$$. $$$have[j]$$$ contains the number of times die face $$$j$$$ has been locked in previous rolls.
$$$dp[i][have]$$$ is the expected number of rolls (When rolling optimally) to create the desired $$$K$$$ groups from dice $$$i...n$$$ having previous rolls represented in $$$have$$$.

What I need help with is the 'rolling optimally' part. I assumed that we will only reroll a die iff the resulting configuration (represented in $$$have$$$ vector) can not possibly create the desired $$$K$$$ groups no matter how we roll the rest of the dice. Otherwise, we will keep our roll and move on to the next die.

How do we prove that it is never optimal to reroll when we have a configuration that can reach an answer?

My attempt was the following:
let $$$E(s)$$$ represent the answer for state $$$s$$$, and $$$R(s)$$$ represents the expected number of rerolls we need to get state $$$s$$$ from our current state.
let $$$a, b$$$ both be valid states that we can reach from our current state. Both $$$a, b$$$ can reach an answer. And $$$E(a) < E(b)$$$.
It is optimal to reroll after reaching state $$$b$$$ iff $$$E(a) + R(a) \leq E(b)$$$.
$$$R(a)$$$ is actually equal to $$$M$$$ since next state is defined only by what die face we get. The probability to get any face is $$$1/M$$$ and the expected value is $$$M$$$. So we it's optimal to keep rerolling iff $$$E(b) - E(a) \geq M$$$.

I have failed to progress any further and I don't even know if that approach is even correct. I think my proof attempt is missing a sort of a case where we're not targeting a specific die face but considering rerolling until we reach one of several die faces or reach a number of rerolls. Please correct me or tell me another approach.

Thanks.