Pinely Round 1 (Div. 1 + Div. 2) Editorial

If , we can always find such pair, here is a possible construction:

The red part is their longest common prefix, and the blue part is their longest common suffix.

Otherwise, the two permutations must be equal, so such pair exists iff .

Do we need more than types of elements? Try to solve the problem with .

Solution

First of all, when there're only types of elements appearing in the sequence, the answer would be .

Otherwise, the conclusion is that we can always reach operations when there are more than types of elements appearing in the sequence.

The proof is given below: When the length of the sequence is greater than , there will always be a pair of positions , such that and has two different neighboring elements. Then we can erase and then the problem is decomposed into a smaller one. If there do not exist such pairs, then we can infer that there exists at least element which appeared only once in the sequence. If there exists such element , then we can continuously erase all the elements next to , then erase at last. When the length of the sequence is less than , it is clear that there will be exactly operations as well.

So we only need to check the number of elements that appeared in the sequence of length . If the number is , the answer will be . Otherwise, the answer equals .

Hint 1: When you are trying to add an element into a set , you will have to add the element to every set that is meant to include .

Hint 2: If does not include , then and are already distinct.

If does include , What is the easiest way of making and distinct?

Solution: Denote an ancestor to as a set that is meant to include .

Denote a descendant to as a set that is meant to be included by .

Let all sets be empty from the beginning.

Iterate through the sets. To make set distinct from its descendants, we can add a new number that hasn't been added to any previous sets to and all of its ancestors.

After the execution above, we will find out that the conditions are all satisfied, since:

- For all descendants of a set , all the elements they have will be included in ;

- Vice versa for all ancestors of a set ;

- For each set that is not an ancestor nor a descendant to , they will not include each other. This is because does not include , since does not have the element ; and does not include for the same reason.

Therefore, the construction above satisfies all given conditions.

Moreover, we can set to the index of for a simpler implementation.

Hint 1: Try to solve the problem in using DP.

Hint 2: There is no need for DP.

Hint 3: You can consider enumerating the bits to carry, and then counting.

Let represents the -th bit of in binary representation (that is, ) and define similarly.

If you decide which bits to carry ahead, you will find that every bit of is independent (because whether the previous bit carries or not is decided), so you can use the multiplication principle to count.

Therefore, in the remaining tutorial, we should determine the carries first and then count the number of options of meeting the constraints of carries.

Define array as our decided carry plan, indicates that the -th bit is carried, and define as .

Notice that .

Ponder each bit, we will notice that if

• , can be .
• , can be .
• and , must be .
• and , must be .

That means that pair has options if , and pair has options if .

So if array has positions that ( , remember we define as ), the count of pair is .

Now we can enumerate , and count the number of has positions that .

The new problem equals a typical binomial problem.

Notice that for every , a valid should have segment of consecutive s and segment of consecutive s if we seen as a normal bit (so that we have zeros).

The number of solutions that divide elements into segments is .

Therefore the answer of each is , and we can calculate it in .

Add them all and you can find the answer in .

Hint 1

Try to figure out the conditions where a task can be solved with operation. Then operations, and then even more operations.

Hint 2

The answer could be larger than only when the graph is made up of cliques, where you could only perform the operations on every vertex in the smaller clique to get the minimum number of operations.

Solution

First of all, we need to check if the graph is already connected at the beginning. If so, the answer would be .

Otherwise, there will be more than connected component. If there exists a vertex that is the only vertex required to be operated to make the graph connected, we call such a vertex "feasible vertex". We may find out that a feasible vertex can only appear in a connected component that is not a clique.

But actually, there will always be such a vertex in a non-clique component. To prove this, we may figure out the sufficient condition for being a feasible vertex first.

The sufficient condition is that, if a vertex is not a cut vertex, and it is not adjacent to all other vertices in the connected component, then it must be a feasible vertex. We can prove that such a vertex always exists in a non-clique component. Here is the proof:

- Firstly, if there exist vertices that are adjacent to all other vertices in the component, we erase all of them.

Apparently, the remaining component would still be a non-clique component. Otherwise, the component could only be a clique from the beginning, which contradicts the premise.

- Then, we will find a non-cut vertex in the remaining component, since that vertices in a graph couldn't be all cut vertices. The non-cut vertex we found is the vertex we are searching for.

