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?
Posted in Uncategorized
Tagged Codechef, Competition, Competitions, Games and Puzzles, Problem setting, Problem solving, Programming, Programming competitions, Programming contests, Recreations, TopCoder, Training
I always enjoyed seeing short and elegant proofs of theorems that I knew before.
I really enjoy this short proof that number of proper placing of opening and closing brackets(-th Catalan number) is equal to:
for example, there are 2 ways to properly place 2 opening and 2 closing brackets, out of 6 total ways:
())(, )((), )()(, ))((
First, we may transform the problem into one about walks on plane.
If we take (0,0) as a starting position, and assign to ‘(‘ a walk into UP-RIGHT direction, and ‘)’ a walk into DOWN-RIGHT direction, we might encode sequences of brackets. So, encoding of ((())))(() is:
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.
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, ...