Eid Mubarak ! Happy Eid-ul-Fitr !!

This picture reminds me of this song.

The guy she told you not to worry about is Tourist.

Let me do this job for you.

Is is Rated (for Div1)?
Ans seems Yes.

MikeMirzayanov awoo Please fix it.
Everyone is registered as "Contestants".
Mark me and others as "out of competition".

we all love pik misha :D

LoOOoOOooOooLoOOOoooOOOoOOLoOoOooOoooooOOL. ROFL. LMAO.
Problems at usual contests: "use a segment tree with some trciky operations and tricky queries"
Problems at educationals: "use a trivial segment tree, (yes) and queries are in the form of $$$[p_i,i]$$$
didn't you feel that difference?"

I'm a wolf! awoo~

true

Best Girl is also Best boy

Baraa_Armoush ur logic hhhhhhh

I wonder why im getting downvotes...am I wrong?

There is always "A worse" in CF...

why?In my opinion this problem is cool.

Expand the summation using prefix sums everywhere

Problem B is just a simple stack based problem of evaluating parenthesized expressions.

And as for signal, check the documentation. signal.alarm is unix only

throw new JokeTooOldException();

D was quite solvable

C is extremely hard to me. lol In my opinion D is easier than C. :)

Create sparse table such that nxt[i][j] is the maximum index sucht that [i, nxt[i][j] ] can be covered using atmost $$$2^j$$$ segments.

Let 1, x2, x3,...,n be index where new subarray starts. Then answer is f(1)×1 + (f(x2)-f(1))×2+....+(f(n)-f(x_k-2))×k. Open it. f(i) is prefix sum till i'th element.

You can extend this proof to general k segments

No you can't 55147246

No. because the f(x) might be something like sin(x) (just for imagination!). suppose there are k + 1 points close to each other, then a huge gap then again k + 1 points close to each other, then a huge gap and so on...

Average of points which have k-1 given integers between them.

My solution lets find minimal distance using binary search. Suppose the answer is X.

Then, our answer point should be in the distance X for at least k points.

Second part is just easy to check if there is a point where k segment intersect [a_i — X, a_i + X].

Complexity O(n * log^2)

But can be easily implemented in O(n * log)

Have you solved it? Well, supose X is outside the range we are right now. Then its better to put it inside the range, to decrease the distances of the k consecutives elements. The ans is the min middle point of all ranges with lenght K. (the best point is the middle one because it gives us the least k minimum differences).

After the Hacking Phase

https://mirror.codeforces.com/blog/entry/67411?#comment-516189

D̶&̶C̶ ̶D̶P̶ ̶o̶p̶t̶i̶m̶i̶z̶a̶t̶i̶o̶n̶ I'm actually not sure(there is no editorial for task, so I wrote what i remembered it was), thx for pointing it out

By the way, the problem is not original, statement is only in romanian though

I have an $$$O(NKlog)$$$ solution for G but still havent been able to implement it until now which ruins my rating as always :)

So we lets denote $$$MAX(L, R)$$$ be the maximum value in the subarray $$$[L, R]$$$, and $$$F(i, j)$$$ as the minimum weight of splitting first $$$i$$$ elements to $$$k$$$ subsegments.

By that, we have $$$F(i, j) = min(F(x, j - 1) + MAX(x, i) * (x - i + 1)))$$$ for every $$$x ≤ i$$$.

Lets have an observation:

We can separate $$$(i - x + 1) * MAX(x, i)$$$ to $$$(i - 1) * MAX(x, i) - x * MAX(x, i)$$$. As always, we will have some data structre like Convex Hull or Lichao Tree to query for the minimum $$$w* MAX(x, i) - x * MAX(x, i) + F(x, j - 1)$$$ for $$$w = i - 1$$$.

Now, normally, one will always think of idea of iterating elements from left to right, maintaining the stack of maximum elements and trying to do something about deleting and pushing elements to that stack. As every time $$$MAX(x, i)$$$ changes, we will need to reset our Convex Hull or Lichao Tree over again.

Lets fix $$$i$$$. Now our stack will represent the changes of the $$$MAX(x, i)$$$ if we iterates $$$x$$$ from $$$i$$$ to the left. And for every fixed $$$k$$$, the elements that satisfy $$$MAX(x, i) = k$$$ lies on a continuous subarray. So my main idea is for each $$$k$$$, i will first find the $$$x$$$ that minimizes $$$-x * k + F(x, j - 1)$$$ before we actually inserting it to our Lichao/Convex Hull.

To do this, you can think of an segment tree which each of its node has a Convex Hull or Lichao tree to take this query. And we will use Convex Hull in this case. If we notice that every time we try to change the $$$MAX$$$ of some subarray by deleting some elements from our stack, their $$$MAX$$$ only gets bigger and bigger. So if we use Convex Hull, we can actually handle queries in $$$O(1)$$$ by using the pointer trick instead of binary searching.

Now once we get the best $$$x$$$ for our $$$k$$$, we will insert a line $$$(k, -x * k + F(x, j - 1))$$$ to our Lichao Tree and take queries later.

But another thing to notice is that if some elements are poped out from our stack, the Lichao tree should also be changed. But luckily, only the top elements are deleted from our stack so its prefix is still the same. Here, we can use a persistent Lichao Tree to handle this case.

So my time complexity is actually $$$O(NKlogC)$$$ for building the segment tree of ConvexHull and $$$O(Nlog)$$$ memory for having a persistent Lichao Tree.

Since this solution is pretty much disgusting, I hope its not author's solution. But i dont want his solution to be $$$O(Nkloglog)$$$ either cause I didn't expect it to pass and spent all my contest thinking of a better (not the one above lol) one.

It can be solved with ordinary segment tree. With time complexity O(NKlogN). Our dp will dp[k][n], where k is number of groups, and n is representing last added to some group. Now let's focus on solving only one dp layer in terms of group. Update segment tree by setting cost of each index to value of dp[prevgroup][that_index]. Now iterate from left to right, suppose that we are at index i now. Each index will have some cost in segment tree. Now our reccurence will be dp[i] = min dp[j] + cost(j,i). This can be easily found if we can calculate efficiently cost(j,i). Instead of calculating it each time, we will somehow update it efficiently. We can do so by grouping elements by maximum element from them to our i. Now one can see that when moving right, we can find where this element represents maximum. And set it as maximum for new group, while deleting previous groups that those elements belong to. Only thing that is left is that maximum is multiplied by length. We can handle this again by segment tree arithmetic progression update (it can be found easily on net, i am lazy to write about it now). I hope i helped.