Some weeks ago, the Nordic Collegiate Programmering Challenge was arranged at the University in Oslo. The teams “Its trivial” and “Mehiko” were ranked first and second in Oslo, and thus got the opportunity to represent the University at Oslo at the international contest NWERC - North Western European Regional Programming Contest 2012. NWERC was this year arranged in Delft in the Netherlands, a city located half an hour from Amsterdam. The contest gathers students from colleges and universities throughout Belgium, Luxembourg, Great Britain, Ireland, Iceland, Norway, Sweden, Finland, Denmark, Germany and the Netherlands, and the winners advance to the World finals.

As Comoyo supports and cooperates with the student organization “Maths, Algorithms and Programming for Students” (MAPS) at the University of Oslo, who organizes the NCPC and the participation in NWERC, here is a travel letter for the two student teams participating in Delft:

The contest itself took place on Sunday Nov. 25th, but the day before they arranged a practice session so the contestants could test the system. We were faced with four easy problems, and one hour to solve them. The problems were pretty simple, and almost all teams solved them. We had a problem with getting Norwegian keyboard layout on the system, so we were really thankful for having a practice session. In the evening NWERC arranged a dinner for all the constestant with free meal and drinks. Our team went home early to rest for the competion. Practice session

Over to the real contest. We all knew that the problems would be a lot harder than the Nordic Programmering Challenge, and knew we had to perform at our best to get a good result. The competion started at 09:30, and we were ready. We used a lot of time to spot the easiest problem, which was problem J. The problem was about fitting two lego-bricks in a opening, and the solution for this problem was to sort.

NWERC

The next problem, E, was a mathematical problem. We needed to calculate numbers of matchings of a cycle. We started by finding a formula for finding numbers of matching in a path, which is actually the Fibonnachi numbers, and then the formula for finding matching in cycles was easy to find. The biggest problem here was that for cycles on length 10 000, the numbers of matching became very big, much bigger than a 64-bit int. How should we solve this? Since none of us have worked with java recently, we chose to generate all the answers in python and then write it as a c++ code. We then discovered found out that the maximum file size is 256 kb, so we could not do that. So we had to bite in the sour apple and implement it in java. This took some time.

The next problem we solved was D, the digital clock. We had a digial clock with some line segments broken. Could we find out how much the clock was? This was solved by a brute-force-ish solution with some smart observations.

Problem I, Idol, was a 2-satisfiability problem. The problem was straight-forward, we had it and solved and coded within 15 minutes.

We saw that a lot of people had solved problem K, and started trying to solve it. After a hour, we finally made a observation which was needed to solve the problem. Unfortunately, it took a long time to code it, because of a lot of bugs. Catastrophically many bugs. The time was about to run out, and we tried to find all the bugs. Five minutes were left when we found the bug which probably would have give us the right answer, but time was to short for us to fix it.

We also saw that problem B was a problem we easily could have solved with dynamic programming. But the time was up. A little frustrating.

Its Trivial thinking

After the competition the results were in: “Its trivial” finished on a 26th place with four problems solved, and “Mehiko” finished on 43rd place with three problems solved. That is actually not bad. Full scoreboard is here. We were all agree that this was a great experience. For “Its trivial” this was our last time we are allowed to compete. Mehiko have new chance next year, and we look forward to the future!

Its Trivial Its Trivial

Mehiko Mehiko

On befalf of MAPS, we want to thank Comoyo for our cooperation!

Regards, Jing Kjeldsen Team member of “Its trivial” and leader of MAPS

comments powered by Disqus