Discussion @ 1208. Legendary Teams Contest @ Timus Online Judge

NP-hard?!

Posted by Erop [USU] 10 Aug 2010 15:33

very similar to the NP-complete problem 3-dimensional matching (3-сочетания)

Re: NP-hard?!

Posted by Sandro (USU) 11 Aug 2010 11:42

Yes, this problem is NP-hard.

Re: NP-hard?!

Posted by Andrey Ladeyschikov 4 Jul 2019 11:06

i have a not brute force solution. The conditions of the problem impose restrictions on the graph

Re: NP-hard?!

Posted by Sandro (USU) 12 Jul 2019 15:09

But your algorithm is wrong :) We added more tests and now you have WA. Thank you!

Discussion of Problem 1208. Legendary Teams Contest