My Blog

I’ve passed the Online Final Round of the Star Baidu Programming contest. Honestly, I don’t know how

The contest itself is comprised of two problems, to be solved within 10 hours. I did the first one for six and a half hours, and the second one for three and a half hours. And I expected to get a ‘0′ for the contest.

The first problem is about hyperlinks from one website to another. It’s basically a graph theory problem, and I can tell you, that’s about all I know about the problem. And I didn’t know anything about graph theory either. All I know is that given a set of data containing a directed graph with weighted edges, we are to first divide them into connected subgraphs, then take away the edges one by one such that: 1. each resulting subgraph doesn’t have a connection with other subgraphs, 2. in each subgraph, there is one node from which we can go to any other node in the graph by following the edges and every node in a subgraph can be visited with at least one other node in the same subgraph, and 3. the sum of the weights of the edges of each subgraph is minimal.

Of course, I’ve never formally studied graph theory, so I didn’t know what to do first. Then I thought of a way to solve the problem: 1. given the data, for each node, find the edge directed to it, which has the smallest weight (this way we have subgraphs), then 2. add up the weights in each subgraph and output. I thought this would be correct (yes with a simple test case), but when I tested another test case, it’s wrong (at least I thought it was wrong). The problem lies with the algorithm itself, since (try not to laugh very hard here) if we do step 1 in the algorithm above, we could easily end up with subgraphs which are actually connected to each other in the first place. There was not much time left when I discovered this, so I decided to just give up (of course I submitted) and try the second problem.

The second problem is a decision-making tool. We are given a set of rules and facts, and from that data we are to logically predict the result. There are two modes of operation, one is the goal-oriented mode, in which from the facts given, we are to use the rules and facts to determine if a given goal is achievable. The other one is data-oriented mode, in which we are given a goal and try to work backwards, also to see whether it is achievable. In both modes of operation, we are to output the order in which the rules are used.

I thought this was easy — I was wrong. At least my computer told me that when there was just 5 minutes left and when I tested my program (I only finished the goal-oriented part), it always segfaulted. So I thougt, what the heck, let’s submit. And then I forgot all about the contest, since I knew I wouldn’t make it.

So on the 28th I didn’t check my score. But in the afternoon a Baidu representative called me. He told me I’ve passed the Online Final Round. So I checked their website just now, and found that I got 50 marks, which puts me in the 26th place.

Now I’m left wondering how I could have got that score, since I can’t even solve even half a problem correctly. I really don’t know how, I think they must’ve got a mix-up or something…

Well, I passed the preliminary round, although I didn’t do very well…

I noticed that there’s a new link in the website for checking the score, and I found out that I got 60 out of 100, which puts me at the 126th position (from about 4000 contestants). I know, this is not so bad if we think in terms of percentage cut-off, but let’s think about this: out of the 4000 contestants, just how many actually solved all the problems? I solved them all, yet I only scored 60. And how many of them took took part just for fun? I don’t know. An optimistic estimate should be that around 700-800 contestants actually took it seriously, thus putting me in about the top 20%. But then what about the other contestants who misinterpreted the problem statements (see my previous post)? That leaves maybe 400 or so. So actually I’m at the top 40%.

But it still doesn’t give me high hopes, either. In the online final contest, only 50 contestants are taken for the grand final. Given my current programming skills, I don’t think I’ll be that far up. But I will try hard to make it into the grand final, although you shouldn’t be surprised if I didn’t.

Wish me luck. I’ll need it.

Today I took part in the Baidu Star Programming Contest. It’s not easy, given that the problem statements are quite vague. And especially on the input/output formats, it’s unclear (such as, "… the words are separated by whitespace…" and then in the input file I saw words terminated by a ‘.’ (full stop). What am I going to make of that?)

The prizes are quite nice, but I’m hoping to go to Baidu for an internship

Some facts:
1. The judge disabled some functions: file write functions, function pointers.
2. Even when I specify that my source is in C, the judge assumes it’s C++. I’ve confirmed this — some -Wconversion warnings are shown by gcc, but not by g++.

