Can someone explain the Expected Value recurrence for 2022 Feb Gold: Cow Camp?

I recently started upsolving the last USACO Gold problems (2022 Feb), but I couldn’t understand the first part of the solution for “Cow Camp”, pasted below:

I don’t understand the recurrence at all.

My current understanding is that after x submissions, we have 2 cases: Either we have already stopped because we achieved more than E_x test cases in a previous submission, or we plan to use the very last (the x+1th) submission. The probability of the first case happening can be found with complementary counting; it equals 1 - P(none of the first x submissions have a score of more than E_x). The probability of the second case is just 1 - P(first case).

But the recurrence doesn’t seem to use either of these probabilities. Instead, I seem to be misunderstanding the two cases. The first term obviously corresponds to the second bullet point, and the second term to the third bullet point. But:

  • Does the “current submission” (first bullet point) mean the xth one?
  • Where does the E_x come from in the first bullet point?
  • Why does the recurrence only seem to consider the very last submission?

Honestly, I think the most helpful would be another complete explanation of the recurrence. Can someone give me some pointers in the right direction?

1 Like

I admit that “current submission” is ambiguous; it should actually be “first submission.” Does this make more sense?

1 Like

Yes, this clears it up! The key for me was the clarification that we are doing casework on Bessie’s first submission - now it’s obvious that the next x submissions have an expected score of E_x. I know understand how the recurrence works - thanks a lot!