d3mon95's blog

New Year and Rating Help!!
By d3mon95, history, 8 years ago, In English

However hard i try i m unable to get the logic behind this problem of goodbye 2016 contest plz help somebody..

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

Comments Comments (11)
| Write comment?
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

why negative, it is new year

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

Check this out

→ Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I've used binary search the answer to find out the maximum possible rating.It's relatively easier to implement and understand.

Check out my code http://codeforces.me/contest/750/submission/23462718

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

    nice code, I really understood your code, I think its an editorial on its own .. Thanks

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

can anyone explain problem C(New Year and Rating) in detail please.I have understood clearly the part mentioned in Errichto's blog ->

For every contest we know that the current rating is x increased by some prefix sum of c_i (changes of rating). If Limak is in the division 1, we have inequality x+prefSum >= 1900 so we have x >= 1900-prefSum. If Limak is in the division 2, we have inequality x_prefSum <= 1899 so it is x <= 1899-prefSum. From this set of inequalities, your task is to find the biggest x satisfying all of them.

now, how to find the biggest x and when to print infinity? Thanks, in advance :)

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

    Keep the maximum and minimum starting rating in two separate variables, e.g. ma and mi.

    When you're competing in a division 1 contest, the inequality x >= 1900 - prefixSum holds. Therefore you might need to increase mi. You can do this with the update mi = max(mi, 1900 - prefixSum). Because we take the maximum, the new mi will satisfy all old division 1 constraints and also the new one.

    Do the reversed thing when you're in a division 2 contest: ma = min(ma, 1899 - prefixSum).

    If mi > ma at the end, then no solution is possible. Otherwise ma will be the biggest starting raking and ma + prefixSum will be the rating at the end of the year.

    My submission: 23523630

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

      When you're competing in a division 1 contest, the inequality x >= 1900 — prefixSum holds. So we need to maximize x here, right? which is done by mi = max(mi, 1900 — prefixSum) this step. so , we are storing max possible value in mi.. then maximum will always be greater than minimum, so why this statement->If mi > ma at the end, then no solution is possible ? and at the end we can simply print the maximum value which is stored in mi . why are we not doing that?

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

        No, you mixed up the variables! mi holds the current minimum starting rating (the lower bound), not the maximum. ma holds the current maximum starting rating (upper bound).

        x >= 1900 - prefixSum gives a new lower bound for the starting rating x, therefore we need to update the lower bound mi. And we need do update mi by using the maximum, because mi has to satisfy all lower bound constraints.

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

          I sincerely than you for helping me so much, one small and last doubt. If x is the initial rating at i=0, then you are computing the maximum and minimum possible values of x(ma and mi respectively). Then with the max initial rating you are adding the prefix sum and getting the final answer.

          My question is that if ma is the maximum possible initial rating then while obtaining that value of ma why are you doing 'min' i.e. min(ma,1899-prefixSum)? why min?

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

            Because the inequality x <= 1899 - prefixSum. This inequality gives a upper bound. x has to be smaller than the value. So at the moment we know x <= ma and x <= 1899 - prefixSum. We can combine these two inequalities: clearly x has to be smaller than min(ma, 1899 - prefixSum), therefore we get the new ma.

            If you're unsure how to combine two inequalities, think about the following problem. Which numbers x satisfy both the inequality x < 5 and x < 3?

            Spoiler
            → Reply