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: 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(n3). 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:

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(n3) time, which is plenty fast.
My Solution