For problem 3, first consider how to answer one question. Balls at the same position can be merged, then consider the entire process in reverse order, The last ball collected must be one of the balls on left or right side of the end point, and the last $$$k$$$ balls collected must form an interval. Enumerate the last ball collected(at most 2 different balls possible), the observation leads a DP that $$$f_{l,r}$$$ indicates if we collect the balls between $$$l$$$-th to the $$$r$$$-th position at the end of entire process, what is the minimal time to collect them. It answers a question in $$$O(n^2)$$$ time, where $$$n$$$ is the different places that have balls. If we calculate all $$$n$$$ beginning position, we can answer a question in $$$O(\log n)$$$ time.

Another observation is that if we have $$$n$$$ different positions that have balls, the minimal time is at least $$$n^2/2$$$, so we only need to solve the task for $$$n\le 1000$$$, previous $$$O(n^3)$$$ solution works.

it is a shame that your comment gets downvoted, growing up something i loved about contests and olympiads was that editorials and model solution were written with the actual desire to educate people, but unfortunately i see more and more people approving this mindset of not explaining the approach in a written format.

even having explanations in comments would be great, they don't have to be official or anything of sorts, i guess community written comments would be just as good too.

Gonna make one for the problems and subtasks I solved, Not the best but it can help anyway.

Then you can do binary search!

First you need to do 2 dijkstras from $$$T.$$$ and $$$S.$$$ node.

Then, suppose we went $$$u.$$$ node from $$$S.$$$ node with $$$x$$$ time, we need to go $$$v.$$$ node from $$$T.$$$ node with $$$K - (x + L)$$$.

(Because we can construct a road between $$$u$$$ and $$$v$$$.)

For a better understanding of my approach, let's represent each person $$$i$$$ as a segment $$$(B_i, A_i)$$$. So now for every query, we need to find out whether there is a permutation $$$p$$$ of left bounds such that all segments will stay valid $$$(B_{p[i]} < A_i)$$$ and all left bounds will change their position $$$(p[i]!= i)$$$.

The first thing that you have to notice is that you can't rearrange left bounds correctly if there is a segment that doesn't intersect with anyone else. In other words, all positions the segment covers are covered only by that segment. Otherwise, there is a strategy to arrange them. The straight-forward check of that condition takes $$$50$$$ points.

In order to get $$$100$$$ points, we need to precompute the following for every segment:

1. $$$lb_i$$$ is the closest segment that intersects with the $$$ith$$$ segment in the array from the left: $$$(lb_i < i)$$$.

2. $$$rb_i$$$ is the closest segment that intersects with the $$$ith$$$ segment in the array from the right $$$(rb_i > i)$$$.

Both things can be precomputed by a segment tree with an assignment on segment. To be specific, we iterate from left to right, and for every position $$$x$$$, we maintain $$$tr[x]$$$, the $$$max$$$ index of the segment that covers $$$x$$$ ($$$tr[x] < i)$$$. Than, to find $$$lb_i$$$, we just take $$$max$$$ on the interval $$$[B_i, A_i]$$$ in the seg-tree.

Finally, both arrays help us respond to the queries offline. Here we iterate from left to right, and on each iteration we respond to queries with the right bound equal to $$$i$$$. To respond to each query quickly, we have to maintain another array $$$f$$$, where $$$f_j$$$ initially points to $$$lb_j$$$, but when $$$rb_j <= i$$$, $$$f_j$$$ becomes $$$+\infty$$$. This structure helps us to respond to each query in $$$O(logn)$$$ as the task is reduced to $$$min$$$ on segment.

I hope I explained it in enough detail; feel free to ask.

I'm yet to implement it, but probably this will work.

• Note that the problem is about intervals (for each connected component, only its row sets are interesting)
• We denote the "local" intervals as the component given in a query and the "global" intervals as the whole component set. I will only solve one queries for the time being.
• You have to find the subset of points that "stabs" all local intervals (intervals have at least one point from the subset), and they are "connected" by global intervals (sort the subset, for each adjacent one, there exists some global interval that contains both)
• The above constraint is mostly like $$$p_{i + 1} - p_i \le f(p_i)$$$, since the above two constraint limits how further you can get from the current point.
• If you do DP on the position, you can solve in $$$O(N^2)$$$ time, and can optimize this to $$$O(N)$$$ time using monotone queues.
• Let's do DP on the cost instead. For each cost $$$X$$$ compute the rightmost point you can reach with such costs. There is two transitions: Use the rightmost $$$c_i = 1$$$, or the rightmost $$$c_i = 2$$$. Also gives $$$O(N)$$$ time, with simpler DP.
• Now the queries: If the current DP position is within some local interval, you can just do naively as each transition skips at least one local intervals and you can't skip too much as a whole. So the problem is to pass through global intervals quickly, possibly with some precomputation. Use sparse table: $$$nxt[i][j]$$$ denotes the position you can reach with cost $$$(2^j-1, 2^j)$$$. Transition: $$$(k-1) + (k) \rightarrow (2k-1), (k) + (k-1) \rightarrow (2k-1), (k) + (k) \rightarrow (2k), (k-1) + (2) + (k-1) \rightarrow (2k)$$$. Using this sparse table, pass through global intervals, while being careful to not touch any local intervals within the process.

They are on Atcoder

We'll try to upload it when Spring Camp materials are available (I just want to do it simultaneously for efficiency, sorry)

Anyway, you could use https://www.acmicpc.net/category/detail/4176 instead. You can use English UI by clicking "English (Beta)" at the bottom.

You can also download the statements from the website (they are available both in English and Japanese), and submit on AtCoder, if it's the translation that's bugging you.