On yesterday's div3F, i've seen multiple solutions detailing this. 1872F - Selling a Menagerie
- Let's model it as how much index i get's affected if we sell i right now.
- Maintain it in a set.
- Always sell the index i that is least affected.
I get that we should always sell an index i that such that for all j, no Aj = i,
However, when there are some Aj = i, why is it optimal to sell the one that get's affected the least?
- How can we prove it's optimal
- Is it ever possible to sell another thing that is currently afraid of the minimum, thereby decreasing the minimum more, such that the sum of all affected will in fact be less.
Implementation details here. 222332183
Thanks for the help everyone!
Not sure if this will clear your doubt, but if you model the problem with a directed graph, you essentially report the toposort as the answer, and whenever you encounter a cycle, you need to break it — so when you are breaking the cycle, you need to pick the node that is least affected, if you remove it's outgoing edge.
The reason we can do this greedily is that since there is only a single outgoing edge from a given node in the diagraph, any node may only be part of a single cycle, so it's optimal to pick the least affected node — no other cycle is affected by doing this.
I don't think the greedy algorithm ensures we remove the nodes in the cycle in a specific manner. That may prevent it from being optimal, so why is my solution working?
The 'specific manner' is just choosing the least affected node. Since 2 cycles never intersect, it is not optimal to break up a cycle by removing an edge which is not going out of the least affected node. If there are multiple cycles, then breaking them up is independent of each other, so you can just choose to keep breaking up the cycle containing the least affected node out of all cycles combined until there are no cycles left.
I'm saying, the algorithm may choose 2 nodes in a cycle in an order that's unpptimal.
It won't. The only time you are getting a[i] instead of 2*a[i], when there is a cycle. After breaking the cycle, there is a straight line, in which the end node is unaffected.
ok lets put it this way.
Let's say our graph is a perfect cycle. Obviously the optimal solution would be to toposort and pick the node thats the least a[i], and keep going backwards.
however, the algorithm may not keep going backwards. that's the issue
It would, because you break the cycle by updating how much $$$a_i$$$ is affected to 0, causing a chain reaction in directed order.
How are we sure that the node before ai would then be the least?
Do you mean the node after $$$i$$$? Say $$$i$$$ is chosen because it is the smallest in the set (least $$$p_i$$$). $$$j=a_i$$$ would be the node after $$$i$$$ whose $$$p_j=c_i$$$. After removing $$$i$$$ from the set and updating $$$p_j\gets p_j-c_i=0$$$, $$$j$$$ is guaranteed to be chosen next because 0 is the smallest.
I meant the node selected right after ai.
Well the same thing I described that happens to $$$i$$$ will also happen to $$$a_i$$$ in the next iteration, and so on until the entire cycle finishes then it moves on to the next cycle if any.