Arpa's blog

Topcoder SRM #780 Editorial
By Arpa, history, 5 years ago, In English

Here is the link to the editorial. Feel free to discuss problems and ask me questions. I'll be glad to improve the editorial with your comments.

  • Vote: I like it
  • -8
  • Vote: I do not like it

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

I'm not getting div2 c ...how it is linked to knapsack?? can you explain the logic more clearly??

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We want to find the probability of gaining i scores in games other than G. It's similar to finding in how many ways we gain i scores. It's a knapsack problem.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      we need to gain i scores in such a way that after adding G to it .It must become greater than n*(n+1)/4.In other words we need to look for only those i's such that after adding G to it ,it can become greater than n*(n+1)/4.Am i right?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        and we'll use knapsack to find those i's and we won't be using G as a weight?

        → Reply