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

Автор vkgainz, история, 3 года назад, По-английски

Good luck to everyone! Comment if you're taking tomorrow!

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

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

+

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

Is there a mirror?

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

How to solve G (Sky's the Limit)?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    Let A[i] be the input array, and let B[i] be an array satisfying B[i] = (B[i-1] + B[i+1]) / 2 + K. (There's a pretty simple pattern we can use to generate B[i].) Then, let C[i] = A[i] — B[i]. The key insight is that setting A[i] = max(A[i], (A[i-1] + A[i+1]) / 2 + K) is equivalent to setting C[i] = max(C[i], (C[i-1] + C[i+1]) / 2). Then, we can use convex hull to compute the final values of C[i]: it's fairly well-known that the final value of C[i] will be the y-value at x = i on the convex hull of the points (i, C[i]). Afterwards, we can add B[i] to C[i] in order to find the final values of A[i], and we print the largest one.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

    Do what Geothermal said, but also note that you have to output floats in decimal notation rather than exponential which is the default for cout. (Even though they make us suffer through reading in exponential notation...)

    Edit: Based on what geothermal said, the problem may have just been cout not printing enough digits for doubles. Guess I can't blame the problem writers for that one (:

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

      Weird; I didn't have this issue--after using setprecision(), outputting log doubles worked nicely on my end.

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

        Ah, I've never used setprecision(), and just used printf("%lf") to get it to work. Is setprecision part of your template/does it ever help with avoiding WA on numerical questions?

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

          I use cout rather than printf. I don't have setprecision in my template, but it's essentially mandatory whenever outputting doubles, as otherwise, cout prints far too few digits.

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

Anyone know if there's gonna be an official editorial?