How to solve CREDCLRS?

This problem seems interesting but unfortunately nobody solved it during the contest…

Hey, the problem was set by aditya1sarode and myself. Our solution to the problem was slightly buggy and hence, incorrect. However, user fhlasek got it right and here’s the explanation of his solution:

Let’s imagine a graph where colors are vertices and there is a directed edge from x to y, iff x is needed to create y. The next step is to detect strongly connected components in that graph. After that I iterate through the components in the reverse topological order. For every such component I calculate how many colors is needed to create or how much dwell (I call this value balance of the component). Note that I can transfer units of colors freely inside a strongly connected component by breaking colors. I just keep track of this balance for all components and in the end just check if these balances are nonnegative. That’s almost it - just a few more details:

If a strongly connected components contains more edges than vertices, by repeatedly breaking all of the colors in the component, the balance can become arbitrary large (let’s call it infinity).
If there is an edge from a component x to y and y has at least two vertices -> balance[x] = infty, because we can repeatedly break colors from y.

1 Like