But implementing it directly (meaning using Tarjan's algorithm to find a non-cut vertex) might not be the easiest way to solve the problem. Actually, the vertex with the least degree in a connected component always satisfy the condition. We would like to leave the proof work of the alternative method to you.

Now we have proven that, if there exists a connected component that is not a clique, then the answer would be at most . What if all connected components are cliques?

If there are exactly connected components, then apparently we will have to operate on all vertices in a connected component. So we'll choose the smaller connected component to operate, and the answer is exactly the size of it.

Otherwise, we can arbitrarily choose two vertices from two different connected components and operate on them. The answer is .

Note that we also need to deal with isolated vertices (meaning vertices that are not adjacent to any other vertices) separately.

Let's analyze the structure of anti-median permutations.

First, if for any holds , or , then segment is bad. So, the signs between adjacent elements are alternating. So, consider two cases: all elements on even positions are local maximums, and on odd local minimums, and vice versa.

Let's find the answer for the first case (for the second, you can find the answer similarly). Consider a segment of length , . Consider the case when is even first. Then . For to not be median, it has to be larger than one of . So, when we consider only even elements, each element (except the first and last one) has at least one adjacent element smaller than it. It's easy to see that this implies that elements at even positions are first increasing and then decreasing.

Similarly, we can see that elements at odd positions are first decreasing, then increasing. It's not hard to see that these conditions are sufficient. Indeed, suppose that:

• All elements on even positions are local maximums, and all elements on odd positions are local minimums
• Elements at even positions are first increasing and then decreasing.
• Elements at odd positions are first decreasing, then increasing.

Then, consider any segment of odd length. Denote it by , and wlog is local maximum. If we look at local maximums, at least one of the following two conditions has to hold: all local maximums to the right of are smaller than it, or all local maximums to the left of are smaller than it. Wlog first case. Then all elements to the right of are smaller than it, and is also smaller than it, so can't be a median.

Now, let's put all elements on the circle in the following order: first, all even elements from left to right, then all odd elements from right to left.

In this circle, the elements on both paths between and are decreasing. It follows that for any , numbers from to form a segment (in this cyclic arrangement).

Then, we can write a of the form: : how many ways are there to arrange the largest elements so that they end up in the positions from -th to -th in this cyclic arrangement. All the transitions and checks are done in , and there are states, so we are done.

For this version, we have to analyze our dp a bit more.

Once again, how do anti-median permutations look? We consider the order of positions on the cycle, as in F1. We choose the position of , and then, for from to , we choose a position of number among two options: right to the right of the current segment or right to the left.

If we fill this way, do we always get an anti-median permutation? Not really. This way makes sure that elements at even positions are first increasing, then decreasing, and at odd positions, first decreasing, then increasing, but it doesn't make sure that the element at the even position is larger than its neighbors. How do we guarantee that? Well, some segments are just not allowed: those, which contain a prefix of odd positions, prefix of even positions, and the prefix of odd positions is larger (off by , depending on the parity of ), and same for suffixes.

Another observation is that if we know where is, we only have to options for where can the segment of numbers from to be (to the right or to the left of ).

This reduces our problem to the following subproblem: we start from some segment and have to end in another segment by expanding the current segment by to the right or to the left without ever entering "bad segments." Turns out that we can solve this in ! Indeed, represent expanding segment to the right by a move up in a coordinate plane and to the left by a move to the right. Then, we have to get from point to some point by moving up or to the right without ever crossing some line of form . This is a well-known counting problem.

Assuming we have already determined that the centroid of the tree is located on the path between and , we may now consider how to locate it.

Let be the vertices on the path from to . Let be the set of vertices reachable from (including ) if we erase all other vertices on the path from to . Then we may find that are a division of all vertices.

Let be the size of . Then there must exist a vertex on the path satisfying that . Notice that the vertices that do not satisfy the condition could not be a centroid, and it is already determined that the centroid is on the path, so is exactly the centroid of the tree.

Then we may consider finding out which set each vertex belongs to with queries so that we can calculate the value of . For each vertex , we may query and . For any two vertices and that belong to the same set, should be equal to . Let and , then . Thus we have found out the sets each vertex belongs to, as well as the value of , as well as the centroid. This process requires at most queries.

Now the problem remains to find a pair of vertices and such that the centroid locates on the path from to .

We can pick a constant satisfying that , then select vertices on the tree randomly, and query the distances between every pair of selected vertices. This requires queries.

Let these vertices be . We can build a virtual tree with being the root that contains all the LCAs of each pair of vertices. Observe that if and only if is located on the path between and . For a vertex , we can find out all vertices on the path from to , and then find out the closest vertex to and connect them. It is exactly the deepest ancestor of .

Now that we have constructed the virtual tree without the LCAs with being the root, we will then add the LCAs into the virtual tree.

Start DFS from . Assume the current vertex is . Enumerate through the nodes adjacent to . Assume the current vertex is . If there exists another vertex which is adjacent to satisfying that is not on the path between and , then and should be both in the subtree of one of 's child nodes. After finding out all vertices that are in the same subtree as , it would be easy to calculate the depth of their LCAs as well as the distance between an LCA vertex and all other vertices in the virtual tree. Then, remove the old edge, and then add edges between the LCA and all vertices found in the same subtree as . Lastly, add an edge between the LCA and . Then repeat the process above, until any two vertices adjacent to are not in the same subtree of a child node of . Then DFS the child nodes of . We will get the whole virtual tree after all DFS are done.

For the vertices chosen from the beginning, we assume that their weights are all , while other vertices have weight. Then we may find the weighted centroid of the virtual tree (when there are multiple such centroids, arbitrarily pick one), and then make it the root. Then for the two vertices with the largest and second-largest subtree of the root, DFS them, recursively find their child vertex with the largest subtree. We will be resulted with leaf nodes. Then the centroid of the hidden tree is highly possible to be located on the path between these nodes. The number of queries in both parts would not exceed .

Proof of correctness:

If the centroid is not on the path between and , assume the centroid of the virtual tree is in the subtree of the centroid of the hidden tree. If the subtrees other than contain at least of the vertices, then the centroid of the hidden tree must be on the path between and . So there will be at most of the vertices not being in . In other words, for each of vertices, it has a possibility greater than of not being in , and there will be at most of the vertices which are not in . The possibility of the algorithm being wrong is not greater than , let , then the value would be approximately .