Friday, 26 November 2010

The competition day! We had our breakfast around 5:30 am and at around 6:00 am, we waited for bus below. As can be easily predicted, the bus was late. After it was arrived, we went to the competition hall to compete. We arrived at the competition hall quite early, but since the competition was late, we need to wait around 90 until 120 minutes (I forgot the exact minutes).

Finally, the competition began!

Trung found some easy problems and start coding it. As I thought, he’s very fast. Only in some minutes, we have got accepted in 3 or 4 problems. Problem I interested me since it’s only about simple LCA. I coded it, and submitted. However, it got WA. I tried to debug it and got nothing wrong. Then, I asked Giang and Trung to debugged it for me, but none of us found something wrong in our code.

Trung kept solving another problems and I kept debugged my code @_@ After about one or two hours, I found that I didn’t call the subroutine for pre-calculating my LCA table. Hell, what a beginner mistake >_< After fixing it and submitting, we got AC. As I remember, at that time we had solved around 6 problems.

I took problem J and started reading. After a while, I found that it can be solved by meet-in-the-middle technique. After coding, I found that my code didn’t give the correct answer for the sample test data. After confirming with Giang, I found that I misread the problem. I asked Giang for his solution. He told me an alternative approach which he was very sure of. After discussing for some moment, I started coding it. Submitted, TLE. We gave it to Trung, he coded and got it AC with some bipartite matching. Actually, this problem is a standard problem about minimum vertex covering in bipartite graph.

After that, I took problem F. I found the algorithm, but could not finish my code. I tried to explain the algorithm to Giand and Trung, so they could code it for me. But, it seemed both of them didn’t understand my algorithm. I coded it, submitted it, got WA, tried to debug it, and submitted again, TLE. After doing more careful calculation, we found that the algorithm I used was too slow. Then, I changed it to totally different algorithm, but could not finish coding in time.

We solved 8 problems, and placed at 10-th rank. We really underperformed today, and I felt sick during the contest because of the heavy schedule. But everything was over.

We went to a museum by bus. I took some pictures in the museum.

pictures to be uploaded later

After wandering in the museum, we got to the Closing Ceremony. HKUST Optimus_Prime got the third place (one of the team member is Danqi Chen, Gold Medalist IOI 2008, best female contestant at that time), NTU Pigeons got second place, and the champion was from ZJU. Both the first and third contains a female contestant. Wow, today girls are very smart! 😀

We had Gala Dinner after the ceremony. Some teams took pictures, but nothing special here.