Problem Author: | Anton Tryhub |
Prepared by: | Oleksandr Groskopf |
Analysis written by: | Pavlo Tsikalyshyn |
10pt
Block 1
If there is at least one boy of a certain type in the set, then all other boys of the same type must also be present. Therefore, we can iterate through all subsets of boy types, check if they satisfy the problem's condition, and choose the best option.
Block 2
Consider the problem as a graph, where the vertices correspond to girls, and the boys are the edges connecting these vertices. We need all edges in the set to have at least one common vertex. Such structures can only be of two types:
Star — all edges emanate from one vertex.
Triangle — three vertices, each connected to the other two.
To find the answer for a star, it is enough to determine its center and count the sum of all edges emanating from this vertex.
For a triangle, we need to iterate through all edges and find the vertex that, together with them, forms a triangle.
Block 3
Since each vertex can have no more than two outgoing edges, we can iterate through all vertices that have exactly two neighbors and check if these neighbors are also connected to each other. If so, a triangle has been found.
Block 4
In this group, it is sufficient to iterate through all pairs of neighbors for each vertex . Then we check if there is an edge between vertices and . This works with a complexity of \mathcal{O}(n^2) since each vertex can have up to neighbors.
Block 5
To quickly find all triangles, we can divide the vertices into heavy (with more than \sqrt{n} neighbors) and light (with fewer neighbors).
First, we count all triangles that contain at least one light edge. This can be done in the same way as in the previous approach, and it will take \mathcal{O}(n\sqrt{n}) time. Then we find triangles consisting only of heavy vertices. To do this, we remove all light vertices and repeat the counting. This also executes in \mathcal{O}(n\sqrt{n}).
The overall complexity of the algorithm is \mathcal{O}(n\sqrt{n}).
Block 6-7
To find the best triangle, for each vertex , we need to consider the triangle formed by the two largest edges emanating from (if such exist). There are such triangles, so we will obtain a solution in O(n \log n) or depending on the method of finding the third edge of such triangles.
We will prove that if the optimal answer is a triangle, we will consider it. Indeed, let the optimal answer be a triangle with sides having weights l_1, l_2, l_3, l_1 \leqslant l_2 \leqslant l_3. Let there be another edge r > b emanating from the vertex located between edges l_2 and l_2 (denote it as ). Then the star centered at will be a better answer than our triangle:
[ star l_2 + l_3 + r > l_2 + l_3 + l_1 = triangle ].