important question regarding ONEKING JAN15

Can anybody explain how ONEKING is not a set cover problem ? Each point can destroy some subset of segments and we have to choose minimum points whose union will give the universal set (here all kingdoms).

Set cover is NP-hard. wiki link. And its greedy is approximation algorithm. So I wonder how everybody’s getting it correct. Is it that writer didn’t notice it and framed question to pass by the greedy method(not the one mentioned in wikipedia). I also got ac by using one greedy method.

I thought of asking it during the competition but was apprehensive I might post some spoilers.

1 Like

ONEKING is easier - you cannot have one set covering point 1, 2 and 4 (without the point 3)…

Also number os available subsets is O(N^2) instead of O(2^N) as in “Set cover”.

@betlista can you explain a bit more . can’t understand your point.

Yes, ONEKING is a set cover problem, that is it can be reduced to set cover. However, that doesn’t show that it is hard. If you recall the definition of reductions, if a problem A reduces to a problem B, then that means B is at least as hard as A (or A is easier than B). So, reducing ONEKING to set cover just shows that set cover is at least as hard as ONEKING.

2 Likes

Can anybody explain how 2-SAT Problem is not a 3-SAT Problem ? Obviously a solution to 3-SAT can solve 2-SAT very easily, since 2-SAT is just simpler!

3-SAT is one of Karp’s 21 NP-complete problems. And its greedy is approximation algorithm. So I wonder how come there are so many 2-SAT problems in programming contest, and everybody just got it right!

I thought of asking it during the competition but was apprehensive I might post some spoilers.