EvenToWorldFinal's blog

By EvenToWorldFinal, history, 2 months ago, In English

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 number of 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

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

wow your team is very good

»
2 months ago, # |
Rev. 4   Vote: I like it +9 Vote: I do not like it

I tried to make a hack case but I couldn't see your code so I'm not sure if it works.

7 11
8
1 2 3 4 6 7 8 9
8
1 2 3 5 6 7 8 10
8
1 2 4 5 6 7 9 10
8
1 3 4 5 6 8 9 10
8
2 3 4 5 7 8 9 10
1
11
1
11

The idea is that you trick the algorithm into removing color 11, forcing a cost of one extra.

I think the optimal cost should be 6 but the greedy algorithm will return 7. Can you tell me if this is correct?

Also sorry the test case is so large. I didn't know if your greedy algorithm was removing unused colors after each step.