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?
