OJ Board

Hello,
this is maximum independent set problem, which is NP-complete. So how can it be solved in 15 seconds?

Hello,
I am getting WA. My program works good for input posted here. Did you assume that the names of cities don't contain spaces?

I have used logarithm to solve this problem. log(nCi)=log(nC i-1)+log(n-i)-log(i).

The smallest number is about 2^-50000. But log(2^-50000)=-34657.359 and there is no problem with precision. If log(nCi)+(n-1)*log(0.5) is small enough, you can ignore it.