Tag Archives: Programming

About problem setting

I finally did it! In 2009-2010, I was helping the Codechef competitions to start.
I created more than 30 problems that were used across 12 different contests.
After, I got distracted (Master Thesis, PhD studies), and I stopped.
After those years, I finally took time to browse my local database of my problems and try and match them
with problems at Codechef. (I never uploaded them directly, it was always uploaded on spoj.pl, and then they were copied.) It was sometimes tricky, but I managed. I feel good about it, like when reconnecting after a long time with a friend. Here is the list of all of them.

What are my impressions about problem setting?
It is a perfect transition between participation in contests and work as a researcher. How so?
Continue reading

Enumeration of Antimatroids, part IV

I promise to finish this topic with this post! (part 1, part 2, part 3)

We ended with a rather efficient (but still double exponential) code that gave us hope to extend the sequence a little bit further. So, what can we improve? Constant, a little, by efficient parallelisation.
Continue reading

Enumeration of Antimatroids, part III

Let us continue the fun we had before here.

How do we speed up the calculation? Well, we need to limit somehow the space on which we perform the search.
Very obvious way is to eliminate the symmetries. Every permutation \pi \in S_n : \{0,1\ldots,n-1\} \to \{0,1\ldots,n-1\} induces a natural transformation on sets (and sets of sets, like antimatroids, …). For example:
\sigma = (120) = \{ 0 \to 1; 1 \to 2; 2 \to 0 \}
working on :
F = \{ \{\}, \{0\}, \{0,1\}, \{0,2\}, \{0,1,2\} \}
\sigma(F) = \{ \{\}, \{1\}, \{1,2\}, \{1,0\}, \{1,2,0\} \} = \{ \{\}, \{1\}, \{1,2\}, \{0,1\}, \{0,1,2\} \}
Continue reading

Enumeration of Antimatroids, part II

As explained before, we would like to extend the following sequence A119770 (don’t click, it will spoil all the fun!):
1, 1, 3, 22, 485, 59386, ...
Continue reading