Power Sockets
Contest: Educational Codeforces Round 101 (Rated for Div. 2)
Difficulty rating: 2600
Tags: binary search, data structures, greedy

// We decided to drop the legend about the power sockets but feel free to come up with your own :^)

Define a chain:

- a chain of length $$$1$$$ is a single vertex;
- a chain of length $$$x$$$ is a chain of length $$$x-1$$$ with a new vertex connected to the end of it with a single edge.

You are given $$$n$$$ chains of lengths $$$l_1, l_2, \dots, l_n$$$. You plan to build a tree using some of them.

- Each vertex of the tree is either white or black.
- The tree initially only has a white root vertex.
- All chains initially consist only of white vertices.
- You can take one of the chains and connect any of its vertices to any white vertex of the tree with an edge. The chain becomes part of the tree. Both endpoints of this edge become black.
- Each chain can be used no more than once.
- Some chains can be left unused.

The distance between two vertices of the tree is the number of edges on the shortest path between them.

If there is at least $$$k$$$ white vertices in the resulting tree, then the value of the tree is the distance between the root and the $$$k$$$-th closest white vertex.

What's the minimum value of the tree you can obtain? If there is no way to build a tree with at least $$$k$$$ white vertices, then print -1.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$2 \le k \le 10^9$$$) — the number of chains and the minimum number of white vertices a tree should have to have a value.

The second line contains $$$n$$$ integers $$$l_1, l_2, \dots, l_n$$$ ($$$3 \le l_i \le 2 \cdot 10^5$$$) — the lengths of the chains.

Output format:
Print a single integer. If there is no way to build a tree with at least $$$k$$$ white vertices, then print -1. Otherwise, print the minimum value the tree can have.

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

Note:
You are allowed to not use all the chains, so it's optimal to only use chain of length $$$4$$$ in the second example.

Example input:
1 2
3

Example output:
2

Example input:
3 3
4 3 3

Example output:
3

Editorial:
At first, let's realize that the tree structure doesn't matter that much. What we actually need is the array $$$cnt_i$$$ such that it stores the number of white vertices on depth $$$i$$$.
Initially, $$$cnt_0=1$$$ and all other are zero. If you take a chain and attach it to some vertex on depth $$$d$$$, then the number of vertices on depth $$$d$$$ decreases by $$$1$$$. Also, the added vertices update some other counts.
So far, it's extremely unclear what to begin with. Let's start by introducing some greedy ideas.
For each $$$t$$$ let's find the most optimal tree using exactly $$$t$$$ chains and update the answer with each of them.
First, it's always optimal to attach a chain with its middle vertex. Just consider the changes in the white vertices counts.
Second, for each $$$t$$$ it's always optimal to take the longest $$$t$$$ chains to use. If not the longest $$$t$$$ are used, then you can replace any of them and there will be more white vertices.
It would be nice if we were able to just add another chain to the tree for $$$t-1$$$ to get the tree for $$$t$$$. However, that's not always the case. But we can still attempt it and show that the optimal answer was achieved somewhere in the process.
Let's show that it's always optimal to attach a new chain to the closest white vertex.
So there are basically two cases: there is not enough white vertices yet and there is enough. What happens if there is not enough vertices, and we pick the closest one to attach a chain to? If there are still not enough vertices, then we'll just continue. Otherwise, we'll have to show that the answer can't get any smaller by rearranging something.
Consider what the answer actually is. Build a prefix sum array over $$$cnt$$$, then the answer is the shortest prefix such that its prefix sum is greater or equal to $$$k$$$.
So we put the $$$t$$$-th chain to the closest white vertex at depth $$$d$$$. It decreases $$$cnt_d$$$ by $$$1$$$ and increases $$$cnt_{d+2}$$$ and further by $$$1$$$ or $$$2$$$. Every chain we have put to this point was attached to a vertex at depth less or equal to the answer (otherwise, we could've rearranged it and obtain the answer before). The optimal answer can be neither $$$d$$$, nor $$$d+1$$$ (also because we could've rearranged). Thus, the answer is at least $$$d+2$$$ and every single chain we have put was packed as tightly as possible below that depth.
The second case works similarly. We could've obtained the optimal answer before $$$t$$$. So the answer is below $$$d+2$$$ and we can do nothing about that. Or the optimal answer is ahead of us, so putting the chain at $$$d$$$ can decrease it as much or stronger as any other choice.
Thus, updating the answer on every iteration will give us the optimal result.
Now we are done with the greedy, time to implement it. I chose the most straightforward way. We basically have to maintain a data structure that can add on range, get the value of a cell and find the shortest prefix with sum at least $$$k$$$. That can be easily done with segtree.
Overall complexity: $$$O(n \log n)$$$.