Hi, Codeforces Community!

Today I virtually participated in the SWERC2023 Contest with my ICPC teammates. We ended up solving 8 problems. Among all of those problems, I particularly enjoyed B. However, I noticed that the approach I use is very different from the standard solution. Let me share the problem with you:

There are $$$N$$$ countries, each country's (let it be $$$i$$$) flag uses $$$k_{i}$$$ colors (There are at most $$$M$$$ distinct colors in total). You want to "buy" some colors to paint all the countries' flags. If the colors you bought cannot paint a certain country's flag, you have to buy the flag. The cost of buying a flag and buying a color are all $$$1$$$. What's the minimum cost to make all the flags (by buying colors and flags)?

$$$N \leq 1000, M \leq 100$$$

The standard solution is as follows:

Build a graph that has $$$(N + M)$$$ nodes which represent the countries and colors. Connect each country to all the colors of its flag. Now we want to find the minimum amount of nodes to "cover" all the edges (for every flag, select itself or all of its colors). This is a classical "minimum vertex cover" problem. Since the graph is bipartite, the answer is equal to the maximum matching. We can either use the Hungarian algorithm or any max-flow algorithms (Edmonds-Karp, Dinic...) to solve it.

But I solved this problem by greedy:

We initially select all the colors available. Each time, we remove one of the color from our set and maximize the flags that are covered by the remaining colors. Add the number of flags that are not covered by our colors to the cost. And we use this cost to update the answer.

This approach works in $$$O(N^2M)$$$

However, I cannot prove the correctness of this algorithm. Can anyone give some hack cases or a formal proof of it?

Link to my code is Here