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.
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.
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.
