Tutorial is loading...
author: Hori
Code: 288397475
Tutorial is loading...
author: willy108
Code: 288397529
Tutorial is loading...
author: Hori
Code: 288397556
Tutorial is loading...
Code: 288397595
Tutorial is loading...
author: lunchbox
Code: 288397611
Tutorial is loading...
author: turtletortles
Code: 288397640
Tutorial is loading...
author: sum
Code: 288397661
Tutorial is loading...
author: Benq
Code: 288397685
Tutorial is loading...
author: Hori
Code: 288397713
Okay so D is done by ChatGPT but also oursaco. oursaco, if you don't mind, can you please tell a little bit about how you contributed to the creation of that problem? Like did you just write the prompt or did the chatGPT stuff have to be revised?
Code is not accessible.
Fixed, thanks for letting me know
cant see tutorial of D, but is it possible to solve D using knapsack?
I didn't solve it, but I think D is to be solved using the observation: if $$$a_i=2^{p_i} \cdot {q_i}$$$, there should be $$$p_i$$$ operations that greedily decrease $$$A_i$$$ and greedily increase the member of the prefix with greater or equal index and max $$$q$$$.
With this, we can compute the optimal sum for each prefix separately in quadratic time. Or, we can compute for each prefix using the the previous prefix in linear time (somewhat like DP).
Essentially, we can process the $$$i^{\text{it}}$$$ prefix as adding $$$A_i$$$ to an array $$$p$$$. By adding $$$A_i$$$, we offer a new $$$q$$$ to all of the elements that precede it. We obviously want all of $$$A_1, \cdots, A_{i-1}$$$ that are using their operations to increase an element with a lesser $$$q$$$ to instead increase $$$A_i$$$. All of the elements that precede the nearest element with a greater $$$q$$$ will not change, but those that follow will now use their operations to increase $$$A_i$$$. We can find the nearest greater element with a greater $$$q$$$ using monotonic stacks, which are well explained by the USACO Guide or CPH. With prefix sums, we can find the the factor by which $$$A_i$$$ increases, and monotonic stacks have a linear time complexity, so the solution is done in $$$O(n)$$$.
I don't see the intuition for Knapsack DP as the problem isn't looking for a subset, but maybe you're on to something.
C is the hardest div2C in history. Even harder than D2 from the last div2 round (rated 2187 on CList).
what is CList?
https://clist.by/problems/
i found it easy
Yo, i've just completed tutorial for problem D in hackmd : link
Sorry for not directly publishing tutorial in codeforces, i prefer using hackmd :)