it was good decision .

*wweak

Looks like a fellow PST member! I sleep early on weekends so I can do codeforces contests at 6:35 AM during the winter. I'm honestly happy about this 10PM contest, I think its a better time than 6:35 AM.

I don't really understand the "There's no way you're complaining". I definitely do not complain about the general situation, where median CF round is at 15:35 for me. I will definitely not be participating in any round starting at 7AM, so that timing is bad for me and my initial post didn't mean to say anything else than "I am not a functioning person at 7AM" in a humorous way. In particular I didn't mean to say that the decision is objectively bad cause I am aware people in other timezones exist, neither did I want to complain like "why are all cfs round so badly timed?", cause I am aware I am in a favorable timezone for the vast majority of contests. Sorry if I came off as entitled or something

I once woke up at 2am to do a contest: https://codeforces.net/contest/2024

YES ⁦^⁠_⁠^⁩

That would make things somewhat weird. Imagine someone seeing a master in tomorrow's official Div2 standings in the near future!

thank you

Good, I can take a power nap.

How dare you to say such words about the round which was prepared with the help of the mighty tourist!

Div1 CF rounds have been 2 hours long historically and still sometimes are. Speedforces isn't a time problem but a balanced difficulty distribution problem.

Carrot

OK, thanks. I was confused because I didn't know that the contest would be marked as unrated until the ratings have been calculated.

Yeah I too solved using DP in O(n). Is there any solution for greedy + sorting as mentioned in the tags??

Instead of ternary search the series itself, binary search its difference (since that is monotonic) — you'd need the first element that the difference changes sign (equal to the position of the extrema).

UPD: I think I made another fatal mistake... the difference is not monotonic.

Finally I found the correct idea, and it's not relevant to the OG ternary search.

Instead of searching for the $$$y$$$ that would yield maxima for each $$$x$$$, we search for the actual answer instead. We see that to reach a specific answer, there will only be a range of $$$y$$$ supports that for the half "behind" (having x-coordinate lower than current $$$x$$$), and another range of $$$y$$$ supports that for the half "infront". If those two ranges intersect, then such answer is possible.

Added with pooty's comment (though I didn't do the exact bruteforce they intended), the number of searches could be lowered enough to fit into TL.

My submission (very sketchy): 294633915

I meant something like $$$1 \, 1 \, 3 \, 2 \, 2$$$. Your case is binary-searchable.

Thanks, I thought the question need some complex data structure or something like that and got completely stuck. Seems so easy now, thanks!

Any good source to learn sweep line?

Does this pass comfortably within the TL? I believe the second binary search along with the data structure queries would make the overall complexity $$$n\log^3{n}$$$ right? If we use a segment tree with the walk on segment tree technique then it can be reduced to $$$n\log^2{n}$$$, which is what I tried to do, but got TLE on my first submission 294679397.

After this, I tried removing #define int long long, then it passed but the runtime was 2999ms, which is very very close to the TL (294679509). I then tried the same thing in C++23 instead of C++17, that passed in 2499ms.

This is probably because of segment tree having a high constant factor, but using segment tree also reduces the complexity from $$$n\log^3{n}$$$ to $$$n\log^2{n}$$$, whereas in a fenwick tree there isn't this concept of 'walking on segment tree' right (I might be wrong here but I haven't come across such a thing in fenwick trees)? So I'm guessing with fenwick tree this approach will be $$$n\log^3{n}$$$ but with a lower constant factor, which is comparable to what I have submitted.

I'm aware that there is another approach where we can do something like two pointers instead of the second binary search to find $$$y$$$ which would further eliminate a $$$\log$$$ factor, but without that, what would be the best way to go about the binary search approach?

I created 3 nodes {s,in,out} for each SCC, which I explain below. Sorry it may not be very clear, but the general idea is to maximize the number of nodes "covered" by a path, which is done by having a cost of -1000 per covered vertex, and as a secondary objective, minimize the total number of paths that start with an original copy (by having a cost of 1 per path).

So for example if at the end we find that the cost is -4997, it means we needed 3 original copies to reach 5 nodes (-1000 * 5 + 3).

The edges for a SCC compressed into a node $$$U$$$:

• $$$src \rightarrow U_s$$$ with capacity equal to the number of messengers in that SCC, and cost = 0. This node $$$s$$$ acts as a splitter to ensure we don't exceed the total number of messengers across the outgoing edges below.

• $$$U_s \rightarrow U_{in}$$$ with capacity=cost=1. This is to minimize the number of paths that actually start at the vertex with an original copy of the plan (the required answer). We need at most one copy per SCC.

• $$$U_s \rightarrow U_{out}$$$ with capacity = $$$\infty$$$ and cost = 0, this represents a path that starts at the vertex without an original copy, so we must've gotten the copy through some other path.
• $$$U_{in} \rightarrow U_{out}$$$ with capacity 1 and cost of -1000. This will ensure we cover each vertex by exactly one path, given the small negative cost.
• $$$U_{in} \rightarrow U_{out}$$$ with capacity = $$$\infty$$$ and cost = 0. This is to say any path can pass through this vertex if it needs to, but note that this is not "covering" the vertex. The previous edge with -1000 would be prioritized first, which would cover the vertex.
• $$$U_{out} \rightarrow sink$$$ with capacity = $$$\infty$$$ and cost = 0. This indicates that we can end a path at any point.

Finally the DAG edges between compressed SCC nodes ($$$U$$$, $$$V$$$) would be added between $$$U_{out} \rightarrow V_{in}$$$. You can check the addEdge calls in 294690574.

Makes sense, and its an easy fix to make the minimal correct everytime, thank you so much for the help, much appreciated