Pencerahan

My team is Ainge ST, coached by Fazat Nur Azizah. We are from Institut Teknologi Bandung, Indonesia, with following members:

- Alfonsus Raditya Arsadjaja, Informatics 2014.

- Luqman A. Siswanto (me), Informatics 2013.

- Wiwit Rifa'i, Informatics 2013.

Radit got hit by a motorcycle. He broke his glasses and some injuries in shoulder and legs. Fortunately, he was able to recover glasses the next day. Until contest day, he still had light injury.

For each team, their strategy will be different. And sometimes a team's strategy doesn't fit to other team but I will tell our team's strategy:

This was actually easy problem but we did not read it first because nobody solved it before. After 2 hours, unexpectedly many teams solved this problem. I read the statement but found it hard. Then I clarified with Wiwit, it turned out that I misread the problem. I coded simple greedy with sorting, then got Accepted nine minutes later at minute 134.

This problem was about graph and quite complicated in detail. When I was coding D, Wiwit and Radit read the problem and found out that it could be divided to some cases, bipartite graph and non-bipartite graph. And hard part was the following sub-problem: given 2 group of numbers, group A and group B, each can have until 100.000 elements. The element can be the same. There are queries, to change an element from group A or group B to some value. After each query execution, we should compute the smallest difference of value between an element from group A and an element from group B.

Wiwit found a solution. For every element from group A, we maintain the closest element from group B to the left, and to the right. It could be implemented with heavy use of set STL. But yesterday in warm-up contest Wiwit coded exactly the SIMILAR technique and failed. Fortunately, in proper contest he did not code it directly, and discussed with us instead. When he told his solution, somehow he found a way to implement the same solution using segment tree but with much cleaner detail. An hour into coding, he submitted, and got Accepted at first attempt!!! It was minute 185. It turned out that yesterday experience gave a useful lesson for him not to code "raw solution" directly, but discussed the detail with teammate instead.

At this point, we were in the top of scoreboard with 7 problem solved. We were really happy until I almost cried T_T But we realized the clock was still ticking, we should continue the work before it was over.

We had 5 problems unsolved. E and K had no attempt from top teams, so we decided to skip that two. The others are G, H, and I. At this point, each person should read each remaining problems, and started solving problems from the most feasible one.

I read the problem and directly found the solution using simple BFS. Given 2D grid and two points, starting point and finishing point. These two points form a shape of rectangle. There are N circles, given the center point and their radius. Check if there is an arbitrary way to visit the finishing point from starting point. The way should not intersect with the circles, but can touch the circles, and the way should be inside the rectangle.

My solution is to label the circles. We gave a circle with label A if it intersects with upper-hull of rectangle, and gave label B to circles those intersect with lower-hull of rectangle. If two circles intersect, we gave an edge between two circle. If there is a way to visit B-label from A-label, then there is no way to visit finishing point from starting point. It's correct because a path of circles from A-label to B-label will "block" us to visit those two points.

I explained the solution to Wiwit then he coded it but we got Wrong Answer so many times. Every time he submitted, we always found corner case. Even Wiwit decided to rewrite to a brand new solution using geometry library from our team notebook. We didn't get accepted for this problem until contest was over.

Given an undirected tree with N nodes. N <= 100.000. There are Q queries, Q <= 5.000. Each query, given K nodes (K <= 50). For every query, compute the minimum sum of distances between any node and those K nodes.

The problem is how to find the so-called "center node" of those K nodes. My approach was to fix a path between 2 nodes. And find the most cheapest center using ternary search. For a fixed path of two nodes, finding the most cheapest center can be found in O(K log^2 N) using Lowest Common Ancestor (LCA) and ternary search. For every node of those K nodes, we can build a path from that node to the farthest node of those K nodes, hence there will be K paths. So the total complexity of solution will be O(Q * K^2 * log^2 N). I calculated and it was not fast enough to get accepted. So I didn't implement this solution and let Wiwit code geometry problem, G.

After contest, the editorials were distributed to participants. It turned out that most optimal center of nodes is always one of the LCA of all-pairs of K nodes. And the magic was: all-pairs LCA of K nodes were actually not O(K^2), but O(K). Hence the overall complexity was O(Q * K^2). I didn't know this magic property before, so I learned something new here.

Given N unique strings. and a number K. We should abbreviate every strings to K characters. The abbreviations should be the sub-sequence of the original string. If a string is lexicographically smaller from other string, then the abbreviation should be lexicographically smaller too. The first character of abbreviation should be the first character of original string.

My approach was to assign the abbreviation greedily. We chose the most lexicographically smallest abbreviation for every string, hence giving more space for abbreviation of next strings. For every string, we maintained the most smallest allowed abbrev. Obviously the most smallest allowed abbrev for the first string is AAA...(K times).

I didn't code it in contest because I was not sure with that greedy solution. Then after contest I coded this approach, submitted here, and got accepted at first attempt T_T

With 3rd ranking at Jakarta site, there is possibility we will get World Final slot in Beijing, China. However, we are still waiting for other regional results. Hopefully the best will happen. Will update this blog soon if there are any news!

UPD: The result is out. We are advancing to World Finals! Last time ITB went to World Final was 2013. Such an honor to bring our university back to attend World Finals after several years.

External links:
WF Announcement:
http://blog.sina.com.cn/s/blog_b946da100102xpg6.html

Practice online judge
https://training.ia-toki.org/problemsets/101/problems

Editorial from problem-setters
https://github.com/jonathanirvings/icpc-jakarta-2017/blob/master/icpc17-analysis.pdf

Contest repository
https://github.com/jonathanirvings/icpc-jakarta-2017