Arpa's blog

By Arpa, history, 20 months 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

»
20 months 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??

  • »
    »
    20 months 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.

    • »
      »
      »
      20 months 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?

      • »
        »
        »
        »
        20 months 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?