Link to problem USACO
I’ve spent some time thinking about the problem, and I got stuck on a few questions. So I eventually looked up the solution but can’t make sense of it.
Firstly, why do we start the bfs from the zeroes only? The way I read the statement, it’s possible that the input doesn’t contain any but the pie exchange ends because all the pies have been used up / there are no suitable pies any longer. If we start the bfs from zeroes only wouldn’t this produce wa?
Secondly, I’m struggling to prove to myself the correctness of the bfs even beyond that. How exactly do we ensure we haven’t used up a pie previously. For example, if B gives E a pie 10 10, then E gives B a pie 11 2, then B should respond with a pie > 2, so 10 10 qualifies. I understand that in the bfs solution this won’t happen because we’ve already marked the pie as visited. But I’m struggling to understand how having just the pie number is enough information to solve the problem independent of how we got there. In my thinking on the problem, I had the intuition that we’d have to somehow keep more than the pie number as a state.
I would appreciate if someone who understands the problem shed some light on it for me.
Blago