Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

Arpa's blog

Topcoder SRM #780 Editorial
By Arpa, history, 7 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

»
7 years ago, hide # |
 
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
  • »
    »
    7 years ago, hide # ^ |
     
    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
    • »
      »
      »
      7 years ago, hide # ^ |
       
      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