Arpa's blog

By Arpa, history, 21 month(s) 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

»
21 month(s) 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??

  • »
    »
    21 month(s) 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.

    • »
      »
      »
      21 month(s) 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?

      • »
        »
        »
        »
        21 month(s) 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?