ATOMS - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

First, say that two items x and y are “related” if there is no subset S _ i with one of x,y in S _ i but not the other. That is, x and y may appear together in an atom. Clearly x is related to itself and if x and y are related then so is y and x. Finally, if x is related to y and y is related to z, then x is related to z. Thus, we can partition the items into subsets A _ 1, …, A _ k so that any two items in the same subset are related and no two items in different subsets are related. These subsets A _ 1, …, A _ k is a partition of the items into atoms. I claim this is optimal. If there was a feasible solution using fewer than k atoms, then there must be some subset among these atoms that contains items from different A _ i subsets which is a contradiction.

There are a number of ways we can proceed from here. The most straightforward is to build a graph whose nodes are items such that two items are adjacent if they are related. Then the problem boils down to counting the number of connected components of this graph. The straightforward way of building the graph is good enough. For each of the O(n^2) pairs of items we check them against the m subsets to determine if they are related. Then we use a linear-time (so at most O(n^2)) search of the graph to determine the number of connected components for a total running time of O(n^2m). Of course, seasoned veterans will see many shortcuts to this approach such as using bitwise operations (m <= 30 encourages this) or the union find data structure to shorten running time and/or coding time. In fact, the graph doesn’t need to be explicitly built. The input limits were kept low to encourage multiple approaches.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

2 Likes

In the Setter’s solution, once we have built s[], it will contain the same value s* for all numbers ‘i’ that are related.
So we can simply iterate over s[] once using a map to count the number of distinct s* values. This will be the desired answer.