[reference to question] (Problem - C - Codeforces)
what this question is all about ?
This is very nice D2C.
You just have to find the closest element from left and right greater than itself for all elements and connect them with an edge.
Solution
I hope you know the basic properties of graph.
Any 2 of the three statements “The graph is connected”, “The graph has n-1 edges”, “the graph doesn’t have cycles” implies the third.
Now notice that the graph is connected.
Proof : Let’s look at the elements in decreasing order of value. n cannot create an edge to anything, because there is no element greater than n. Let’s look at n-1.
Since n must be somewhere, n-1 will form an edge to n.
Let’s look at n-i. There must be some element greater then n-i if i>0, so it will form an edge to at least one element greater than itself. So the graph will just add all nodes n to 1, one by one, implying the graph is connected.
If there are n connected nodes, for there to not be a cycle, it implies that we have n-1 edges. Since all nodes from 1...n-1 will form at least one edge, We can deduce that all must form exactly one edge so that the total number of edges is n-1.
So all elements on at least one side must be lesser than itself for every element. Therefore we can deduce there cannot be three elements a\ b\ c such that a > b < c. Therefore the permutation must be a mountain, as in increasing and then decreasing for it to be acyclic. The top element must be n.
We can show that there are 2^{n-1} mountain permutations.
Let us choose some subset of 1 ... n-1. We can arrange the subset in increasing order to the left of the peak, and arrange the unchosen elements in decreasing order to the right of the peak. So the number of mountains is the number of ways to choose a subset from n-1 elements. Since each element can either be chosen or not chosen, there are 2^{n-1} such subsets.
3 Likes