ivy’s page

1

The contestants received a hand full of programming problems and had one computer per team (of up to 4 people) at their disposal. This single computer is commonly perceived a bottleneck but I think it makes the game quite interesting. While the contestants think, create solutions, and electronically submit their crafted programs, an judging systems tests these solutions. The jury monitors (and possibly interferes with) this process, and it’s always good fun to see which briliant and completely wrong (and everything in between) solutions the contestants came up with.

This year we had a succesfull match. A lot of teams showed up and the eleven problems made up a balanced and solvable collection. The average number of problems solved by a team was above 5, making a lot of competitors feel they played well (and they did). The winning team solved 10 of them, and all teams at least solved two (see detailed score information).

about the problems

Creating the right set of problems is a challenge. It’s easy to create hard problems; I remember organising the dutch programming contest in 1997 where the winners were the quickest of two student teams (of a total of 30 or so) solving 3 out of 8 problems. The other student teams solved 0,1 or 2. On the other hand, it’s been all too easy if all problems were solved by a team before the match ends.

An approach that balances the problem set and is applied each year, is making one real-real easy problem which should be solvable by any student. This year we had SpuitElf, which has a so deviously crafted Dutch title, I would never be able to translate it into English. In a long story (requiring smart reading), the problem introduces the hypothetical existance of extraterrestial races having a different number of fingers/claws/tentacles when compared to humans. Our decimal positional counting system is assumed to be based on our ten fingers, which would of course be completely different for these other beings. The asssignment is to write a progam that, given a number of fingers n for a race, writes down how the number n+1 is denoted in the n-count positional system. (If you don’t get it I can only tell there are 10 kinds of people in the world: those who understand binary, and those who don’t. What a great help I am )

Programming contest problems spring from several sources. Sometimes, it starts with an efficient algorithm around which a hypothetical context for the problem is created (possibly refering to real life situations). The other way around, it can be a real life encountered problem where one asks himself the question how to solve it. Usually, an initial idea needs some revisions before it’s mature. It should be unambigious, clearly and completely specified, solvable in a decent amount of time and without domain-specific knowledge, and if possible fun to read.

For instance, this year’s problem TAR was actually inspired by a board game called the Trans America Railway. While playing this game, I wondered, given a set of stations, how to determine the minimal amount of rail pieces required to connect them. This is a real hard problem, so it should be simplified for a bit. Hexagons are hard to handle and don’t amount to the real complexity of the issue at hand, so we’ll transform the original playing field into a grid. The problem is that with any number of stations, this is an NP complete problem. That means that it’s not solvable in an efficient way (Non Polynomal to be exact). But like with many NP complete problem, with a fixed, small n (a limited set of stations, in this case: 3) the problem is comprehendable and solvable in constant time.

Anyway, within the organizing commitee most of the time is spent creating the right, well specified set of problems and solutions. Creating non-ambiguous specifications means playing with the language carefully. Have a look at the resulting problems of this year (in Dutch).

I’ve noticed people stumble upon this page when they search for the compiler warning

warning: implicit declaration of function `rint'

The short answer:
If you compile with -ansi, the rint function prototype is not defined while you include math.h. So either

• declare the function prototype (double rint(double x);) in the code yourself, the linker will be able to resolve it,
• drop the -ansi compiler switch,
• use an ansi C90 standard compliant function (e.g. nearbyint, round or trunc)
• or write your own rounding solution (macro or function).

And now the original post…

Currently, I’m involved in organizing the yearly local programming contest of our institute. The programming contest is organized in the fashion of the famous acm collegiate programming contest. During the contest, teams of up to three people try to solve problems. The problems do not represent real-world it-problems, but I regard them puzzles which are challenging and entertaining from a mathematical and computer science (algorithmic) perspective. There’s a huge problem archive on the net if you’re looking for some challenges…

As I was preparring a solution in C, I stumbled on a rather odd bug. I narrowed the problem down to the following test case:

#include <stdio.h>
#include <math.h>
int main() {
  double d = 4.231789923234234;
  printf ("%f %d\n", d, (int) rint(d));
  return 0;
}

I compiled the program in two different ways (both compile well):

(If you wonder why I included -ansi at all; that’s part of the contest regulations.)

Studying the output, it’s quite obvious something’s wrong with the rint call (this wasn’t apparent in the original program). As I always compile with -Wall (the judging system does not, because warnings are interpreted as errors), my default safe warning-strategy gave away a hint:

warning: implicit declaration of function `rint'

Well, this means the rint prototype was not defined yet. According to the C specification, an undefined function defaults to the int return type (so the prototype becomes int rint(double)). The compiler is completely happy, but leaves an unresolved symbol to the rint function. The linker does not complain about it because it resolves the standard math library double rint(double) reference, but this means the double return value is interpreted as an int! This obviously is very wrong.

The question is, how can this be?

analysis

The man man-page of gcc, under option -ansi states:

The macro “__STRICT_ANSI__” is predefined when the -ansi option is used. Some header files may notice this macro and refrain from declaring certain functions or defining certain macros that the ISO standard doesn’t call for; this is to avoid interfering with any programs that might use these names for other things.

The rint man page (in the CONFORMING TO section I never read) says the function only conforms to the BSD 4.3 C standard; the ansi C90 standard is not mentioned. Therefore, when you include math.h while the “__STRICT_ANSI__” macro is defined, the rint prototype is not declared.

Well, problem tracked, but I would like to see these kind of compiler warnings by default! Until then, I can only advice to carefully check the used library functions when compiling with -ansi. Remember: -Wall is your friend!

I’ve read about phishing many times before, but today I was almost trapped by a fake mail. In a moment of negligence, I clicked the link in the following mail. I have used my paypal account quite a while ago, and I’ve been warned about paypal hacked accounts.

Security Center Advisory! We recently noticed one or more attempts to log in to your PayPal account from a foreign IP address and we have reasons to belive that your account was hijacked by a third party without your authorization. If you recently accessed your account while traveling, the unusual log in attempts may have been initiated by you. If you are the rightful holder of the account you must click the link below and then complete all steps from the following page as we try to verify your identity. Click here to verify your account If you choose to ignore our request, you leave us no choice but to temporaly suspend your account. Thank you for using PayPal! The PayPal Team Please do not reply to this e-mail. Mail sent to this address cannot be answered. For assistance, log in to your PayPal account and choose the “Help” link in the footer of any page. To receive email notifications in plain text instead of HTML, update your preferences here. PayPal Email ID PP697

Protect Your Account Info Make sure you never provide your password to fraudulent persons. PayPal automatically encrypts your confidential information using the Secure Sockets Layer protocol (SSL) with an encryption key length of 128-bits (the highest level commercially available). PayPal will never ask you to enter your password in an email. For more information on protecting yourself from fraud, please review our Security Tips at http://www.paypal.com/securitytips Protect Your Password You should never give your PayPal password to anyone, including PayPal employees.

Luckily, after I clicked the ‘PayPal’ link to set things right, my address bar showed http://217.11.100.3/~cs/. That immediately roused my attention; this could never be for real!

Further investigation showed

• the link I’d have to follow is http://217.11.100.3/~cs/paypal/ is a non secureip-adress that reverses to cliente-3.iberbanda.es,
• the message was generated by user ‘demo’ and originates from server 1n7-159.servernode.net

I forwarded the mail to PayPal, which luckily seems seems to take it seriously (they should!).

This made me realize the potential of bugs in browser software (like IE had for a while), where false or fake adresseses can be displayed in the bar. Well, they didn’t get my account info today