I_love_PMK's blog

NP problem in Polish OI.
By I_love_PMK, 9 years ago, In English

Today I found a problem in XXI Polish OI.

Tourism

But I think it's a NP problem, base on this

I've tried greedy solution, but got 45 points. I'm looking for a solution on Polish OI page but it doesn't have. Someone please help me, thank you.

  • Vote: I like it
  • +13
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +18 Vote: I do not like it

From the original statement:

"The councilor observed that the current road network does not allow for a long journey. Namely, wherever one starts the journey, it is impossible to visit more than 10 towns without passing through some town twice."

→ Reply
»
9 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Someone please help :<

→ Reply