Drazil Likes Heap
Contest: Codeforces Round 631 (Div. 1) - Thanks, Denis aramis Shitov!
Difficulty rating: 2400
Tags: constructive algorithms, data structures, greedy, implementation

Drazil likes heap very much. So he created a problem with heap:

There is a max heap with a height $$$h$$$ implemented on the array. The details of this heap are the following:

This heap contains exactly $$$2^h - 1$$$ distinct positive non-zero integers. All integers are distinct. These numbers are stored in the array $$$a$$$ indexed from $$$1$$$ to $$$2^h-1$$$. For any $$$1 < i < 2^h$$$, $$$a[i] < a[\left \lfloor{\frac{i}{2}}\right \rfloor]$$$.

Now we want to reduce the height of this heap such that the height becomes $$$g$$$ with exactly $$$2^g-1$$$ numbers in heap. To reduce the height, we should perform the following action $$$2^h-2^g$$$ times:

Choose an index $$$i$$$, which contains an element and call the following function $$$f$$$ in index $$$i$$$:

Note that we suppose that if $$$a[i]=0$$$, then index $$$i$$$ don't contain an element.

After all operations, the remaining $$$2^g-1$$$ element must be located in indices from $$$1$$$ to $$$2^g-1$$$. Now Drazil wonders what's the minimum possible sum of the remaining $$$2^g-1$$$ elements. Please find this sum and find a sequence of the function calls to achieve this value.

Input format:
The first line of the input contains an integer $$$t$$$ ($$$1 \leq t \leq 70\,000$$$): the number of test cases.

Each test case contain two lines. The first line contains two integers $$$h$$$ and $$$g$$$ ($$$1 \leq g < h \leq 20$$$). The second line contains $$$n = 2^h-1$$$ distinct positive integers $$$a[1], a[2], \ldots, a[n]$$$ ($$$1 \leq a[i] < 2^{20}$$$). For all $$$i$$$ from $$$2$$$ to $$$2^h - 1$$$, $$$a[i] < a[\left \lfloor{\frac{i}{2}}\right \rfloor]$$$.

The total sum of $$$n$$$ is less than $$$2^{20}$$$.

Output format:
For each test case, print two lines.

The first line should contain one integer denoting the minimum sum after reducing the height of heap to $$$g$$$. The second line should contain $$$2^h - 2^g$$$ integers $$$v_1, v_2, \ldots, v_{2^h-2^g}$$$. In $$$i$$$-th operation $$$f(v_i)$$$ should be called.

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

Example input:
2
3 2
7 6 3 5 4 2 1
3 2
7 6 5 4 3 2 1

Example output:
10
3 2 3 1
8
2 1 3 1

Editorial:
The property of heap we concern in this problem mainly are:
1. The tree is a binary tree, each node has a weight value.
2. The weight of a node is always larger than the weight of its children.
3. We use $$$a[I]$$$ to record the weight of vertex $$$i$$$, and the number of its children are $$$2 \times i$$$ and vertex $$$2 \times i + 1$$$ (if exist).
Another key point we should consider seriously is before all operations and after all operations, the tree must be a perfect binary tree. Many contestants didn't notice the constraint during the contest.
I think there are two different thinking directions for this problem. One is considering node from bottom to top. Another one is considering node from top to bottom. For me, from bottom to top is more intuitive.
Now we talk about "from bottom to top" first, it means we consider node from larger index to smaller index in the tree after all operations (call it final tree after). For the leaves in the final tree, it's not hard to know, the minimum possible final weight of each leaf is the minimum weight of nodes in its subtree before all operations (call it beginning tree after). For the other nodes in the final tree, its weight must satisfy two constraints, one is it should be larger than the final weight of his children, another is the weight should exist in its subtree of the beginning tree. Luckily, these lower bounds are all constraints we should consider to get the answer. For each leaf in the final tree, we maintain a data structure that stores all weight of its subtree in the beginning tree. Then the minimum value in this data structure is its final weight. For other nodes in the final tree, we merge the two data structures of its children. the remove all value which is less than the final weight of his children. There are many data structure can do these operations, such as min heap(author's code) or sorted array(isaf27's code).
With the above method, we get the minimum possible sum of the remaining $$$2^g-1$$$ elements. But we still don't know how to construct it. All we know is which weight values are reaming in the final tree. Now I want to prove that no matter how the order I call the function $$$f$$$, if the remaining weight values set is the same, the final shape of the final tree will be the same.
This time I prove it from top to bottom. We only know which weight values set to remain in the final, Then We iterate node from smallest index to the larger one. We always can determine the weight value of the iterated node, because the weight value only can be the maximum value in its subtree. This trait also can let us know that the final tree we get in our method is a perfect binary tree.
Conclude all things above. after we can apply the function $$$f$$$ from bottom to top on these nodes with weight value doesn't exist in the final tree.
In the "from bottom to top" method, it has some thinking level difference between calculating the minimum sum and constructing a list of possible operations. So I determine let competitors output the operations.
- - -
Now we talk about the "from top to bottom" method. The main idea of this method is iterating index from $$$1$$$ to $$$2^g-1$$$ and in each iteration, applying the function $$$f$$$ on $$$i$$$-th node until the shape of the final tree is impossible to become a perfect binary tree. The method is quite easy to write and almost has no difference when asking you to output the operations. But I think it's hard to prove. Evenly, I think the solution should be wrong until I write this solution and test it.
Firstly I want to prove the minimum possible final weight value of node $$$1$$$ is the same as the above "from top to bottom" method get. We call the value as $$$mi_1$$$. If some algorithm $$$B$$$ can get more small weight value in the final tree, It means all weight values which are not smaller than $$$mi_1$$$ disappear. But according to the conclusion "if the remaining weight values set is the same, the final shape of the final tree will be the same.". the final tree generated by $$$B$$$ can also get with firstly applying the function $$$f$$$ on node $$$1$$$ at least one more time than above "from top to bottom" algorithm, and do some other operations. But it will make the final tree is impossible to be the perfect binary tree. Now we disprove it.
Now we want to prove the final weight value of node $$$i$$$($$$i>1$$$) is the same as the above "from top to bottom" method get. Only when applying function $$$f$$$ on ancestors and descendants of node $$$i$$$ will affect the final weight value of node $$$i$$$. And when we apply on its ancestors, the $$$f$$$ may recursively apply $$$f$$$ on $$$it$$$ at most once. So each time $$$f$$$ applies on its ancestors is equivalent to apply on itself once or do nothing. Therefore, The proof can be don as what we do on node $$$1$$$ just by only considering the subtree of node $$$i$$$.
Now, we have proved the "top to bottom" algorithm can make each node of the final tree has the minimum possible weight value.
When I found the "top to bottom" algorithm during preparing the contest, I ever consider changing the problem to something else because the method is too easy to guess and to write. But I have no other more proper problem that can be used. It's a little pity for me.