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

By Shayan

Before stream
27:06:00

# | User | Rating |
---|---|---|

1 | tourist | 3845 |

2 | jiangly | 3707 |

3 | Benq | 3630 |

4 | orzdevinwang | 3573 |

5 | Geothermal | 3569 |

5 | cnnfls_csy | 3569 |

7 | jqdai0815 | 3532 |

8 | ecnerwala | 3501 |

9 | gyh20 | 3447 |

10 | Rebelz | 3409 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 171 |

2 | adamant | 163 |

3 | awoo | 162 |

4 | nor | 153 |

5 | maroonrk | 152 |

6 | -is-this-fft- | 151 |

6 | TheScrasse | 151 |

8 | Petr | 145 |

9 | pajenegod | 144 |

10 | orz | 143 |

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/21/2024 16:54:00 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

+

Is there a mirror?

Yes, I believe this is the mirror.

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

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.

Explaination very clear and simple!

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.

This problem relies on a very similar idea.

An explanation (for the problem Balance from USACO December 2018) can be found here.

Edit: Beat :(

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

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

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?

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.

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

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.

Where will the slides be posted?

Slides, test data, and other information have been posted at https://www.icpc.org/icpc-north-america-qualifier

Thanks!