Boys and Girls (Çözgüdiň düşündirişi)

10pt

Block 1

If there is already at least one boy of a certain type $x$ in the set, then all other boys of the same type must also be present. Thus, we can iterate all subsets of boy types, check if they satisfy the conditions of the problem, and choose the best option.

Block 2

Consider the problem as a graph, where vertices correspond to girls, and boys are 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:

1. Star — all edges radiate from a single vertex.

2. Triangle — three vertices, each of which is connected to the other two.

To find the answer for a star, we need to determine its center $x$ and calculate the sum of all edges radiating from this vertex.

For a triangle, we need to iterate over all edges $(u,v)$ and find a vertex, together with which they form a triangle.

Block 3

Since each vertex can have no more than two outgoing edges, we can iterate over all vertices that have exactly two neighbors and check if these neighbors are also connected to each other. If so, a triangle is found.

Block 4

In this group, it is enough for each vertex $x$ to iterate over all pairs of its neighbors $(u,v)$. Then we check whether there is an edge between vertices $u$ and $v$. This works with a complexity of \mathcal{O}(n^2) since each vertex can have up to $n$ neighbors.

Blocks 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 will take \mathcal{O}(n\sqrt{n}) time. Then we find triangles that consist only of heavy vertices. To do this, we remove all light vertices and repeat the counting. This is also done in \mathcal{O}(n\sqrt{n}).

The overall complexity of the algorithm is \mathcal{O}(n\sqrt{n}).

Blocks 6-7

To find the best triangle, for each vertex $x$, we need to consider the triangle formed by the two largest edges radiating from $x$ (if such exists). There are $O(n)$ such triangles, so we can find the solution in O(n \log n) or $O(n)$ depending on the method of finding the third edge of such triangles.

Let us 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 \geq l_2 originating from the vertex situated between the edges l_2 and l_2 (denote it as $v$). Then a star centered at $v$ will be a better answer than our triangle:

[ star l_2 + l_3 + r l_2 + l_3 + l_1 = triangle ].