post

ACM-ICPC Asia Phuket Regional Contest 2013

Teams from UI (photo by Denny)

Teams from UI (photo by Denny)

This is my last ICPC regional contest in my life as a contestant, since this is my second ICPC regional contest in 2013 (after Jakarta site) and since I am in my final year in college (hopefully). I had competed in 6 regional contests before. As this is my last chance, I gave my best effort for this contest. I practiced a lot before departing to Phuket, mostly learning new data structures.  I really hoped that I would obtain the best result in Phuket.

On the last days before going to Phuket, I successfully learned and implemented a rare data structure called Heavy-Light Decomposition on trees. The information on this can be found here.

There were 3 teams from University of Indonesia that participated: +1 2.0, Sepiring Lhompat 2.0, and Algorythmists. These teams were chosen because we were in the top 4 (from UI) of ACM-ICPC Indonesia National Contest 2013, the qualification round for Indonesian teams for Jakarta site. Our coach rearranged the teams composition,  then sent 3 teams to Phuket site and 1 team to Danang site (Sepiring Ber2.0).

Team

My team is +1 2.0, coached by Denny with the following members:

  • Alham Fikri Aji
  • Ashar Fuadi (me)
  • William Gozali

Contest

The contest was so intense. The problemset can be downloaded here. Here is the story…

We used a rather standard strategy. First, each of us looked for the easiest problem, and it seemed to be problem J – Minimal Subarray Length. The problem statement is literally like this: You are given an integer sequence of length N and another value X. You have to find a contiguous  subsequence of the given sequence such that the sum is greater or equal to X. And you have to find that segment with minimal length. This seemed to be a straightforward sliding window problem. I quickly coded it, tested with the samples, and realized that it couldn’t be solved this way because the elements of the sequence could be negative. This is one nice example of why examining the constraints is really important. We decided to postpone this problem.

The next easy problem we found was problem I – Cabin Baggage, and it seemed that it was really the easiest problem. It is a simple problem: Given N boxes with the dimensions and weights, and a predicate, for each box determine if it satisfies the predicate. Then Gozali implemented it. At first the solution didn’t work with the sample cases because he had some errors in writing the “if” predicate so I had to assist him. Finally we got Accepted at minute 14.

Next, I read problem G – Meeting Room Arrangement. It is a straightforward activity selection problem. The constraint is a bit misleading: the number of events is up to 20, but the number of test cases is up to 100. This made me spend some time thinking of possible simple exponential solution. However, I decided to code the usual greedy algorithm, and got Accepted at minute 23.

Then, Gozali thought that he had an O(N log^2 N) for problem J. While Gozali was finalizing his algorithm, Aji worked on problem C – Counting Lattice Squares. The problem asks for the number of lattice squares in an M x N grid that have odd area. Gozali and I had not EVEN thought about the solution at all when Aji began working on it. Aji got it Accepted at minute 51, being the third fastest team to solve this problem, thanks to his specialization on solving problem about “patterns”. He then only gave this hint: If S is an odd integer, then all lattice squares whose corners lie on the sides of an S x S square will have odd area (there will be exactly S  such squares).

Aji and I then tried thinking the solution for problem E – Airport Sort together. Abridged problem statement: There is a permutation of the first N natural number. Numbers 1..K belong to zone 1, (K+1)..(2K+1) belong to zone 2, and so on.  You want to rearrange the numbers in such a way that the first K numbers belong to zone 1, the next K numbers belong to zone 2, and so on. There are 2 options. Option 1: in one second, swap two numbers in adjacent positions. Option 2: simultaneously, a number can be moved from position x to position y, in |x-y| seconds. Calculate the difference of time required to rearrange using both options.

