Nov 082013

My Note

Here I want to share a bit about my experience as one of the authors and judges in this contest. In short, it was exhausting but fun.

Preparing the problem set
Preparing a good problem set is not a trivial task. There are a lot of things that have to be considered when you’re preparing the problems, e.g., there should be one very easy problem that can be solved by (almost) all the teams, but should not be a trivial problem; there should be several challenging problems such that no team solved all the problems, but these hard problems must be solvable in the contest time; it’s just a matter of which hard problems attempted by the teams, and these problems will be the deciding problems (determine the winner). So, somehow you have to be able to predict and “measure” the teams ability.

Usually I’m the one who prepare the easy and medium problems, because all other authors tend to propose more challenging problems. In this contest, I prepared problem A (the easiest), C, D and F. None of those problems are hard, right? The most challenging problem for this contest came from Derianto Kusuma (problem E) in which no team was able to solve this in the contest time. Problem J from Felix Halim was challenging as well, because you have to come up with a very-very efficient approach to solve this problem (constant factor in your algorithm does matter in this problem). On the other hand, there are only two teams who solved problem B from Derianto Kusuma; I thought this problem was not so hard, but it appears only a few attempted this problem and succeed.

There are couple of things you should do when preparing the problem (aside from adjusting the difficulty level of the problem set):

  • Write a complete problem statement and input/output format. Most of the authors gave me only the “idea” and the problem’s draft (sometime with the solution), and rarely send me a complete problem statement. Usually it’s my job to create a story and write the problem statement for them. Derianto Kusuma is an exception among the authors; when he proposes a problem, he will send you a complete problem statement! and the problem statement itself is already good so I don’t have to make a lot of changes (it reduce my work loads!). Felix Halim also wrote a complete problem statement (due to his “secret” intention).
  • Write a second solution for each problem. The author usually write the solution for his/her own problems; however, to ensure the correctness of the author’s solution, we have to write another “independent” solution for the problem. This is where a tester is needed; his/her job is to write his/her own solution for each problem without consulting with the author’s approach. Keep in mind though, it doesn’t mean the author’s solution is absolutely correct after it has been tested; it just reduces the chance that the author’s solution is wrong (both author and tester might make a same mistake causing their solutions to be wrong). The testers for this contest were Risan, Felix Halim, and me.
  • Prepare test data for each problem. Of course it cannot be only a random cases, you should also prepare some corner or tricky cases. Usually I consult with the author for each problem when preparing the test data.
  • Write a verifier code for each test data, i.e. to ensure all test data have correct format as specified in the problem statements.
  • Proof read all problems. You need someone (who you can trust) to proof read all the problems and make sure there is no error or ambiguity. Fiona Liausvia, Risan and Felix Halim were the proof-reader for all problems in this contest.

Preparing this contest took me ~1 month of my time! Well, not really 1 month for ICPC, but combine it with BNPCHS 2013, INC 2013 which also held around the same time, I have to leave my other works for more than 1 month! My work load on BNPCHS 2013 was not high as there are Jollybees (BINUS ICPC Teams) who help me with the problem preparation; however, there are only a few who can help with INC and ICPC. This is the reason why this write-up (analysis of problem set) is delayed. I didn’t even manage to publish write-ups for the previous two years; there are tons of my other (delayed) works that waited for me once ICPC is finished.

Preparing the system
The system was mainly prepared by Muhsin Sodiq, Hutomo Widjaja, and Surya Sujarwo (with his team). I only checked whether the system is ready or not one day before the 1st day of ICPC. Most of the PC2 set-ups were done by Hutomo Widjaja.

From the past experience (I think it was ICPC 2008 Jakarta update: it was INC 2011), we know that PC2 might crash if the size of input/output for the problems are too large. Back then, the system crashed when a lot of users tried to login into PC2; after some trial and error analysis, we concluded that (partly) the reason was because of some problems had a large input (~14MB). We used PC2 version 8.7 at that time, but in ICPC 2013 (as well as previous years ICPC), we used PC2 version 9.2. We don’t know whether this version has a same problem as its previous version or not, but we don’t want to take any risk. Therefore, we employed a “two layers of PC2” strategy for problems with large input (the idea was suggested by Eko Wibowo in ICPC 2008 INC 2011); I decided an input is large if it’s size is more than 4MB. For these problems, we didn’t upload the input/output in the main PC2, instead, we set up a new separated PC2 for these problems. So when a team submits a run for these problems to the main PC2, judge-A will “download” the run and resubmit it to the other separated PC2. This run then will be judged by judge-B in other PC2 and the response to will be given to judge-A; judge-A then give the response to the team. It seems in-efficient, but it works! We only did this for problem with large input.

