Hi!

One of my students got the following problem on a competition.

Given a undirected graph with $$$N\leq 100$$$ vertices and $$$M\leq 1000$$$ edges. $$$1\leq K\leq N$$$ vertices are considered special and you are given their numbers. Each edge has a "safety" characteristic — a real number between $$$0$$$ and $$$1$$$.

The task is to find the longest cycle, which has at least half of special vertices and the product of safety on the edges is at least $$$0.5$$$.

It seems to me that this problem with $$$K=1$$$ is the same as finding the longest cycle in a graph, but as far as I know this is NP-hard.

Is it unsolvable in polynomial time or did I miss something?

P.S. I have a screenshot of the statement but it is in Russian. If you want — I can post it in the comments, but I warn you — it is very bad:)