After a while, we came up with a very critical observation: the actual numbers are not important; for each position, we only have to care of the zone of the number in that position. So, we can replace each number in the original permutation with its zone number. Then, the time required for option 1 is actually the number of inversions, which can be computed using BIT (Binary Indexed Tree) or merge sort. We used BIT because it is much simpler to code. For option 2, we can use greedy: the leftmost position of zone 1 is moved to position 1, the second leftmost position of zone 1 is moved to position 2, …, the leftmost position of zone 2 is moved to position K+1, …, and so on. We got Accepted at 01:27.

So far, at this point we had 4 solved problems. Gozali took over the computer to implement his solution for problem J. He submitted twice, but unfortunately they were all Time Limit Exceeded. It seemed that his solution has too large complexity. We then re-thought of the solution. Finally I came up with an O(N log N) solution, as follows. Let S[i] be the i-th number (1-based) in the sequence. Let sum[i] be S[1] + S[2] + … + S[i].  Then, iterate for i from 1 to N. For each i, we actually want to find the largest j ≤ i such that (sum[i] – sum[j]) ≥ X, and then report the smallest i – j.

This can be done roughly as follows. We have N+1 values V = {0, sum[1], sum[2], …, sum[N]}. Sort, remove duplicates, and compress these values such that for each value x we know its (unique) rank among these values; call it rank(x). We maintain an array maxPos, such that maxPos[r] = maximum i such that rank(sum[i]) = r.

We start with maxPos[rank(0)] = 0. Iterate for i from 1 to N. For each i, let x = sum[i]. We need to find the largest y in V such that x – y ≥ X (can be done using binary search). Then, the largest j is equal to the maximum value of {maxPos[rank(y)], maxPos[rank(y)+1], …}. After that, we update maxPos[x] = i. Finding the maximum value can be done in log N if we build maxPos using BIT. We submitted it, and got Accepted at 2:22.

Aji then had some idea for problem B – Teaching Hazard. It is actually very similar to this problem; the difference is that the base can be a composite number. Then, he submitted and got Wrong Answer. Apparently his lemma was wrong.

Then, I worked on problem A – Spanning Trees in a Secure Lock Pattern. Ultimately, it asks for the determinant of an N x N matrix, with N up to 36. I was very lucky because I had matrix operations code in our cheatsheet, and this ICPC was the first time ever in which I actually refer to the matrix operations code. So I just literally read the input, converted it into the required matrix (with simple ifs), retyped the determinant code as is, tested on the samples, passed, submitted, and got Accepted on the first try, at 3:12.

Now we had 6 problems solved and less than 2 hours remaining. At this point, there were 2 teams that solved 7 problems. We planned to solve 8 problems. Here was our strategy: none of the teams solved problems H and K, so we thought it’s better to just skip these problems. Problem D was actually solvable and some teams had solved it already, but would require very long implementation and very high accuracy. For problem F, some teams also had solved it, but we hadn’t come up with any solution yet. But, it is clearly about DP, and somehow Aji and I were confident that eventually we could solve it.

So, Gozali then finalized the solution and began implementing problem D – Seven Segment Display. In a nutshell, you are given a graph, determine whether it is isomorphic to the 7-segment display representation of each of digits 0 – 9, where there can be more than one node on the 7-segment edges. We can simplify many things here. For example, if a graph is isomorphic with digit 6, then it is also isomorphic with digit 9, etc.

Meanwhile, Aji and I tried very hard to solve F – Boxes. Eventually we thought that we had a working solution, but Gozali had not finished yet. It was too risky. So, we decided that we will wait until Gozali finished implementing D. 15 minutes before contest ended, he finished and submitted. Unfortunately we got WA; quite expected, since there were so many cases to consider. Then, he printed the source code and debugged it, while Aji and I took over the computer and frantically coded our solution for F. Gozali interrupted us two times to fix small bugs and resubmitted, but still WA. Finally we thought we had a working solution for F, but it didn’t pass the sample cases. When there was only 6 minutes left, Gozali tried for the 4th time, submitted, and got Accepted!! (4:54) The code was over 400 lines, and Gozali said this is the longest code he has ever written for a single problem.

