XXIII Colombian Programming Contest - Second place!
Sep
17

As I had said, last saturday was the XXIII Colombian Programming Contest. It took place simultaneously in 6 cities of Colombia with a total of 93 competing teams. This competition was the qualification round to participate in this year’s International Collegiate Programming Contest (ICPC). The Top 40 teams have advanced to the next contest that will take place next October 24th in Bogotá, to compete against Venezuela and Ecuador and decide who will advance to the World Finals in China.

We ended second, solving 4 of the 10 problems. Here’s how it went.

Resources

Here is the problemset. Here is all the code we wrote that day (exact zipfile of our folder from the competition. Also contains incorrect solutions to the problems we couldn’t solve). Here is the final scoreboard. Here is the input/output used by the judges.

The contest

Supposedly we had to be at 8 o’clock in the morning at the university but having competed in previous contests, I knew that I could arrive later, which I did. Thankfully, my teammates had arrived early and they already had my T-shirt and badge ready. We had a quick breakfast in the cafeteria and then proceeded to enter the contest room for the warm-up.

Warm-upproblemset

We won the warm-up! Something amazing happened. Before the competition started, we looked at the titles of the problems and one of them was “Birthday paradox”. Then Daniel said: “Did you know that if there are 23 randomly chosen people, the probability that at least two of them have the same birthday is greater than 0.5?”. Axy and I where like “Really? Why? Let’s see” and we found the formula and checked that it was true.
10 minutes later, when the warm-up started, I was amazed since the problem Birthday paradox asked exactly for the formula we had calculated before the competition started. That’s real luck!

Unfortunately, somebody deleted the warm-up scoreboard from our computer during the break after the warm-up, so I don’t have any evidence that we indeed won.

Main contestproblemset

We had lunch and then got ready to start the fight. We painted our faces like some sort of aggresive indians because we wanted to intimidate the competitors. Sadly, we finished looking like some cute kitties and being laughed at:

From left to right: Axy, me and Daniel

Anyway, back to bussiness. The counter started. 5 hours left and I was already feeling bad. I was very nervous but tried to stay calmed. I read the problems and decided to go for problem F.

Problem F – Burger time? Solved on minute 50. 2 wrong tries.

This was certainly the easiest problem. I read it and thought doing binary search would be fast enough, with an O(n log n) algorithm. Unfortunately, this solution timed out. I tried to optimize it a little and submitted it again. Time limit exceeded again! Fuck. I looked at the board and like 3 teams had already solved it. I thought there must be a linear solution and after thinking a little I finally came out with an elegant and short linear solution. I felt the relief of solving the first problem, as I knew we where now classified for the Regionals.

Problem C – Best coalitions Solved on minute 100. 2 wrong tries.

I read this problem and immeadiately the bells of dynamic programming rang in my head. I thought this was going to be straightforward but I coded it and received a Runtime Error verdict. Then a Wrong Answer. I honestly didn’t know what was wrong, so I changed some things here and there and submitted again and finally got a Yes. I think the problem was with reading the input.

After this, the Silence Hour begun. And we were placed ~9th place.

Problem I – Langton’s ant Solved on minute 269. Correct on the first try.

Now, it’s exactly because of problems like this why I sometimes hate Colombian National contests. It was an obvious easy simulation task. Except for one detail. The input was given as a huge integer that should be converted to binary. As Amy Winehouse would say, “What kind of fuckery is this?”. There’s no fun in this, it just makes the competition Java biased and boring for us, real language coders. Here’s something I want to shout: Using Java doesn not make you tough, funky or cool. It’s like having a sign that reads: “Look at me, I use Java! When I grow up I will be a garbage collector!”. And yes, anybody can use BigInteger.

I didn’t code this problem, Axy did. I just went straight to the bathroom to cry for sadness. Here in Colombia we have a cruel enough conflict. There’s drugs, violence and crime. Why the fuck do we want to make things worse by forcing innocent colombian students to code in Java?

Problem D – Informants Solved on minute 280. 2 wrong tries.

I had been struggling with this problem for most part of the competition. I was thinking of an over complicated solution using 2-SAT with didn’t quietly went well and gave me two erroneous and frustrating submissions. Near the end, I was tired of thinking and was about to give up with this problem when I noticed the number of informants was small (20) and coded a O(2^n) brute force solution that gave us a Yes. Yes! The lesson: Don’t get fancy with complicated algorithms, simple solutions are better (As I also confirmed later, when somebody told me about an even easier solution which I sadly forgot).

Well, I’m not personally satisfied with the results but we did all we could. I think the lack of training was evident. Too much work is harmful.

At the end of the competition, our PC^2 looked like this:

Our submissions