← All solutions

Shortest judge solution: 709 bytes. Shortest team solution (during contest): 851 bytes.

This is one of the easier problems in this problem set. After reading through the statement, we can see the problem is about constructing a tree where as many vertices as possibe have a given degree (note that the only information we care about from the input are the degrees of vertices in the input graph, and not the exact shape of the input graph).

The choice of which vertices preserve their degree can be made greedily. Since we have to construct a tree, the sum of degrees of all the vertices will be 2n − 2, and each vertex will have degree at least 1. Thus, we are left with n − 2 spare degree increases to assign. In order to satisfy as many vertices as possible, we should assign these increments to the vertices with the smallest expected degree first. In this way we arrive with a degree assignment that satisfies as many degrees as possible.

The second part of the problem is to construct a tree with given degree values. This can be done in a number of ways. One such way is to order the vertices by degree, and add them to the tree in order of decreasing degree, starting with the highest degree vertex as the root, and maintaining a list of “outstanding degrees” – that is vertices with a larger expected degree than the number of edges already connected. When adding a new vertex to the tree, we connect it to any of the vertices with positive outstanding degree (and decrease the outstanding degree of both vertices by one). Note that until the very end, there will always be a vertex with positive outstanding degree in the already constructed tree. This is because a tree with k vertices has outstanding degree zero if the sum of expected degrees in the tree is 2k − 2, and so the average expected degree is (2k − 2)/k. However, the average expected degree among all vertices is (2n − 2)/n, which is larger than (2k − 2)/k since k < n, and the average expected degree in any partially constructed tree is at least equal to the average expected degree among all vertices, because we take the vertices from the largest expected degree.