1
$\begingroup$

I'm practicing for National programming competition and I came on this problem:

We are given undirected complete graph with N vertices. Every edge in graph has color red or green. We should find number of triplets(i,j,k) of vertices such that edges(i,j),(j,k)and(i,k) all have same color. We are given N and M where M is number of red colored edges in graph. And in next M lines we are given all red edges that exist in this graph. Rest of the edges(edges that are not in the input are green). N is between 3 and 300000 (3<=N<=300000) M is between 1 and 300000 (1<=M<=300000) Time limit is 2s I'm guessing that solution should have O(NlogN) complexity but I don't have idea how to solve it in that complexity.

Can someone please give me some idea on how to approach and solve this problem?

Thanks in advance.

$\endgroup$
2
$\begingroup$

It's enough to count the red degree and green degree of every vertex, then do some arithmetic.

First let's count the number of monochromatic paths of length $2$: pairs of edges $(i,j)$ and $(j,k)$ of the same color. For each vertex $j$, if it has $r_j$ red edges and $g_j$ green edges, there are $\binom{r_j}{2}$ red paths and $\binom{g_j}{2}$ blue paths that have $j$ as their middle vertex. This can be computed and added up quickly for all $j$ - you should be able to do it in $O(M+N)$ time.

Let's suppose that we've counted $P$ such paths.

There are $\binom N3$ triangles total. A monochromatic triangle contains $3$ monochromatic paths, but a mixed triangle still contains $1$ monochromatic path. So if $X$ is the unknown number of monochromatic triangles, then $$ P = 3 \cdot X + 1 \cdot \left(\binom N3 - X\right) = \binom N3 + 2X \implies X = \frac12\left(P - \binom N3\right). $$

$\endgroup$
1
  • $\begingroup$ Thank you so much! $\endgroup$
    – John
    Jan 23 '19 at 3:22
2
$\begingroup$

Let $A$ be the adjacency matrix for the red edges, and $B$ the adjacency matrix for the green edges. Thus $A+B = C$ which has all its off-diagonal elements $1$ and diagonal elements $0$. The number of monochromatic triangles is $$\frac{1}{6} \text{Tr}(A^3 + B^3) = \frac{1}{6} \text{Tr}(A^3 + (C-A)^3) = \frac{1}{6}\text{Tr}(C^3) - \frac{1}{2} \text{Tr}(AC^2) + \frac{1}{2} \text{Tr}(A^2C) $$ Now $$\eqalign{\text{Tr}(C^3) &= N(N-1)(N-2)\cr \text{Tr}(AC^2) &= 2(N-2) M\cr \text{Tr}(A^2C) &= \sum_{i=1}^N \deg(i)(\deg(i)-1)}$$ where $\deg(i)$ is the degree of vertex $i$ in the red graph, i.e. the number of red edges incident on vertex $i$. Thus all you need besides $N$ and $M$ are the degrees of the vertices.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.