Обсуждение @ 1208. Соревнование легендарных команд @ Timus Online Judge

Online Judge

Задачи

Авторы

Соревнования

NP-hard?!

Послано Erop [USU] 10 авг 2010 15:33

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

Re: NP-hard?!

Послано Sandro (USU) 11 авг 2010 11:42

Yes, this problem is NP-hard.

Re: NP-hard?!

Послано Andrey Ladeyschikov 4 июл 2019 11:06

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

Re: NP-hard?!

Послано Sandro (USU) 12 июл 2019 15:09

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