We solved 7 problems! We literally hugged each other after solving D. With 6 minutes left on the clock, we postponed our excitement and tried to debug F until the last minutes. We were sure that our approach is correct, but we couldn’t find the mistake. Unfortunately until contest ended we did not solve it.

After contest ended, we discussed our approach for problem F with ThanQ team who solved it in-contest. Our approaches were similar. May be we were just unlucky and couldn’t think calmly under the pressure of little remaining time.

Closing Ceremony

This was the best ICPC closing ceremony I ever had. We gathered in a large hall, with many big round tables and nice dinner. The performances were also nice.

Anyway, here is the final result:

#1: Armageddon – Peking University, solved 9
#2: Long Time No See – Shanghai Jiao Tong University, solved 9
#3: bcw3Dno7122 – National Taiwan University, solved 9
#4: Nemesis – Shanghai Jiao Tong University, solved 8
#5: ThanQ – National University of Singapore, solved 8
#6: +1 2.0 – University of Indonesia, solved 7

We got the 6th place, bronze medal, and prize of 10,000 bahts. We thought that we failed to grab a WF spot this time as well. But then we realized that #1, #2, and #4 are Chinese teams, which should be excluded from the ranking (via Asia rule), while #3 should get a WF performance slot because National Taiwan University were in the top 10 of WF 2013. After discussing with Steven Halim, NUS coach, we should be #2 in the official ranking after ThanQ, and should get a WF slot!

+1 2.0 won bronze medal (photo by Denny)

+1 2.0 won bronze medal (photo by Denny)


Excursion

Due to unavailability of direct flight on certain days, we extended our travel. So, we have two days full for exploring Phuket, plus the  official excursion provided by the organizers.

On the official excursion, we went to Patong Beach. We took a nice photo with some of the escorts and other contestants:

Patong Beach (photo by Fredric Sanjaya)

Patong Beach (photo by Fredric Sanjaya)

On our own excursion, we went on a Phuket tour. This tour was actually delayed one day due to bad weather. We visited small islands, did kayaking, had good lunch on board, etc.

Phuket Tour ship (photo by Denny)

phuketexcursion2

James Bond Island (photo by Denny)

 

 

 

 

 

 

World Finals Slot

Although my team should almost surely qualify to WF, we are not 100% sure until the official announcement is published. Asia WF rule changes from year to year, so it’s better to wait until C. J. Hwang (Asia director) announce the slot allocation in his blog. I checked the schedule and found out that the last Asia regional contest is Tehran contest on 20 December 2013. So, after that date, I checked his blog literally every day, waiting for the announcement to show up. Finally, on 2 January 2014, the post was published. We really advanced to WF 2014 as expected! This is the first time for University of Indonesia to qualify to ACM-ICPC World Finals.

I would like to thank Felix Halim for his wish on my Competitive Programming 3 book beside his signature. It really comes true.

The note means "Wish you go to WF 2014"

The note means “Wish you advance to WF 2014!”

So, I still have to train myself harder, (at least) until the 2014 ACM-ICPC World Finals in Ekaterinburg, Russia 🙂

About Ashar Fuadi

Ashar Fuadi is a competitive programmer from University of Indonesia. He loves to code, especially for TopCoder SRM, Codeforces, and ICPC.
Follow Ashar on Google+ and Twitter.

Comments

  1. So happy to read your story 🙂 I hope this won’t be a one-off legacy, and there are more to come after you guys graduate 🙂

  2. congratulations! nice to hear that 😀

    hope it will happen in my college time soon 🙂

  3. Hierony says:

    My spirit arise man!.

  4. Please give a solution of problem D 2013 “Factors”

Trackbacks

  1. […] 2014, pertama kalinya dalam sejarah UI lolos ke WF! Blog post tentang ICPC Phuket & Da Nang: (post Ashar, post […]

Speak Your Mind

*