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.

PNOI 2k8 Problem A: A Simple Task

Problems from PNOI2008

Type: mathematics
Difficulty: easy

The first thing that came to mind in looking at this problem was "prime factorization".

Every positive integer has a unique prime factorization, and there is an algorithm for outputting the prime factors of a number n:

p = 2;
while (p * p <= n) {
  if (n % p == 0) {
    output p;
    n /= p;
  } else p ++;  
}

Simply put, if the current prime number being considered divides the number n, divide n by p (and output p), otherwise go to the next prime number, until what remains is prime.

There are some details of the loop that need noting: p does go through non-prime numbers, like 4, but, at that point in time (what is left of) n cannot be divisible by 4, otherwise, it would have been divisible by 2, and then divided by 2 before p becomes 4; the loop condition basically ensures that, if it is not met, the value in n is a prime value, but how?

Those familiar with the Sieve of Eratosthenes know that you can determine the primes in the range of 2 to n by marking the lowest uncrossed number as prime, crossing out all its multiples, then repeating until no more values can be crossed out. Experience will tell you that once you cross out the multiples of the largest prime less than or equal to the square root of n, the remaining uncrossed numbers are all prime.

This is because if one of the numbers between the square root of n and n was composite, say c, it would have to be a multiple of a number also in the range, say p < c, otherwise it would have been crossed out. But c has to be at least p * p, and p * p is greater than n, so that's not possible.

That explains the prime factorization algorithm, but how do you solve problem A?

We simply divide n by 2 as many times as possible, counting: whatever remains is odd.

p = 0;
while (n % 2 == 0) {
  p ++;
  n /= 2;
}
output n, p;

Philippine National Olympiad in Informatics 2008

And, for my next post, another blow-by-blow of a programming competition I am a judge at: PNOI 2008. Here at Faura Hall in AdMU, basically checking internet access. Will see if I can actually have a blow by blow. If not, join me here for the summary.

Edit: Boo, they shut down the internet throughout our side to ensure lack of net-access in the venue. Ten contestants, winner got problems A and B (trying D) and runner-up getting A (trying B and D). One more contestant tried A.

Edit: Forgot to mention technical problems causing late submissions. Fourth contestant tried A and B.

Will do a rundown of problems in separate posts. Stay tuned.

Migration

After an aborted try, and much soul-searching, I am now finally ensconced in the island-nation of Singapore, to try my luck in a rat race of a different arena.

I'd like to extend my thanks to all my friends, and my relatives, who have supported me throughout this time. Whatever success this new phase of my life will bring will definitely be a reflection of the help you have given me.

A Month After, and Two Days Too Late

Again, looking for a new job. Staying at work was fun, but now, strangely, I go from working, to working student, to just student. Later, it'll be delinquent student...

Summon the Thunder

Well, after a brief stint of "trying to be SQL savvy and only somewhat succeeding", I am back to prototyping, and what a doozy it is! A veritable whirlwind of changes. I do hope we can get to finish by tomorrow.

Escapism

Am sort of escaping (lack of allotted) work right now, trying to be productive by scanning my mails. Isn't this the reason why there isn't access normally? But I don't want to do this often.

I will be back at my station in a bit, but it does feel good to be typing with purpose...

Standby

Today's dinner was interesting, as it had mojos with them. What's interesting is that I didn't pay for the mojos.

Anyways, today was the first standby that I had stood by, and it was interesting. I am reminded of how much more work our bosses have, because I'm fairly sure that they're still there, talking with their overseas counterparts, trying to make ends meet, where one end is the end user, and the other end is, well, me. Of course, all the interesting stuff happens in-between and thus must be realized at that level.

I'm mostly thankful that I'm at home now, instead of later.

Home is Where You Lay Your Head Down...

... when not laid close to the keyboard. Barely made the train home, but it's all right. Still have seven screens for tomorrow, which are hopefully easier than those made today or yesterday.

And this is supposed to be easier?

Narcolepsy

If I don't survive this week, it'll be due to my heightened state of perpetual sleepiness. On the plus side, work keeps me awake. On the minus side, repetitive work feels like non-work, and I start to drowse.

At least I've gotten over this Monday's shellacking. And my legs aren't tightening up anymore.