Блог пользователя d3mon95

New Year and Rating Help!!
Автор d3mon95, история, 8 лет назад, По-английски

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

  • Проголосовать: нравится
  • -21
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

why negative, it is new year

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Check this out

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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://mirror.codeforces.com/contest/750/submission/23462718

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 :)

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      → Ответить
      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        → Ответить
        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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?

          → Ответить
          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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
            → Ответить