Overall, the problems are quite good; at least they are not so easy (but don’t take my word for it; I’m not a good programmer). I spent 9 hours and 30+ minutes to solve them all (time limit is 10 hours), and I’ve attached a screenshot of the final screen (well, the judge’s compiler was a bit too strict…).

One day, my friend <snip> posted news about BPK Penabur buying a large number of Microsoft licenses. Here is the link on detikinet:
http://www.detikinet.com/index.php/detik.read/tahun/2005/bulan/08/tgl/22/time/145116/idnews/425188/idkanal/349

I’ll highlight some important parts of the article:

Perjanjian itu meliputi penggunaan lisensi sistim operasi beserta
aplikasi Microsoft untuk 1000 komputer, pada 120 sekolah di 15 kota
yang dinaungi Yayasan BPK Penabur.

1000 licenses for 120 schools in 15 cities? WHAT THE FUCK are they talking about? AFAIK, a decent school should have at least 40 PC’s (so that every student in a class can use one). And this means that BPK Penabut will still pirate the software. Then when ASB (Association of Software Bullies) comes, they’ll have to pay…

…sekolah-sekolah di bawah
BPK Penabur akan diizinkan untuk memakai sistim operasi Windows XP,
aplikasi perkantoran Office XP, aplikasi Live Meeting, Visual Studio
dan Software Informasi Sekolah (SIS).

This means that schools owned by BPK Penabur are allowed to use Windows XP, Office XP, LiveMeeting (version?), Visual Studio (version?), and SIS(?).

Menurut Ketua Umum Yayasan BPK Penabur Robert Robianto, BPK Penabur
memilih untuk bekerjasama dengan Microsoft karena beberapa hal. Ini
termasuk penawaran SA dengan harga yang relatif terjangkau, pelatihan
dari Microsoft, ada program tambahan untuk sekolah, dibantu Microsoft
dalam pembelian komputer murah, serta pertimbangan perjanjian lisensi
apabila harga lisensi mendatang jadi lebih murah.

I suspect that Mr. Robert has been bribed by Microsoft into saying this. It’s marketing hype. Ignore it.

"Ada hal yang lebih penting yang menurut saya sangat hakiki, yaitu BPK
Penabur sebagai sebuah badan pendidikan yang tujuan utamanya adalah
mempersiapkan dan mendidik anak-anak bangsa, bukan hanya di bidang
akademik tetapi juga iman dan budi pekerti. Salah satu komponen penting
dari budi pekerti yang luhur adalah menghargai hak cipta (copyright),"
kata Robert.

So they are teaching kids to use proprietary software, when there are open source alternatives available. How nice.

Lagipula menurut Robert, software Microsoft yang mereka gunakan hanya
untuk kepentingan edukasi, bukan untuk produksi. "Kami percaya bahwa
dari sebuah lembaga pendidikan yang menghargai hak cipta akan
dihasilkan anak didik yang baik."

Yes, but when they go to their workplaces they are already used to Microsoft software, which makes them dependent on Microsoft. Then when they can’t buy the original versions they will pirate them, and it even worsens the situation. Mr. Robert must have been high on marijuana lately.

Selain SA, BPK juga mendapatkan program Learning Grant (LG).
Ini merupakan program bantuan pengembangan kapasitas seperti pelatihan,
sertifikasi dan pengembangan kurikulum untuk siswa dan guru.

The equivalent of selling your soul to the devil.

Microsoft memutuskan untuk menyertakan kegiatan training yang dipandu oleh Team MUGI (Microsoft User Group Indonesia).

Microsoft MUGs YOU!!!

As a side note, LUG’s are gramatically correct while MUG’s aren’t. Well, I use Linux for my daily computing needs, but I don’t think nobody ever uses Microsoft for anything. They may use Windows, Office, Visual Studio, etc., but they certainly never use Microsoft for something… or is Microsoft so sexy that it can be used for walking around with one hand sticking into your pants (a.k.a. STREET MASTURBATING)? I honestly don’t know. Fuck Microsoft. Fuck it hard.

Enough ranting, I’m ending this post.

edit: I’ve removed my friend’s name to protect his/her privacy.