ACM-ICPC Asia Jakarta Regional Contest 2017

This is my last ICPC regional in my life as contestant. I am in 5th year in college, entry batch 2013. I had competed 5 times in ICPC regional before (Jakarta 14/15/16, Singapore 15, Manila 16). As this is my very last regional ICPC contest, I give my best effort for this contest. We are really ambitious to attend ICPC World Final as this is our deepest dream. I and my teammate (Wiwit) even postpone our graduation one more year to compete once more in ICPC. So this 5-hour contest will judge whether our sacrifice will be worth it or not.

There were 15 teams from Institut Teknologi Bandung attending Jakarta Regional. 45 persons departed with a big bus from Bandung to Jakarta. It took around 4 hours, until we reached Binus Square, the hotel we stayed at.

Team

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.

Preparation

Individual performance is not enough to become competitive in regional contest. ICPC is a team-based competition, so communication between members in team is important, and it needs to be trained too. We also need to practice efficiency to tackle problems, in order to remove unimportant high overhead due to context-switching between members working in only one computer.

Besides self-training to learn speed coding and learn new topics, we did team trainings. In a week before Regional Jakarta 2017 in every single day, my team did self team-training. We gathered in a place and simulated a 5-hour contest with one workstation only.

Here is complete list of our gym training, in case you guys are willing to train using the same problemset as us.

https://vjudge.net/contest/197702
https://vjudge.net/contest/197977
http://codeforces.com/gym/101606
http://codeforces.com/gym/101243
http://codeforces.com/gym/100253
http://codeforces.com/gym/101532
http://codeforces.com/gym/101194
http://codeforces.com/gym/101572
http://codeforces.com/gym/101412
http://codeforces.com/gym/101480
http://codeforces.com/gym/101485
http://codeforces.com/gym/101498

After team training. Some selfies won't hurt.

Specialization

Every team member has his own specialization:
- Radit: speed coder (for first-blood problems), ad-hoc, weird pattern problems, greedy
- Luqman: speed coder, DP, data structures, graph
- Wiwit: all math stuffs, geometry, advanced data structures, graph, other hard problems

Basically Wiwit is our team's carry. In many times, Wiwit solves "decider" problem. My goal and Radit's in every contest is to solve easier problems as quick as possible and as much as we can to minimize time penalty, so Wiwit don't have to "touch" easy problems. It will give him more time to work on thinking hard problems.

A week before

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.

A day before

There was a warm-up contest, and our carry was down. Wiwit was down.

We were given 4 problems, Radit and me coded 3 of them. But Wiwit failed to implement the last problem with heavy use of set from C++ STL. For an hour he debugged the code but still cannot find the logic flaw, and Radit always found the countercase. In the last 15 minutes, Wiwit surrendered and gave the computer to me, I rewrited, and coded alternative solution using segment tree, and got AC.

Debugging last problem at warm-up

I felt bad for him because I rewrote his solution. I suggested him to take a contest with easy problems when we had arrived to hotel to boost his morale. But instead of boosting morale, it happened:

Then we took AtCoder contest for 2 hours, and he performed not well too. I even had better ranking than him, which was RARELY happened.

It was bad for our team. Team carry's morale would indirectly project our result for the proper contest tomorrow.

Strategy

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:

For first 2 hours, we try solving easier problems as many as possible.

The last 3 hours, hopefully the remaining problems are hard problems only. Each person should read each unsolved problems, then we discuss, and divide the problems based on each person specializations. Each person will work on different problems. Then we will start working from most feasible problem to solve.

Contest

The contest was intense. You can read here, or even submit solutions.

A. Winning ICPC

Radit somehow found the way and grabbed the keyboard directly. He got Accepted in 4 minutes. He was our first-blood speed-coder today.

J. Meeting

Wiwit also somehow found the way and took the computer. He coded then submit but got WA. He found the misuse of IF logic and corrected it quickly, and got Accepted at minute 16. Sadly he didn't get the first AC, losing to Sukar ditaklukkan team at the same minute.

L. Sacred Scarecrows

Wiwit said it was DP problem and gave it to me. Given N x M 2D grid with N <= 14 and M <= 1000. Each cell of given grid will be either ^ or a dot. If the cell is ^, it means we cannot grow plant there. Then we should compute how many different way to grow plants to cells, if for every row there should be at least one plant, and for every 2 columns there should be at least one plant. I come up with O(2^N * 2 * M) DP state, but for every state I need O(2^N) transition. I discussed with Wiwit about this solution then Wiwit found O(3^N * M) total transition using the same state I mentioned to him before. He coded it but still got TLE. Then he found a way to optimize it to become O(2^N * N * M). Wiwit coded it and we were the first Accepted team at minute 81.

F. Random Number Generator

It was about expectation value. Some team solved this problem so we should start working on it too. Given a number N <= 3000 and some sequence number between 1..N with length K. There is a Random Number Generator (RNG) that continue to output numbers between 1..N uniformly. The RNG will stop if each number from 1 until N has been outputted at least twice, and so far it has been already outputted that sequence number with K-length. Compute the expectation of number until the RNG stopped outputting.

Fortunately, Wiwit gave me this link long time before, and he taught me about expectation value. I found out a fact: which number and how many times it has been outputted is not important. We only need to care how many numbers that already outputted zero times, once, and twice or more. I came up with DP O(N * A * B) which A is how many numbers that already outputted zero time, and B is how many numbers that already outputted once. We can deduct how many numbers that outputted twice or more by N - A - B. But A and B can be at most N, and O(N * A * B) was definitely too slow. I discussed with Wiwit about this solution. He did some paper work and found a critical observation. N can be excluded from computation and we can compute in O(A * B). Wiwit coded the formula and got Accepted at minute 111.

C. Non-Interactive Guessing Number

Meanwhile I and Wiwit were coding problems, Radit was working on this problem on paper. It was about weird ad-hoc stuff, as his specialization. When Wiwit finished with coding F, Radit was ready to code. I and Wiwit even didn't read the problem and we didn't know what Radit coded. He finished in 14 minutes, pretty quick. We got Accepted at minute 125.

D. Make a Forest

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.

B. Travelling Businessmen Problem

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.

G. National Disaster: Two Towers

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.

H. ANTS

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.

I. XEN 3166

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

We love balloons. Surely.

Closing Ceremony

There was a resolver. Every pending submission in freeze time will be revealed one by one. It can be seen here, the most thrilling part starts from 1:24.

Anyway, here is the final results:
#1: DomiNUS – National University of Singapore, solved 9
#2: PECaveros – National Taiwan University, solved 8
#3: Ainge ST – Institut Teknologi Bandung, solved 7
#4: Caladbolg – Shanghai Jiao Tong University, solved 7
#5: 3body – National University of Singapore, solved 7

Final scoreboard can be seen here.
https://competition.binus.ac.id/icpc2017/final.html

We got 3rd place and the Best National award. It was the best result we got in regional contest. As prizes, each of us got gaming keyboard, gaming headphone, 1 TB external hard disc, and two running watches. Thanks to the generous ICPC Jakarta Regional committee.

World Final Slots

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

Pencerahan