Update: Eko Wibowo has just told me that the problem was caused by the insufficient memory on the server. PC2 version 8.7 somehow needs a large amount of memory whenever there are problems with large input. I remembered Surya Sujarwo profiled the performance of PC2 on the server. BTW, I think now they have a new server with larger memory (10GB).

The contest
This year’s t-shirt contest for committee is pink. I like the color.

We have 5 honorary judges (Denny, Hardy, Lucky Adhie, Niko Ibrahim, Teddy Mantoro), 4 main judges (Felix Halim, Risan, Winardi Kurniawan, and me) and 5 assistant judges (Hutomo Widjaja, Felix Jingga, Ricky Winata, Evan Leonardi, Ang Ing Ing). Honorary judges are those (from various universities) who are invited to be involved in the judging contest to ensure the fairness of the judging process, while assistant judges are those who want to help judging the contest (all of them are ex-ICPC contestants whom I trusted).

As usual, the contest was five hours. This year we don’t have a superior team like previous year (recall +1 ironwood branch from National Taiwan University who solved all problems in less than 4 hours), thus the competition was quite fierce. The first rank was changing a lot during the contest and observing the scoreboard was fun.

The contest started at 9:30 WIB, and around 10:00, all honorary judges and Felix Halim went out from the judge’s room to join the meeting with other local teams’ coaches. I don’t know any details about the meeting, but I guess it’s about encouraging other universities to host programming contest as well (to promote ICPC and develop Indonesian student’s talent in programming).

The contest ended at 14:30 WIB, and the winner, as you might already know, was team ThanQ from National University of Singapore. They solved 8 problems and the deciding problem was B which no team from other university solved it (there is other one who solved B, but they’re also from NUS). Teams in 2nd place to 5th place solved 7 problems and they are from National Taiwan University, FPT University, National University of Singapore, and Nanyang Technological University.

The dinner was great. Like previous years, there were ~7 rooms, each with different kind of dishes served and we can go to any room we like (have to visit them all!). However, I was a bit late, so I only managed to enjoy several dishes only (not all).

  12 Responses to “ACM-ICPC 2013 Jakarta – Problems and Analysis”

  1. are you sure there isn’t mod operation ?

    and this : j = j + 1, why it isn’t j = j-1 ?

    • Ah, you’re right, it should be j =j – 1 (updated).

      MOD operation is not needed, What we really need is whether a two substrings have a same hash value or not, not the hash value itself. There are only addition and multiplication operators, so overflowing the result doesn’t matter.

  2. ^that comment above is for pasti pas

  3. Halo Mr. Suhendry.
    Saya ingin sekali bisa berkompetisi di ACM ICPC. Saya Mahasiswa tingkat 2 di salah satu perguruan tinggi di bandung. Tapi skill koding saya tidak terlalu bagus. algoritma sorting saja masih bingung. Gimana ya kiat nya untuk belajar algoritma yg baik dan benar agar bisa nanti suatu saat ke ACM ICPC?

  4. How to determine which prime number should be used? I tried some prime numbers and the result is not as expected.

    • (Problem F). Just use large prime number (larger is better, its chance to collide is smaller). I used 1000003 and it’s fine.

      • I have implemented it and submitted on Live Archive, but got WA 😀
        Is there something wrong with my implementation? Could you please check it?

      • I didn’t read your code, but it failed the first sample input: PASTIPAS.

        • Yes and it works if I do MOD operation, but still WA on Live Archive. Does your solution with above algorithm still work on LA? Maybe you/others have added more test cases to break that hash function? Or my implementation wrong?

        • I’m the one who send the data to LA and I’m pretty sure LA’s admin was quite busy to do any changes on the dataset.

          BTW, I’ve just noticed an error in F’s pseudocode. There is one line which is wrong. Try to figure that out! 🙂

          hint: pay attention to the rolling hash (when you do the multiplication with prime number); you might want to check other resources on rolling hash.

  5. ^ problem F Pasti Pas!

  6. Problem H can be solved by Dynamic Programming,here I find two states,one is index of the current question,another is wrong answers used/left so far, and then minimize the answer. But this solution does not work,though sample test case gives correct output. I saw another boolean state in some accepted codes in HUST, which tries both minimizing and maximizing. Can you please explain why another state is needed here?

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>