Training Day 1

Adrian, Nicholas and Joshua work on problems on Monday evening, the first day of pre-IOI training.

After gathering all eight Australian IOI contestants and the four team leaders at the University of New South Wales, the pre-IOI training camp began with a two-hour problem session discussing solutions to the 2013 Asia-Pacific Informatics Olympiad. After a fine dinner at Tensaya, a Japanese restaurant in Kingsford, we became acquainted with the computer labs in which we'll be spending the next five days working.

One of the problems the students all solved today was Palindrome-Free Numbers:

"A palindrome is a sequence of digits that remains the same when it is read backwards, for example, 727 or 183381. A number is palindrome-free if it does not contain a palindrome of 2 or more digits. For example, the number 16276 is palindrome-free whereas the number 17276 is not because it contains the palindrome 727.

Your task is to calculate the total number of palindrome-free numbers in a given range (that is, numbers that are at least a and no more than b where 0 ≤ a ≤ b ≤ 1,000,000,000,000,000,000)"

Clearly, if a and b are reasonably small, you could solve this problem by hand. Between 120 and 140, the only numbers with palindromes are 121, 122, 131, 133, so the remaining 17 numbers are palindrome-free. You could write a computer program to count from a up to b and check each one for palindromes, however even modern fast computers can't check every number up to 1 billion billion in under a second (which is how long the program is allowed to execute for). Instead, the students have to come up with a clever algorithm using dynamic programming to quickly discard entire ranges of numbers. Remember, this problem was the one that most students found the easiest in today's exam!

Time for dinner now at a randomly chosen restaurant on Anzac Parade, see you in our next update!