Dec 192014
 

Notes

Teams
We have 73 teams registered, but apparently 4 teams did not show up (3 locals and 1 foreign). There are 58 local teams from:

  • Top 50 of INC 2014 (Indonesia National Contest),
  • Top 5 ∪ 3 best Sumatra teams (total 7 teams) from ICPC 2014 Provincial Sumatra,
  • Top 5 from CompFest 2014.
    However, only 1 team claim their right to qualify from CompFest 2014; the other 4 forfeited as they wanted to compete in INC 2014 (they’re qualified from INC).

and 15 foreign teams.

The contest
Unlike in any other regionals (… which I know) where all teams compete in one big room, in Jakarta (Bina Nusantara University), teams are divided into 5 contest rooms. However, those rooms are separated by glass windows (you can see all other teams from any contest room), so, virtually, it’s “one” big room. Before the contest starts, teams were asked to verify their PC2 login account by trying to log in into the system. This to ensure there are no login problem (e.g., wrong password) when the real contest starts. Even though the committee seems to be confident with the username/password distribution, we encountered problems with two teams: they cannot login into their PC2. Upon inspection, it seems one team tried to use their practice session’s account (which of course, different), while the other mistakenly ripped the username/password and used a wrong account. Because of these problems, I have to run back and forth between contest and judge’s room (I had not gotten my walkie talkie at this time), and the contest was delayed for 15 minutes.

Aside those (login) problems, the contest itself was quite smooth.

This year we have two honorary judges: Denny from University of Indonesia, and Lucky Adhie from Bandung State Polytechnic. Actually, we invite other three: Dr. Teddy Mantoro, Niko Ibrahim, and Hardy; however, Dr. Teddy and Niko couldn’t make it to the contest as they have to attend another important meeting with APTIKOM, and Hardy suddenly had an important problem (he cancelled his flight the night before). We also have (quite a lot) assistant judges: Ricky Winata, Winardi Kurniawan, Eko Mirhard, Panji Kharisma, Felix Jingga, Felix Perdana, Albert Lie, Harryanto, and Ang Ing Ing. They are programming contest alumni which were invited to help with the judging process.

As usual, each accepted problem in the first four hours of contest will get a balloon of various colors. Each color represents one problem. I don’t remember the exact colors, but I’m sure the RED color belongs to the easiest problem (problem A). It was intended, as we want to make the atmosphere be more happy (red is a bright color, and contestant’s t-shirt is yellow). The committees only prepared 10 balloon colors (usually there are only 10 problems, but this year we have 11). So, there are 2 problems with the same balloon colors. We decided it’s going to be problem G and K, with balloons for problem K has a stripe (black tape) on it.

The contest was quite interesting. We expect some strong teams to dominate the contest, e.g.,

  • ThanQ+ from NUS – they’re the winner of previous year ICPC in Jakarta, with one member change,
  • Taipei-Hot from NTU (Taiwan) – they won 3rd place in recent ICPC in Taichung, and they’re 1st in the first four hours; also team from NTU (Taiwan) completely dominated ICPC 2010 and ICPC 2012 in Jakarta (there were no ICPC 2011 in Jakarta) even though it’s a different team,
  • from local teams: BerinGAS from UI – they’re the winner of INC 2014 who solved all the problems.

At early contest time, BerinGAS managed to lead the scoreboard for a while when their 3rd problem got accepted in minute 39. However, they took quite a while before their 4th problem get accepted in minute 80. At this time, there are already several other teams ranked higher. The contest was mostly dominated by ThanQ+ (as expected) and Team X from Korea University. ThanQ+ took the lead with 10 problems solved until their closest competitor, Team X, solved their 11th problem in minute 201; however, ThanQ+ managed to seize back their position when they solved the last problem in minute 218. ThanQ+ has penalty time of 1224, while Team X has 1292, thus the champion prize went to ThanQ+, while the runner up is Team X. On the third place, Java# from VNU University of Engineering and Technology, also managed to solve all the problems. Their last problem was problem K which was accepted in minute 291, 9 minutes before the contest end.

I noticed two notable teams which were able to solve 3 problems in the last hour of the contest:

  • UMN-Alpha (Universitas Multimedia Nusantara) from 4 to 7 (problem D, E, and F),
  • CPCU Happy Night (Chulalongkorn University) from 6 to 9 (problem D, G, and J).

