Check each number of liars independently.

How to check, whether there are exactly $$$x$$$ liars?

How to solve for $$$n = 2$$$?

How to solve for $$$n = 4$$$?

What is the number of options that is present in the infinite amount of rounds?

Choose the smallest such number of options.

How does this number and $$$m$$$ relate to the answer?

What can we say about the position of the maximum elements relative to $$$[l, r]$$$?

You can use DP, or otherwise:
Iterate over the middle maximum element and choose $$$[l, r]$$$ greedily.

What is the relation between two models that go one after another in a show?

If you calculate the relation "model $$$i$$$ can go before model $$$j$$$" somehow, how to calculate the answer?

How to calculate this relation fast enough?

What happens in the general case after 2 queries?

Can we solve the question in 3 queries?

How to choose the third query, so that we don't intersect any bad candidates?

I've compiled 10000 best participations in a Div. 2 contest into a CSV file
It's funny, that I myself am mentioned 4 times and all of those are Educational Div. 2 contests
This is the python script I used to fetch this information

My first message from message from MikeMirzayanov was more than a year ago! Also antontrygubO_o has rejected almost 30 (29 to be exact) problems to this point, so you can see I really tried my best to deliver this round. It was a great journey, I hope to come back with a Div. 1 or even a Global round in the future!

What's the lower bound for the amount of blocks for the answer to be $$$\texttt{YES}$$$?

Check the predicate for every prefix.

Let's consider the smallest amount of blocks we need to make the first $$$i$$$ heights ascending. As heights are non-negative and ascending the heights should look like $$$0, 1, 2, 3, ..., i - 1$$$, so the minimum sum is $$$\frac{(i - 1) \cdot i}{2}$$$. It turns out that this is the only requirement. If it's not the case for every prefix the answer is $$$\texttt{NO}$$$ because we can't make some prefix ascending. Otherwise the answer is $$$\texttt{YES}$$$ because you can move the blocks right till there is at least $$$i$$$ blocks in the $$$i$$$-th stack and this would make the heights ascending.

Is problem really two dimensional?

How to solve the problem if $$$y = 0$$$?

At first let's see that the problem is not two dimensional. If we change the $$$x$$$ coordinate the sum of distances by $$$y$$$ is not changed at all. So we just need to calculate the number of good points on a line with points having coordinates $$$x$$$ and then $$$y$$$ and multiply the answers.

Now to calculate the answer on a line we could use a known fact: point with the smallest summary distance is between left and right median. So now we only need to sort the array and find the elements on positions $$$\lfloor\frac{n + 1}{2} \rfloor$$$ and $$$\lfloor \frac{n + 2}{2} \rfloor$$$ and return their difference plus one.

Binary search?

How to check if the maximum element is in the left or the right part of the array in two queries?

Let's solve for some subsegment $$$[l, r)$$$ and $$$mid = (l + r) / 2$$$. Now let's check if the max element is in $$$[l, mid)$$$ or $$$[mid, r)$$$. Let's find the second max element in $$$[l, r)$$$ and call it $$$smax$$$. Now let's think that $$$smax$$$ is less than $$$mid$$$ (for symmetrical reasons). Now if we ask $$$[l, mid)$$$ and second max is still $$$smax$$$ it means that maximum element is in $$$[l, mid)$$$, otherwise it's in $$$[mid, r)$$$. Now we've shrunk the segment by a factor of two. So the resulting number of queries is $$$2 \cdot \lceil log_2 10^5 \rceil = 34$$$.

Binary search AGAIN?

How to solve the problem if the second maximum element is at position $$$1$$$?

How to check if the maximum element is to the left or the right of the second maximum in two queries?

Let's find second max $$$smax$$$. Now let's check if the max element is to the left, or to the right. Just ask $$$[1, smax]$$$ and see if the answer is different to $$$smax$$$. Now let's suppose that the max element is to the right (for symmetrical reasons). Now we only need to find the smallest $$$m$$$ such that the answer to the query $$$[smax, m]$$$ is $$$smax$$$. The smallest such $$$m$$$ is obviously the position of the maximum element. Now we need to use binary search to find such $$$m$$$. So the resulting number of queries is $$$2 + \lceil log_2 10^5 \rceil = 19$$$.

How to solve the problem if all the values are $$$-1$$$ and $$$1$$$?

Binary search ONCE MORE?

How to check if the answer is at least $$$x$$$?

