Can someone please explain it again, thanks.

Can you please explain the ternary search idea ? At first glance on this problem I thought a ternary search idea but while implementing it, I found some difficulties. Then I solved it using binary search. Thanks in advance.

Q·log_1.5Q solution with long long got accepted in 951 ms

hmm, you should imagine that like in real life, except it only has n hours ( not 24 hours) and doesn't have 0 hours. Here is an example how that goes in time zone 1 if we have n=4: TZ1: 1 2 3 4 | 1 2 3 4 | 1 2.. and so on. Meanwhile, in TZ2: 2 3 4 | 1 2 3 4 | 1.. and so on . Hope you can understand, my English and explanations is not good at all =))) .

I'm not sure what the editorial is saying either, but let me explain my solution.

Let the two sides of the cutlet be A and B. Consider the case where we have two availability intervals [l_i, r_i] and [l_j, r_j] with i < j. Let's say we enter interval i with side A, flip to B during interval i, stay at side B until interval j, and flip to A during interval j. If we only consider these two flips, then the amount of time we had side B would be in the interval [l_j - r_i, r_j - l_i]. If we have two more intervals x,y where i < j < x < y, we can perform the same flip as above between i and j with x and y as well (ie. A -> flip at x -> B -> flip at y -> A). In fact there are no conflicts regardless of how we flip things at i, j, x, and y as long as they are of the form I described earlier.

Let's build a graph as follows. Each interval becomes a vertex. Let i < j, we connect interval i to j with a directed edge of length 1 and value [l_j - r_i, r_j - l_i]. Connect the source to all intervals with value [l_i, r_i], and connect all intervals to the sink with value [2n - r_i, 2n - l_i]. These edges represent the time the cutlet spends at side B. We also have to add the side A edges, which are just duplicates of these with value [0,0]. Value here means the time the cutlet spends on side B.

Now, taking an edge from i to j means we do the flips A -> flip at i -> B -> flip at j -> A. This gives some time in the value of the edge. The value of a path whose edges have values [l₁, r₁], [l₂, r₂], ... is simply [l₁ + l₂ + ..., r₁ + r₂ + ...].

IF we add the restriction that we can only have The solution to the problem is now finding the shortest path from the source to the sink whose value contains n, taking alternating side A and side B edges (ie. we can have the cutlet on side B for time n).

To deal with the case where we might have to flip multiple times in one interval, first we note that we want to flip at most twice in a given interval. So we add side B edges from i to i with value [0, r_i - l_i]. This doesn't cause a problem because we must take alternating side A and B edges. However, this only considers cases where we do A -> flip at i -> B -> flip at i -> A, but this is sufficient because the B -> flip at i -> A -> flip at i -> B case cancels out with this one.

To find the shortest alternating path, you can use Dijkstra with an extra flag that says whether to take a side A edge or a side B edge. Also store the value for each visit. Whenever we reach the sink, check to see if the value contains n, if it does, then we found the answer, otherwise, skip this path and keep looking.

Applying spells only on first string is equivalent to applying spells on either strings since spells are bidirectional in this case.

We need to check whether a love triangle exists or not. To do so, it is sufficient to check for all i that whether the i^th plane is a part of a love triangle or not. Let us say that the i^th plane is A, f[A]=B and f[B]=C. if A is part of love triangle, then f[C] should be equal to A. Also f[C] = f[f[B]] = f[f[f[A]]] which should be equal to A, thus it is sufficient to check for all i that whether f[f[f[i]]]==i or not.