Jima's blog

Nice Problem From POI
By Jima, history, 8 years ago, In English

http://www.spoj.com/problems/MUSKET/ hello everyone,there is a nice problem from polish olympiad,i have tried to solve it but ... can someone explain how solve it? or if have some ideas share it each other. sorry for my bad english.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

To solve this problem you have to use dynamic programming to answer the question if ith and jth musketeer can be the last two fighters in the tournament. Then you just check which one wins this kind of duel and add the winner to the output. You can also have some fun simulating the tournament for x times, this kind of solution was given around 70% of points on the POI. If you have some more doubts, ask.

→ Reply