Let's binary search the answer. Now let's check if the answer is at least $$$x$$$. Replace all values that are at least $$$x$$$ with 1 and values that are less than $$$x$$$ with $$$-1$$$. Now if for some segment the median is at least $$$x$$$ if the sum on this subsegment is positive! Now we only need to check if the array consisting of $$$-1$$$ and $$$1$$$ has a subsegment of length at least $$$k$$$ with positive sum. So let's just calculate prefix sums of this array and for prefix sum at position $$$i$$$ choose the minimum prefix sum amongst positions $$$0, 1, ..., i - k$$$, which can be done using prefix minimum in linear time.

So the resulting complexity is $$$O(nlogn)$$$.

Did you read that $$$w$$$ is at most $$$50$$$?

How to change the graph for dijkstra algorithm to work with this rule?

Add some fake vertices and edges to make things work.

Let's think about it this way. For a middle vertex we only care what are the weights of the edges that pass through it. Now for every vertex $$$v$$$ let's create some fake vertices $$$(v, w)$$$, where $$$w$$$ is the weight of the last edge. This would add at most $$$O(M)$$$ new vertices. Now for each starting edge $$$(u, v, w)$$$ let's make an edge $$$u \rightarrow (v, w)$$$ of weight $$$0$$$ and for each vertex $$$(u, was)$$$ and edge $$$(u, v, w)$$$ let's create an edge $$$(u, was) \rightarrow v$$$ with weight $$$(was + w)^2$$$. Now running Dijkstra's algorithm from vertex $$$1$$$ will result for correct answers for all vertices (as we've simulated the paired edge situation with fake vertices and edges). Also we wouldn't create more than $$$O(M \cdot maxW)$$$ edges cause if some vertex has degree $$$t$$$ we would create no more than $$$t \cdot maxW$$$ edges and sum of all $$$t$$$ is $$$2 \cdot M$$$.

Carefully implemented this would result in $$$O(M \cdot maxW \cdot logM)$$$ or $$$O(M \cdot maxW + MlogM)$$$ time and $$$O(M \cdot maxW)$$$ or $$$O(M)$$$ memory. All of those were fine.

Root the tree.

After rooting the tree, how does the intersection of two paths look?

After rooting the tree, what are the two types of intersection?

Let's root the tree at some vertex. Now the intersection vertex is lca for at least one path.

Now there are two types of intersections: with the same lca and different lca. Let's count them independently.

For each path and it's lca let's find the subtrees that path goes to from lca. This would result in a triplet $$$(lca, subtree1, subtree2)$$$ (replace subtree with $$$-1$$$ if there is none) with $$$subtree1 < subtree2$$$ or both of them are $$$-1$$$.

Now to count the intersections of the first type let's use inclusion-exclusion principle. Remember all paths that have same lca. Now we need to calculate the number of pairs so that they have different $$$subtree1$$$ and $$$subtree2$$$ (or $$$-1$$$). The formula is going to be $$$cntpath \cdot (cntpath - 1) / 2 - \sum \left(cnt(subtree1, x) + cnt(x, subtree2) - (cnt(subtree1, subtree2) + 1) \right) / 2$$$ (from inclusion-exclusion principle) where cntpath is the number of paths with this lca and $$$cnt(x, y)$$$ is the number of paths with triplet $$$(lca, x, y)$$$. The situation with $$$-1$$$ is pretty similar, left as an exercise to the reader.

Finding the number of intersections of second type is a bit easier. We just need to calculate the number of all intersections between a path with fixed lca and a vertical path which crosses this lca (the path is not neccessarily vertical, but it contains both lca and it's parent) and then subtract $$$cnt(subtree1)$$$ and $$$cnt(subtree2)$$$, where $$$cnt(x)$$$ is the number of vertical paths that go into subtree $$$x$$$.

After that we just have to print out the sum of this two numbers. Counting all the needed functions can be done using some data structure (small-to-large for example) or some subtree dynamic programming.

The resulting complexity is $$$O(Mlog^2M)$$$ or $$$O(MlogM)$$$ or even $$$O(M)$$$ if you're strong enough.

Today I was peacefully solving a virtual contest Codeforces Round 381 (Div. 1). After solving AB I've had roughly 30 minutes for all other tasks (not much since C difficulty was 2500). But after reading C I've clearly understood that this is a stupid segment tree task and I can definitely solve it, it was all about implementation. After about one and a half hours I had a working solution, which passed all pretests and got stuck on test 4. After running a stress test on 20000 absolutely random tests I've started to suspect something.