How about the host teams (Bina Nusantara University)? I don’t know what happened to them. Lately they couldn’t perform as expected when competing in their own home. I expect the best teams (Sylph and Panda Shu) to solve 8 to 9 problems, but they only managed to solve 6 problems in this contest. They performed quite good in other local contest. Sylph even managed to get runner up position in INC 2014 by solving 9 out of 10 problems. Maybe there are some unknown factors in ICPC Jakarta (e.g., maybe they hate the contest room or distracted by the snacks?); who knows.

BTW, I noticed that ICPC contestants (in general) are getting stronger and stronger each year. Now three teams managed to solve all problems in contest time. It’s time for the problem-setter to prepare harder problems for them.

Dinner party
BINUS always managed to serve tasty local foods for the dinner party. Even though I was invited to the VIP room (different kind of food, “table manner” – more like serious discussion during dinner, etc.), but I enjoyed food not in VIP room better, of course, while chatting with contestants and old colleagues.

“Greatest achievement in ICPC”
During dinner party, I noticed one contestant (from local team) asking an escort to take a photo with him. He then took a photo together with the escort, only two of them in the photo; I don’t need to mention that the escort is a she, right?. When I confronted him, I asked “why don’t you asked her phone number?”. He replied that (with happy face), that was (the photo) already his greatest achievement in ICPC for 4 years :))

