MCO16505 - Editorial

PROBLEM LINK:

Practice
Contest

Author: Zi Song Yeoh

DIFFICULTY:

MEDIUM

PREREQUISITES:

SQRT DECOMPOSITION

PROBLEM:

Find the number of triangles with pairwise distinct edge colors in a graph.

EXPLANATION:

One way to do it is to divide the vertices into heavy and light. Heavy vertices are vertices with at least \sqrt{2m} neighbours. The rest of the vertices are light.

For each heavy vertex w, we iterate over all possible edges (u, v). Then, we check if (u, v, w) form a colorful triangle. This part takes O(m\sqrt{m}) time.

For each edge with both endpoints light, we iterate through the adjacency list of one of the endpoints u and check if the two endpoints and the vertex from the adjacency list form a colorful triangle. Note that care has to be taken to avoid overcounts (in particular we should ignore heavy vertices, for example). This part works in O(\sqrt{m}) per edge and thus O(m\sqrt{m}).

The complexity is O(m\sqrt{m}).
There seems to be other solutions as well but I will not describe them here.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

RELATED PROBLEMS:

//