PNOI 2k8 Problem B: Rina's Triangles

Problems from PNOI2008

Type: mathematics, data structure
Difficulty: easy

Rina, in the title, refers to Rina Caballar, a former co-worker of mine and current co-worker of Dr. Pablo Manalastas, head judge at PNOI 2k8, who provided this problem. This problem was originally given in last year's Javacup, which is an annual collegiate two-man team Java programming competition hosted by CURSOR, a UP Computer Science organization in which I have had the privilege of previously worked; they were last year's judges.

Dr. Felix Muga II, another judge at PNOI 2k8, was the one who first noted that the triangles resembled Pascal's triangle, though the operation was subtraction instead of addition, and that the number of elements in each "succeeding" row decreased by one instead of increased. Keeping the visual, it probably works better imagining that the triangle pointed downward instead of upward.

89  78  12  13
  11  66  1
    55  65
      10

The solution is to generate the triangle and compare all pairs of numbers to determine if any two of them are the same. This can be done with one array, and it would be easy to do the comparison that way, but I'll try to maintain the triangle shape in a two-dimensional array, where generating the triangle is easier.

for (i = 1; i < 4; i ++)
  for (j = 0; j < 4 - i; j ++)
    if (tri[i - 1][j] > tri[i - 1][j + 1])
      tri[i][j] = tri[i - 1][j] - tri[i - 1][j + 1];
    else
      tri[i][j] = tri[i - 1][j + 1] - tri[i - 1][j];

The trick is to compare all possible pairs of elements of the triangle: what you basically want is a way to keep track of one element while going through all the other elements "after" it, comparing them, then going to the "next" element. This is why an array would make it easier to do: "after" and "next" are simply the elements whose indices are larger. We try to simulate that here:

flag = TRUE;
for (i = 0; flag && i < 4; i ++) {
  for (j = 0; flag && j < 4 - i; j ++) {
    for (m = i; flag && m < 4; m ++) {
      if (m == i)
        n = j + 1;
      else
        n = 0;
      while (flag && n < 4 - m)
        if (tri[i][j] == tri[n][m])
          flag = FALSE;
        else
          n ++;
    }
  }
}

Note that flag is used to determine whether or not two elements have been found equal. flag does not need to be a Boolean (truth) variable: flag can be numeric, 1 and 0 can replace TRUE and FALSE, and the comparisons changed accordingly. When two equal elements are found, all the loops will terminate, so no additional comparisons will be made.