If you wonder who he is. He is the same “ITB” guy during the photo session.


  19 Responses to “ACM-ICPC 2014 Jakarta”

  1. The BEST thing about Jakarta regional contest that is rarely seen on any other contests (aside from the dinner party) is the editorial to the problems. That is, this blog serves the best of the event. Not even the world final has such an editorial.

    I would like to share some rather strange experience as a contestant. This is for problem D. As Suhendry wrote, that problem is purely combinatorial. Do some basic combinatorial problems and this problem should not be hard.

    Our first submission got ‘wrong answer’, although we are sure about the correctness of our solution. We then double-checked for any overflow errors, but we could not find one. We literally do the MOD operator after each statement. There is no such statement as {long long} = {int} * {int}. I remembered we have some {long long} = {int} * {long long}, but it should be all right, isn’t it? I also printed long long as %I64, as the previous contests in Binus used such format.

    In desperation, we do the following ‘unimportant’ changes:
    -no ints are used in mathematical operations.
    -we scan and print using ints to avoid the %I64 format.
    -after scanning, we typecast ints lo long longs.
    -before printing, we typecast long longs to ints.
    Suddenly it got accepted! Now we can’t explain why it didn’t get accepted the first time.

    ————————–

    Okay, now this is for problem E.
    The intended solution was explained in the blog. But one of my friend which was not in my team told me that their team solved it using simple DFS. Well, it should get TLE, but if you are lucky you can get it accepted that way.

    No wonder why so many teams got it accepted, while some top teams struggled in this problem.

    • I don’t know what happened to your D, but I also experienced a similar thing when preparing the problem. I made a mistake on the mod operation (a += b mod m, which is wrong). A common error on problem D is overflow (not sure whether this also happened to your D).

      As for problem E, some contestants also report to me that they managed to get accepted with a DFS for each Q query. It should be TLE. The mistake is on us; we did not code the DFS solution or any linear time solution for Q query (even though we’re aware of this), and directly prepare data which (supposedly) make the solution TLE. It seems the data was not strong enough, some teams managed to get accepted with this.

  2. I have question for problem F.
    when we check for second swords which have been satisfied by the first sword, if no first sword have
    satisfied it, what step we must take?
    In my opinion we must take one number(the length) to satisfied the second sword.
    But i still confused How the greedy technique to choose that number.

    • Let say each (second) remaining sword is a line segment [b,c], then our task it to select a minimum number of points such they cover all the given segments.

      To get the greedy solution idea, imagine you’re considering the point one by one from the left most (e.g., 1), and increase (move it to the right) one by one at each step. At each point, ask yourself whether this point must be chosen. The keyword here is “must”, it means if we didn’t choose this point, then some segments (to the left of it) will not be covered, e.g., because it’s the end of some uncovered segments. Try to figure out by yourself why this strategy will find the minimum number of the needed points to cover all the segments (it’s not hard to prove it by contradiction, i.e., assume there is a better solution by choosing a point which lie to the left of the “must” point).

      • How to handle cases like:
        1
        2
        1 1 1
        1 1 1

        ?

      • @Joe:

        I forgot the problem already.

        I’ve just checked your case with my code, and the output is 2. After re-reading the problem and solution in this post; supposed there are two dragons (like in your input): A and B; you need 2 swords to kill A (even though B <= A <= C), and the same set of swords can be used to kill B; thus, you only need 2 swords. The first sentence of the last paragraph of the analysis (F) contains the key-phrase.

  3. Problem E
    For query Q A B
    Did you check it by find the parent of A and B like on disjoint set data structure for every query?

    • Yes. We reverse the input order so we can use disjoint set data structure for each Q A B query.

      • So in the worse case, if we have skewed binary tree with 5000 query Q A B, where A is the last node and B is the second last node. Isn’t that will TLE?

      • Err… no. Disjoint set (union-find) data structure, using tree structure, has an O(log* N) time complexity for each find query, i.e. answering Q A B. Observe that it’s log*, much slower than log.

        This disjoint set data structure is constructed using the input tree, but it is NOT the input tree.

        You can find more about disjoint set data structure on the net, e.g.,
        http://en.wikipedia.org/wiki/Disjoint-set_data_structure
        Find “disjoint set forests”, especially the “union by rank”, of course combined with “path compression”.

        It is one of the basic data structure you should know; and it’s very useful, for example, when you want to implement Kruskal Algorithm to find minimum spanning tree on a graph.

  4. Could you please explain the implementation of O(N.K.E.M) in problem C? Thank you

    • @Lost Boy: for problem C, the naive transition is from state dp[x][k][e][p] to another is O(L). That is, by bruteforcing the 4 possible outcome of assist levels.

      It can be reduced to O(1) by precalculating the top two transitions based on the state of [x][k][e] in O(L). Then, to pick the best outcome, we only need to decide from the two possibilities, thus the transition cost is now O(1).

    • @FH: Oh? so is it O(N.K.E.L) or O(N.K.E.M) with M = 2?

      @Lost Boy: Theoretically, both O(N.K.E.L^2) and O(N.K.E.L) are O(N.K.E) since L in this problem is constant (4). However, it seems this constant factor plays an important factor here, so it’s good to know.

      • @Suhendry: it’s O(N.K.E.L + N.K.E.L). One is to precompute the top two best outcome, the other is to actually apply it.

        Actually, I suggested Suhendry to bump up the L to 10 so that it will make a bigger difference :P, but since we didn’t have enough time to modify the problemset, we just use L = 4.

  5. Hi, sorry to bother again, but after some time, I still don’t know how to solve D. Could you give any tips ?

    • You can count for each position [K+1..N] where p will be selected (of course p will not be selected if it lies in [1..K]). In other word, focus your attention on a particular p position first (then you only need to evaluate for all possible positions for p).

      Let say p lies at P: [1, …, K, …, P, … N]. Note that P should be between K+1 and N to be selected. There are 3 parts that you should analyse: [1..K-1], [K..P-1], and [P+1..N]. The segment [K..P-1] should be in increasing order (the ranks are worsen), otherwise p at P will not be selected, and p should be < rank at P-1. Gathering all the details, you just have to play with combinatoric (only nCk and n!). I don't remember the details, but that's the general idea.

  6. I have question for problem B.
    I still not understand how to verify a complete graph from the graph that we suspect as “barbel”. Could you help me? thanks

    • Pick any arbitrary node which has degree of |V|/2 – 1, let label this node as p. The neighbour of p is neighbour(p) = a1, a2, a3, …, ax, where x should be |V|/2 – 1. Now for each q of p’s neighbour, you need to check whether they also connect to all nodes in {p U neighbour(p)} \ q, i.e. set of neighbour(p) and p, and exclude q. Just a simple iteration suffices.

      For example, let p = 1 and neighbour(p) = 2, 3, 4, 5. Now you have to check whether node 2 also connects to {1, 3, 4, 5}. Check whether node 3 connects to {1, 2, 4, 5}, and so on, do this to all p’s neighbours.

 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>

(required)

(required)