SRM 693, D2, 250-Pointer (TriangleEasy)

James S. Plank

Sat Sep 17 02:02:02 EDT 2016

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: August, 2016
Competitors who opened the problem: 401
Competitors who submitted a solution: 279
Number of correct solutions: 190
Accuracy (percentage correct vs those who opened): 47.4%
Average Correct Time: 24 minutes, 21 seconds.

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³). 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³) time, which is plenty fast.

My Solution