vkgainz's blog

NAQ 2021
By vkgainz, history, 4 years ago, In English

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

  • Vote: I like it
  • +31
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

+

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

Is there a mirror?

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

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    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.

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

      Explaination very clear and simple!

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks Geothermal for the clear explanation. Where can I learn more about the convergence of C[i] to the convex hull of the points (i, C[i])? I am interested in a formal proof as well as some similar problems to practice.

      → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it -10 Vote: I do not like it

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

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

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

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

        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?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          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.

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

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

→ Reply