Tomorrow I'll travel to Iasi to participate at the National Computer Science Olympiad, where I will compete with 400 of the best high-school coders in the country.


Regional Phase

I qualified first at my age section in my county, but it wasn't without being a little nervous about the result. I managed to "steal" 44 from 200 points, but the level of the problems were a little higher then I expected (here is my code for the regional problems). Overall, I am the 44th in the "country rank", which gives me hopes for another medal this year.

The Road

My bus departs at 8 am from Ramnicu-Valcea, and I arrive at 11 am in Bucharest. Then, we take the 12 am. train, and we will arrive in Iasi at 7 p.m. I suggest following the Twitter hashtag #oni12 for other updates.

First Day - Arrival

Team Valcea, after arriving in Iasi
Today, we arrived in Iasi, after the long 12 hours trip. The road wasn't boring because it was full of discussions over methods of implementing binary trees, or solutions for problems given at recent contests or debates about the famous Big O complexity for different algorithms. Moreover, I've missed mr. Ovidiu's stories about his "adventures" as a truck driver in USA.

In the train we travelled, there were about 6-7 counties + Bucharest (including some infoarena admins) and also the whole Olympiad board. Additionally, we met two of my teacher's ex-students which were also Olympic medallists, and now they are proposing problems in the committee.

Now, we are resting in the dormitories from Grigore Asachi High School, after playing a game of Whist. Tomorrow we will have free time, and then the opening ceremony.

Second day - Opening Ceremony

Opening Ceremony @ Faculty of Agronomy Hall
We woke up, a little tired, and ate at the cafeteria (the food is acceptable). Afterward, we went to the mall, to play bowling... I still suck at it. It's fun that we can travel by public transportation for free... but we got a little lost for a while.

The opening ceremony was one of the funniest I have ever seen. At the National Olympiad, the public hates long speeches, so we start applauding after every 3-5 words, when the speaker talks more than he should. Although, this time, the speakers were prepared for this, and they shortened their talk, saying only a few sentences, and waiting between them for the people to stop clapping. After the peak of the ceremony, the presentation of the Olympiad committee, the speaker said as a side note, that students in the board were more cheered then teachers... I wonder why...

Finally, we went for an hour at a billiards club near our dormitories, for a little relaxation before the big day of tomorrow: the first round of problems.

Third day - First Round

I'm alive, and with a good score: 92 points from 300. After 4 hours of brain draining, I managed to "steal" points from all of the problems, which were really beautiful:
  • Search - Dynamic programming on strings. You were given a set of 1.000 words, and a set of 100.000 queries. You start with a blank pattern, and for every query, you can add a character or subtract the last one from the pattern. After doing this operation, you have to figure out for every query the number of words which contain, a substring of this pattern. For example you have the words "palalila" and "alabala", and the queries "a", "aa", "aab", with the answers 2, 2, 1. The solution was a little complicated: you start searching from the left for every word on the first query, and then you memorise the position of the first letter. For the next query, you start from the last memorised positions. Another optimisation is pre-processing the words, to know in O(1) time what is the first letter on the right, for every combination. I managed to get only 20 points... and still don't know why :(
  • Urat (Ugly) - classical combinatorial problem, with permutations and 2 formulas. It's boring... but I got 52 points
  • Zlego - for 50 points you can apply any pattern matching algorithm... for 100 there was an "obvious" solution, using the prefix function from KMP to build a tree... got only 20 points
With this score, I am currently in my objective of obtaining a medal. Tomorrow, everybody thinks that it will be a hard day, because neither the problems from the local phase, nor the problems for today had graphs or trees... so we all know that it will include graph theory.

The atmosphere here is like an usual contest: people swearing because they allocated too much memory, or happy because their solution got more points then they expected. Our county, Valcea, isn't doing very well, because we are only 3 students in the "medals" right now, from 10. I hope tomorrow, will be a better day for us :)

Fourth day - Second round

My "workplace" for the 2 rounds
We all knew that today wasn't going to be easy... but we didn't expect to be really this hard:
  • Drumuri [Roads] -  I wrote 300 lines... but I didn't get any points... you were given a graph, were you could insert or remove edges, but every component had to be a road. Then, you had to answer several queries about other vertices in the roads.
  • Minerale - O(n ^ 3) dynamic programming... ugly, no points
  • Tarabe - it only took 20 minutes for me to implement the priority queue and to obtain 60 points. The full solution included a binary search.
The results have been announced on the official website: I am on the 20th place, and I will surely get a bronze medal. Our team, Valcea, is now standing quite well: 6 from 10 participants are qualified to the last round, where the participants of the national team are decided. I will write tomorrow, after the closing ceremony, all the medals and prizes we won.

After the contest, there was an interview organised by the Ecole Nationale Superieure Cachan, a French university which was giving 5 places for participating at activities organised by them in France. The interview went well, and I managed to speak a fair amount of time in French (until I started to talk about Computer Science). I am really confident about the result, because the interviewers looked really pleased at the end :-)

Also tomorrow, we will go sightseeing the town... but I don't know if we will even get up in the morning, because today we missed the bus and walked about 5 kilometres to our dormitories, and we are tired.

Fifth day - Closing Ceremony

Team Valcea after the Closing Ceremony
And the final results for high-school are (in age order)[mention means in the first 10%]:
  • 9th grade
    • Daniel Hainagiu - Silver Medal & first under the line of mentions
    • Andreea Popescu - Bronze Medal
  • 10th grade
    • Ionut Suciu - last Silver Medal
  • 11th grade
    • me - Bronze Medal - 20th place
    • Cosmin Oprea - Bronze Medal
  • 12th grade
    • Stefan Mirea - Silver Medal & last mention (and he coded in Pascal)
The Wood Spoon
In addition, there is a tradition to give to the member of the team who has the least points The Wood Spoon, with the signature from all the team members. This year it was Vali Modan's turn and he received it with "excitement".

For a little relaxation before the results, we visited before the botanical garden and went to the cinema, where we saw The Hunger Games and it reminded me that there are other important things, then being sad that I forgot to treat a special case, for which I lost 40 points and the silver medal).

Tomorrow will be the last day in Iasi for us. The last round is for the qualifications in the team for the international contests... but almost nobody except Stefan has real chances for qualifying in the "elite group". The train for Bucharest will depart at 11 pm, and I'll go straight home in Valcea, because Acadnet was postponed in May.

Sixth day - qualifications for the national team

Usually, there were 2 rounds for selecting the coders in the national team... but the "economic crysis" reduced it to only one round. It was a disaster for me... I got 0 points.

At 11 pm, we took the train to Bucharest, and after that, we took the bus and arrived in Valcea the second day at 12 am.

Final words

Overall I am happy with the result, the organisation was good and the problems were well balanced. Congratiulations to all and, as we the participants always say, next year it will be better.
Valcea Team, from left to right: Ioana Murgan, Stefan Mirea, Andrei Vacaroiu, me, Cosmin Oprea, Radu Oancea, prof. Ovidiu Dumitrescu, Vali Modan, Ionut Suciu, Daniel Hainagiu, prof. Miana Arisanu (Andreea Popescu is missing because she left to the Maths National Olympiad). Alex Mircescu from AISB, took the photo, and was as a team member