Living in NlogN World

The IOI 2009 is over and a new champion has arise. This time is Henadzi Karatkevich, a 14 years old kid from Belarus. Yeap, you're reading well, only 14 years old.

The problems of this years were 8 instead of the traditional set of 6 problems. Even more impressing is the fact that the solution for full score of most of the problems were O(NlogN). 6 out of 8 problems in total. The other two were about simulation and DP, very easy in fact...

You may be used to solve problems with "small" constraints, but this year IOI was for those who are not used to solve problems with really huge constraints. It was common to find constraints as N<(500.000, 1.000.000, 1.000.000.000) and their naive solution is O(N^2), O(N^3) or O(2^N). So, how the problems were solved for full score? Two main techniques were used:

• Sorting
• Binary Search

The idea behind each problem is the following:

Day 1:

• Archery: Binary Search with "simulation" (this was the hardest problem in the competence)
  
• Hiring: Sorting/Heap
• Poi: Sorting (one of the easiest problems in the competence)
• Raisins: DP, with a precalculation like Maximum Sum (UVa 108)

Day 2:

• Garage: Simulation (this one was other really easy problem)
• Mecho: BFS with Binary Search
• Regions: Disjoints Sets/DFS/Trees
• Salesman: Sorting (hard problem)

I'm still studying the solutions for Archery, Hiring and Salesman, because their solution is not trivial at all. In fact, Archery did not get any perfect score in the whole competence. The other problems are not big deal if you have knowledge in their solution techniques.

If you want to check the problems by yourself, go here.

Happy weekend for all of you!

More Randoms!

Random is on fashion!

My recent writings on my thesis were about pseudorandom numbers generators. You may be thinking "Why they are called pseudorandom?", and is a common question and a subject of large discutions.

By definition, any sequence of number is called random if is agree with the following properties:

1. There's no identificable patterns over the sequence
2. Is well distribuited over a set (even on an statistical set)
3. Is imposible to guess the future numbers based on the current numbers

If you're using an algorith to generate the sequence, is sure that you're breaking the last condition. And the reason is simple: There's no algorithm with REAL stochastical behavior.

If you're looking for real random number generators, then you should look elsewhere. One of the most common source of true random numbers are physical phenomena, like electric noise or atmospheric noise. Is posible to find random numbers generated from the second phenomena at www.random.org, and with the first in some cryptographic devices (such an IBM crypto-card).

Back to algorithms, there's several generator. One of the most famous and popular, and not necesarly most powerful, is the Linear Congruential Generator (LCG). This generator has been used since the last 40's, when the Monte Carlo simulation arise as a new technique. The basic recurrence relation behind a LCG is defined by:

Xi = (aXi-1 + c) % m

With this simple formula, is posible to generate a sequence up to m different values. When m is well chosen, it is possible to increase the generator period (numbers generated before it start to repeat), to a maximun of m. Nevertheles, a and c must be well chosen for improving the equidistribution over several sets. Park & Miller, defined and standard for choosing a, and m. They realized that (after some research) generators with c = 0 had the same or better behavior than generators with c!=0. The minimal standar that they pick was:

a = 16807; m = (1<<31) - 1

Some other implementations may be found in the code published on this post, including ran0, ran1 and ran2.

Is important to mention the Blum Blum Shub generator, proposed by the Leonore Blum, Manuel Blum and Michael Shub. This generator is widely used in cryptography. Due this work and some others, Manuel Blum (who born in Venezuela!) gained an Turing Award in 1996.

Link to home-made pseudorandom generators:
http://www.filehosting.org/file/details/50238/randoms1.1.cpp

Welcome newcomer!

Welcome to this blog!

In this blog I'll publish some of my algorithmic work, along with some description of it use, motives and related implements issues. Altough my mother language is Spanish, I'll write most of this blog entrances in English, in order to make it more accesible to other non Spanish speak people.

My first entry is a gift for those who believe in trust and integrity in bussines and a kick in the balls for those who believe in lying and explotation.

This entry contains the algorithm that produce the "secret" card code and serial of each of the DTV pre-paid system in Venezuela. Altough it may seem a security breach, this code is useless for generating fakes cards codes, because it simply work with the current time as the seed for the random generator, among others security tricks that I place in the system (pretty basic... if the code was not generated by the server, it is useless).

The card generator uses the famous Mersenne-Twister (MT) pseudorandom generator, designed for high speed and high reliability (long period, equidistribution over a 623-dimensional space). Even whe is "posible" to guess the sequence of random integers genereted by the algorithm after 624 generations, this code is not affected by that, simply because every 624 random integer generation, it is reseted. Nevertheless, this behavior may affect the performance of the code generations, because everytime the generator is reseted, it needs a "warming time" before getting able of produce decent random integers.

PS: @DTV: Do you really believe that an IBM cryptographic card was used to generate the codes? These NR guys were lying all the time!

Link to the code:
http://www.filehosting.org/file/details/50065/code_generator.cpp