### SRM 693, D2, 250-Pointer (TriangleEasy)

### James S. Plank

Sat Sep 17 02:02:02 EDT 2016

Like many topcoder problems, this one is solved easily if you don't try to be
too smart. Let's distill the answer in its simplest terms:
- If there exist nodes
*i,*
*j* and
*k* such that there is an edge from *i* to *j*,
*j* to *k*, and
*k* to *i*, then there is a triangle.
The answer is zero.

- Otherwise, if there exist nodes
*i,*
*j* and
*k* such that there is an edge from *i* to *j* and
*j* to *k*, then we have two sides of a triangle, but not the third:
The answer is one.

- Otherwise, if there exist nodes
*i* and
*j* such that there is an edge from *i* to *j*,
then we've got one side of a triangle, and we need the other two: The answer is two.

- Otherwise, the answer is three.

So, you need to set things up so that you can answer the questions above. The constraints
are small -- *n* ≤ 50 -- so you can enumerate all combinations of *i*, *j*
and *k*. That enumeration is a triply nested **for** loop, whose running time
complexity is *O(n*^{3}). 50*50*50 = 125,000 -- that fits easily into
Topcoder's time constraints.
The last piece of the puzzle is the following:
given *i*, *j* and *k*, how do you determine whether there are edges from
*i* to *j*,
*j* to *k* and/or
*k* to *i*? You could run through the **x** and **y** vectors, but
that will cost you another factor of *n*. To be fair, it may well be fast enough
for topcoder, but instead, you can make those determinations in *O(1)* if you
use an *Adjacency Matrix*. This is a two-dimensional (*n X n*) vector, **A**,
where **A[***i*][*j*] equals one if there is an edge between nodes
*i* and *j*

Your first step, therefore, should be to create an adjacency matrix from **x** and **y**.
Then enumerate all *i,j,k*. Once again, it doesn't pay to be too smart in this enumeration.
I had each of *i*,
*j* and *k* go from 0 to *n*, because the constraints say that there will
be no edges from a node to itself. Therefore, if, for example, *i* equals *j*,
we don't have to worry about our code thinking that it can make a triangle, because there
will be no node from *i* to *j*.

I'm guessing that the number of coders who got this wrong was due to the following. Suppose
you enumerate all *i > j > k*. And in your inner loop, you test:

- If there are edges from
*i* to *j* to *k* back to *i*, return 0.
- If there are edges from
*i* to *j* to *k*, set your current best to one.
- If there is an edge from
*i* to *j*, and your current best is three, set it
to two.
- Otherwise, do nothing.

That is going to fail when you have three nodes, and an edge from 0 to 1. Why? Because the
only time that the inner loop gets executed is when *i=2*,
*j=1* and
*k=0*, and you'll note, this combination of *i*,
*j* and *k* won't set the current best to one in the tests above. In my code,
I test every *i,j,k* combination, and even though there's a lot of redundancy, the
code still executes in *O(n*^{3}) time, which is plenty fast.

**My Solution**