### vkgainz's blog

By vkgainz, history, 3 years ago,

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

• +31

 » 3 years ago, # |   +3 +
 » 3 years ago, # |   +8 Is there a mirror?
•  » » 3 years ago, # ^ |   +6 Yes, I believe this is the mirror.
 » 3 years ago, # |   0 How to solve G (Sky's the Limit)?
•  » » 3 years ago, # ^ |   +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 years ago, # ^ |   0 Explaination very clear and simple!
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 3 years ago, # ^ |   +11 This problem relies on a very similar idea.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 An explanation (for the problem Balance from USACO December 2018) can be found here.Edit: Beat :(
•  » » 3 years ago, # ^ | ← 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 years ago, # ^ |   0 Weird; I didn't have this issue--after using setprecision(), outputting log doubles worked nicely on my end.
•  » » » » 3 years ago, # ^ |   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 years ago, # ^ |   +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 years ago, # |   +5 Anyone know if there's gonna be an official editorial?
•  » » 3 years ago, # ^ |   0 Yes, there will be overview slides for each of the new problems (B,E,G,H). We're a bit behind putting the slides together but expect we'll release them in the next day or so.
•  » » » 3 years ago, # ^ |   +9 Where will the slides be posted?
•  » » » » 3 years ago, # ^ |   +5 Slides, test data, and other information have been posted at https://www.icpc.org/icpc-north-america-qualifier
•  » » » » » 3 years ago, # ^ |   0 Thanks!