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**).

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

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

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.

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!

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:

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.

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.

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

Indeed, I was more than happy because I managed to grab a T-shirt, in a dramatic way! Here is the story:

– The SRM started at 00:00 in my local time. I set my alarm at around 23:30, and I woke up on time.

– I tried launching the Arena. It didn’t work! I indeed had some problems with the Arena and I think I had solved it, so I was so confused. Desperately, I tried opening the JavaWS cache viewer and the JNLP file and then comparing them. The arena-client-7.0.8.jar file was missing from the cache, so I tried manually downloading it via wget. It turned out that using my connection (Android portable hotspot), that file couldn’t be downloaded completely; I also didn’t know why. So I used wget several times using -c flag until it was downloaded completely. Then, I modified the JNLP file to point to the downloaded arena-client-7.0.8.jar. Here is an interesting point: I didn’t know how I got the inspiration to do those things! They suddenly popped up in my mind. Maybe it was due to the fear of missing SRM 600?

– I was 10 minutes late in the coding phase. I opened 250, and then solved it 8 minutes. Couldn’t find any tricky cases, so I was pretty confident.

– Then I opened 600. We want to have at least R palindrome rows and at least C palindrome columns. Well, there are 2 conditions. To simplify things, why don’t we do brute-force on one condition? So, my solution is to choose which (at least C) columns we want to be palindrome using brute-force, and then compute the minimum cost to have at least R palindrome rows using dynamic programming. On the first compile, my code failed due to a missing ‘]’ character. On the second compile, my code compiled successfully, and **passed all examples on the first try**! I submitted it in 44 minutes.

– Coding phase was over. In challenge phase, I couldn’t find any interesting solutions. In the end, I ranked 72nd if I recalled correctly.

– System tests! I really hoped that I made it to the top 60. After systests, I passed both problems and my final rank was **61st**! Off by one! I was so sad. I hope at least one person above me cheated so that my rank would go up to the top 60.

– Soon, there was a message telling that the 60 random participants had been selected and posted in the forum. I rushed and clicked the forum link provided in the message. But the forum was so slow and I couldn’t open it. I was so nervous!

– I gave up and intended to open it later. But then someone in the Arena told me that I was selected as one of the random 60 participants. Yay! I managed to get a T-shirt!

– Several days later, the admins announced the final results. Indeed there was one coder in the top 60 that cheated. So, my official rank is actually 60th. In other words, I got T-shirt from both slots As expected, they removed me from the random slot and assigned another lucky participant.

—

So that’s the story of me winning a(nother) T-shirt from TopCoder. It was also my first time to solve a 600-pointer problem, although I’m not sure whether it is assigned 600 because of the difficulty or because it is SRM 600. But I don’t care it anyway.

]]>In GCJ, you have to download the input files and solve them quickly. It is a great time saver if the input files are downloaded right to your working directory after you click “Solve X-Small” / “Solve X-Large”.

You can change the location in your browser setting. For example, in Chrome:

It is **very important** to check the integrity your output files before submitting them. The fact that your solution passes the example cases does not mean that your solution will pass the official input files easily. For example, if you find that your output file contain negative numbers, whereas the answer is supposed to be non-negative, then it means you have overflow error somewhere in your solution.

However, checking the output file by opening it manually can be rather time-consuming. You can use tee to automatically check it. tee is a UNIX command that writes to a file and the standard output simultaneously. The basic usage is

./solution < input_file | tee output_file

The above command will run your solution using input from input_file, and output the answer to both output_file and the standard output (the screen). Furthermore, if you **flush** the output after printing the answer of each test case, this will work in real-time; i.e., as soon as your solution finishes solving a test case, the answer will be immediately displayed to the screen. This way you can estimate how long your solution will finish solving all test cases in your machine. In addition, as soon as your solution output strange answer, you can immediately stop the execution of your program and debug it.

This is different from the traditional way. You have to wait until your solution solves all test cases before you can check the sanity your output file.

tee only works in UNIX. For Windows users, try using wintee (I haven’t tested it, though).

**Edit**: Felix Halim pointed out that non-UNIX users can simulate tee’s behavior by printing the answer twice: to the output file and to the standard error as well, like this:

cout << "Case #" << tc << ": " << res << endl; cerr << "Case #" << tc << ": " << res << endl;

This works well because the test case output in GCJ is usually small (like a single integer), so you only have to copy one single printing statement.

You only have 4 minutes for the small input and 8 minutes for the large input. Time is very precious in GCJ, so I like to automate everything. I wrote a small C++ program to automate the process of running my solution on the correct input files and producing output files. Here are the source code if you are interested.

**Edit**: Because GCJ now supports more than one type of large input files for each problem, I have modified the source code a bit.

#include #include #include char buf[1024]; int fail() { printf("Usage: gcj <problem> (small [<attempt>] | large [<type>])\n"); printf("Examples:\n"); printf(" gcj A small\n"); printf(" gcj A small 1\n"); printf(" gcj B large\n"); printf(" gcj C large 1\n"); return 0; } int main(int argc, char* argv[]) { if (argc >= 3 && !strcmp(argv[2], "small")) { int attempt = 0; if (argc == 4) sscanf(argv[3], "%d", &attempt); else if (argc > 4) return fail(); sprintf(buf, "./%s < %s-small-attempt%d.in | tee %s-small-attempt%d.out", argv[1], argv[1], attempt, argv[1], attempt); system(buf); } else if (argc >= 3 && !strcmp(argv[2], "large")) { if (argc == 3) sprintf(buf, "./%s < %s-large.in | tee %s-large.out", argv[1], argv[1], argv[1]); else if (argc == 4) sprintf(buf, "./%s < %s-large-%s.in | tee %s-large-%s.out", argv[1], argv[1], argv[3], argv[1], argv[3]); else return fail(); system(buf); } else return fail(); }

So, for example, here is how I work on problem A:

- Write the solution as A.cpp.
- Build it into A.
- Download the small input file.
- Run “gcj A small” and watch the tee output.
- Submit the output file and source code.

For more advanced automation, you can use codejam-commandline beta tool developed by Googlers. However, I find the above tips are sufficient for me.

For C++ users, you don’t have to worry again if the problem requires you to work in arbitrary-precision integer data type (a.k.a. bignum or big integer). You can use the **GMP** library as it is free and publicly available. You don’t have to switch to Python/Java in contest now! For more reference, you can consult vexorian’s blog post: http://vexorian.blogspot.com/2010/05/google-code-jam-qualification-rounds.html.

One of the downside of GCJ is that you cannot have too many friends to watch on the friends scoreboard. Usually, you want to watch the performance of coders in your country. You can use a nice tool developed by Ahmed Aly: Google Code Jam Tools. It can show the results of previous contests for any country.

Any other tips? Please share

]]>This year, I became the person-in-charge of Programming Competition of Computer Festival 2012. The competition was a standard ICPC-like programming competition. There were two categories: college and high school. The online qualification rounds were held in 8-9 September 2012, while the final rounds were held in 13-14 October 2012.

It was an exciting and tiring experience managing this national programming competition. We had to prepare the registration system, generate ideas for problems, create and polish problem statements, generate test cases, prepare teams accommodation, and many more. I was lucky to have 8 strong and hard-working staffs: Gozali, Febry, Berty, Guspra, Nira, Ara, Faris, Fariz. Thanks a lot!

Here are the final round problems. Note that the problem statements are in Indonesian only.

Special thanks to our problem setter besides the staff: traveloka.com (**Derianto Kusuma**), and our tester: **Risan**.

The problems for the high school category were surprisingly quite easy for some of the contestants. The first ranked contestant solved all problems in about 3.5 hours; however, he was the only contestant to solve all problems.

On the other hands, the problems for college category were quite hard. No teams solved all problems during the contest.

Congratulations to the winners!

**College**

**1st**Rank: Team**<3**from University of Indonesia**2nd**Rank: Team**Pandawa**from BINUS University**3rd**Rank: Team**IsengBangetParah**from Institut Teknologi Bandung

**1st**Rank:**Nathan Azaria**, SMAN 2 Purwokerto**2nd**Rank:**Jonathan Irvin Gunawan**, SMAK 1 BPK Penabur Bandung**3rd**Rank:**Cakra Wishnu Wardhana**, SMAN 8 Yogyakarta

Here are some photos, from preparation, contest days, and closing.

*… so I would like to suggest you to write Div-2 part of Member SRM 489. If you agree,* …

*Thanks,*

* Ivan*

That was my first approval statement from **mystic_tc **(Ivan) for writing an SRM. Yay! I received that email after I proposed a problemset for a Member SRM. Ivan posted a “Looking for Member SRM 489 writers” thread in the forum, then I tried to propose, and I was glad that the proposal was approved. I was really really happy that time.

For those who don’t know, Member SRM is actually a regular SRM whose writers and testers are not paid. It is voluntary for keeping 3 SRM per month. That was OK for me as what I want was the experience of working together with the admins to prepare an SRM.

I actually proposed a complete set of five problems, but it turned out that the Div-1 problems did not satisfy Ivan. Yes, when I read the problems now, I realized that they are very lame problems. Therefore, Ivan assigned me to write only the Div-2 part. The Div-1 problems were written by **rng_58**.

After being assigned as a writer, I had to sign an agreement document and sent it to Glastonburry (Indonesia – USA, incurring an expensive JNE fee :(). And then I logged in to a Java applet called **MPSQAS** (Member Problem Submission Quality Assurance System). This is where the complete problem statements, solutions, and test cases are uploaded to. Only approved writers can create problems there, obviously. To be approved, you must apply for a writer there (I did that after I proposed the problemset).

For Member SRM 489, Ivan also assigned two testers, **vexorian** and **liympanda**, also a language checker, **eleusive**. Overall, testers are responsible to submit their solutions to all problems and give feedbacks about the difficulties of the problems. The language checker is responsible to check the spelling and grammar of all statements, since most of the time the writers are not native in English. He/she also usually gives suggestions about the background stories of the problems.

While the writer writes the statements, testers will give feedbacks as a correspondence — every single feedback will be recorded in MPSQAS and emailed to all writers and testers. So, the problem creation lifecycle typically consists of writing statements, receiving feedbacks, update statements, receiving feedbacks, and so on until we are all satisfied and agree with the final statements.

My problems for this SRM were:

- D2-250: BadVocabulary
- D2-500: Buying Flowers
- D2-1000: SolitaireChess

The point distribution of the problems are also discussed, moderated by Ivan, usually when the problem statements have been finalized. In this SRM, the distribution was normal, 250-500-1000 in both divisions. Quite often the distribution varies if one or more problems have more/less difficulties than usual. The easy problem is usually worth 250, 275, or 300 points; the medium 450, 500, 525, 550, or 600 points; the hard 900, 925, 950, 1000, 1050, or 1100 (very hard!) points.

After spending a lot of efforts on polishing the problems, then the match started. Writers and testers are given special accounts, **writer**, **writer2**, **tester**, and **tester2**. We can log in to the Arena as admins! With these orange handles, writers, testers, and admins:

- are in ninja mode: we can read all whispers!
- can read the coders’ solutions in coding phase.
- are responsible to answer clarifications regarding the statements/constraints, usually giving “please reread statement” answers.
- usually bet on the approximate number of solvers of each problem.
- have fun watching the division summary. Yes, it is always fun to watch people solving our problems!

The sad part was that until the match was over, nobody solved my D2-1000 actually it was to be solved using a “classic” dynamic programming.

Several months later, I got an interesting problem idea which I thought would fit for a D1-Hard (PickAndDelete problem). I came up with a D2-Hard not long after that (after inventing a D1-Hard, it seems easy to come up with the rest!) and the other three problems before them, and then proposed the problemset to Ivan. Luckily, Ivan approved my entire problems and even invented a better solution for D1-Hard (N^3 –> N^2 lg N). **Chmel_Tolstiy **was assigned as the tester.

The points distribution for this match was unusual, 256-512-1024 for both divisions. This was Ivan’s cool idea as it was SRM numbered 512, so all problems had points that were powers of two. I think this was the first time that the point of each problem is not divisible by 25.

It turned out that there were 11 coders that solved the D1-Hard and nobody used Ivan’s faster and smarter approach. Oh, I admit that his solution is so smart that I believe I could not come up with that idea at all! That showed the true power of an SRM admin

After the match was over, Ivan asked me whether I was going to write the editorial. I accepted that request and carefully wrote my first SRM editorial, although a bit risky because it was my first time to write. Surprisingly, it seemed that many coders liked my editorial and eventually it got **+39/-0** reputation.

This was my first paid SRM. I earned **$525** for the problemset (five problems) and **$75** for the editorial. A very good payment!

So this was my third SRM. I created the problemset with a nice theme, i.e., the SRM itself (what a recursive contest!). The problems were:

- D2-250: SRMRoomAssignmentPhase
- D2-500/D1-250: SRMCodingPhase
- D2-1000: SRMSystemTestPhase
- D1-500: SRMIntermissionPhase
- D1-1000: SRMChallengePhase

See, the problem names are the phases in a usual SRM

This was the first SRM **[[rng_58]]** (Makoto) moderate as the new algorithm coordinator, after successfully winning TCO 2010 and TCO 2012. This was the first match after TCO 2012 finals. In this match, Makoto the new admin invented a better solution for D1-1000 and thus we raised the constraint from 50 to 2500! Like I said, SRM admin is unbeliavebly smart, whoever he is.

Mr. Dengklek, the main character, first appeared in this SRM (and then always appeared in my subsequent SRMs). He is the main character of Indonesia’s national olympiad in informatics, for those who don’t know.

I also wrote the editorial for this match. People seemed to like this editorial too, and it got **+37/-1** reputation.

Before I competed in ACM-ICPC Asia Manila Regionals 2011, I proposed another problemset to Makoto. He accepted all problems except the D1-Hard. However, he assigned me to a match and asked me to improve the current D1-Hard or to come up with another problem.

The match would start right after I came back to Indonesia from Manila. It turned out that Makoto also competed in the same regionals. And (intermezzo) guess what, his team won the regionals, obviously!

Almost every night in Manila we discussed about the D1-Hard via chatting. Since I could not invent a good Hard for days and the match day was approaching, Makoto proposed to use his own problem, DengklekMessage (previously named FaxCiel and CielMessage). He said the problem was invented by Ivan and him together. I accepted the proposal. Makoto then asked to be a tester for the problem; I also accepted that although I was not fully confident.

One day before the contest started, I solved the hard with a simple matrix exponentiation algorithm. Makoto then said that the solution was quite trivial and he had to rewrite the problem, the statement, solution, and test cases. The current version is harder and I could not solve it before the match.

I didn’t write the editorial this time as I had so many college assignments. It was **vexorian **who was finally assigned to write the editorial.

Yet another SRM written by me. Not much to say.

For this match I created a turned-out-to-be-very-tricky D1-Easy (DengklekMakingChains). It was so tricky that during testing, Makoto counted that:

- my solution failed
**twice**, - Makoto’s solution failed
**twice**, and - Ivan’s solution failed
**once**. (he won! :p)

As all testers wrote wrong solutions for this problem, it was assigned 300 points. However, even after adding very strong examples cases, so many people still got challenged and failed the problem. Makoto even said that this problem could be a 500-pointer with arbitrary length of chains and very weak example cases.

This one was quite an unexpected SRM for me.

Once I proposed a complete problemset to Makoto, and (again) he approved all except the D1-Hard. Then I had a quick chat with **dolphinigle** asking whether he had a free D1-Hard problem, and he said he had free D1-Hard and D2-Hard problems. We agreed to make a collaborative SRM. We then tried to contacted Makoto, and he immediately approved our idea and assigned us to this match.

I heard that problem writers are rare lately; that might be why he approved to create an SRM with two writers.

Anyway, we had to agree with a common theme for the problems. I suggested the Kingdom of Ducks background story as usual, and he suggested to use <Theme>X<Name> format for the problem names. Therefore, we agreed KingX<name> for my problems and PrinceX<name> for his problems, featuring King Dengklek and Prince Gogo. A good fusion, eh?

Random thought: I still liked the example cases in my D2-Easy problem — it consists of all people preparing this match: “dolphinigle”, “gofushar”, “rngringo”, “mystictc”, “misof”, “metelsky”, and of course, “dengklek”

—

Phew, that was quite long story. To sum up, I have been a writer/one of the writers of six SRMs up to now, and I am very happy. Problem setting at TopCoder is an interesting experience! (And of course it generates revenue :P)

I hear that nowadays writers are not as many as they were before. If you want to try to write problems for SRM, please read the Write Problems for TopCoder page.

]]>The contest had three types of problems: algorithmic, company, and real-world problems. The algorithmic ones are much like usual competitive programming problems. Company problems are set by some of the companies. Real-world problems are “real”, for example, one of them is creating a web service for resizing company logos.

During the 48-hour contest (yes, only 2 days), I managed to solve 6 algorithmic problems and 1 company problem. I ranked #38 overall and #2 in Indonesia (the first rank went to **dolphinigle**).

Here is an analysis on some of the problems.

**Coin Tosses** (Accepted, 20/20 points)

I first tried solving this problem by transforming it into system of linear equations.

Assume that N = 3. Let f(x) be the expected number of tosses needed to make 3 consecutive heads, given that we have already x consecutive heads. Of course, the range of x is 0 <= x <= 3.

Now, let’s evaluate f(x). It is clear that f(3) = 0 (no additional tosses needed); this is the base case.

For 0 <= x < 3, there are two possibilities:

- The next toss results in head. We have x+1 consecutive heads now, so the expected number of tosses is 1 + f(x+1).
- The next toss results in tail. We don’t have any consecutive heads now, so the expected number of tosses is 1 + f(0).

Both cases happen with probability 1/2. Therefore, the formula for f(x), 0 <= x < 3, is:

or, more simply,

The complete formulas for N = 3 would be:

One may be tempted to solve the function using dynamic programming, but that does not work as the formulas are cyclic. For example, f(0) depends on f(1) but f(1) also depends on f(0).

Now, take a look at the equations once more. Actually it has been implicitly solved. We can work backward (back-substitution) like this:

So,

Having computed the values of f(3) and f(0), we can use them compute the value of f(2), and then f(1). We have solved the equations! This solution clearly runs in O(N) time complexity. We can precompute the results for all N and stores them in a 1000 x 1000 table. The total complexity is O(N^2 + T).

But there is a problem with this solution. Simply running this solution with large N and small M will generate a very large output that overflows double data type. Replacing double with, say, BigInteger, would probably result in TLE. So, I tried printing the results for small N and M, and then tried looking for pattern. The pattern was amazingly obvious. It turned out that the answer for this problem is simply .

This new solution can be coded in Java/Python with their built-in big integer data type, and would run fast enough for 100 test cases.

**Permutation** (Accepted, 14.67/25 points)

This problem is essentially an approximation to the Traveling Salesperson Problem. Just assume that the numbers are cities, and V[i][j] is the cost of going from city i to city j. A permutation of the numbers means a path that visits all cities exactly once.

The method I used was splitting the cities into blocks of 15 cities each (or may be less than 15 for the last block). Then, for each block, I did a DP with bitmask to get a Hamiltonian path considering only cities in that block, with the maximum cost.

The DP I used is two-dimensional: dp[u][mask] is the maximum cost of visiting all cities not contained in mask, given that the last visited city is u. The set mask is represented with a bitmask of n bits, where n is the number of cities in the block (15 or less).

So, the base case is

, for all u (we have visited all cities).

The recurrence is determined by choosing the next city v to visit, after visiting city u:

, for all v not in mask.

The maximum cost of a Hamiltonian path in this block is simply by choosing a starting city that leads to the maximum cost:

, for all u

The Hamiltonian paths for the other blocks are computed in the similar way, except that the starting city of a block must be the last city of the previous block.

**Count Strings** (Accepted, 50/50 points)

This was the hardest problem I solved in the contest. I had to learn regex parsing and converting it into finite automata, during the 48-hour contest.

First, I converted the input string into an NFA (Non-deterministic Finite Automata), and then transformed it into DFA (Deterministic Finite Automata). There is a nice tutorial and explanation on how to parse a regex into an NFA and then into DFA here.

To make it simple, a DFA is a directed graph, whose vertices are “states”, and edges are “transitions” between the states. The edges are labeled by ‘a’ or ‘b’. One vertex is marked as “starting” state and several vertices are marked as “finishing” state. A string of ‘a’ and ‘b’ is like a path in the DFA from the starting vertex. If the path ends in one of the finishing vertices, then the DFA is said to “match” or to “accept” the string.

For example, the input **((a|b)(a*)) 5** can be parsed into this DFA:

--a-->[1]--a / | ----+ | v / | [O]--+ [3]*--a--> | ^ \ | --b-->[2]--a

The starting vertex is vertex 0, while the finishing vertices are vertices 1, 2, and 3. Any string that leads to a path from vertex 0 to any of the vertices 1, 2, and 3 is accepted by the regex (try it with several such strings). Now, the problem is to count the number of strings which lead to paths of length 5 starting from vertex 0 that end in vertex 1, 2, or 3.

Let’s build the adjacency matrix of the above graph:

It is well-known that is actually the number of paths from i to j of length 1. More generally, is the number of paths from i to j of length n. Therefore, here are the steps to solve this problem:

- Construct a DFA from the input regex.
- Build M, the adjacency matrix of the resulting DFA.
- Raise M to the L-th power, using exponentiation by squaring.
- Sum all , where x is the starting vertex and y is a finishing vertex, for all y.

The hardest part is actually constructing the DFA. It took me several hours straight to learn the construct it from the above link.

**Picking Cards** (Accepted, 20/20 points)

First, sort the input in ascending order. For example, let the sorted input be 0, 0, 1, 1, 4. Consider the cards one-by-one. For each card, we will count how many ways to pick up to that card.

- The first card has c = 0. Because we haven’t picked any cards yet, it can be picked. There are only 1 way: {1}.
- The second card has c = 0. The smallest valid position for this card is the first position. So, there are 2 ways: {2, x}, {1, x}.
- The third card has c = 1. The smallest valid position for this card is the second position. So, there are 2 ways: {x, 3, x}, {x, x, 3}.
- The fourth card has c = 1. The smallest valid position for this card is the second position. So, there are 3 ways: {x, 4, x, x}, {x, x, 4, x}, {x, x, x, 4}.
- The last card has c = 4. The smallest valid position for this card is the fifth position. So, there are 1 way: {x, x, x, x, 5}.

In each step, the ‘x’s can be replaced with any valid sequence from the previous step. Therefore, the total number of ways is 1 x 2 x 2 x 3 x 1 = 12.

The smallest valid position for the -th card (1-indexed) is . The total number of valid positions for that card is then (or 0, if ). Therefore, the total number of ways is:

**Subsequence Weighting **(Accepted, 30/30 points)

Let’s try solving it with a simple dynamic programming solution. Let be the maximum weight of a subsequence that ends in . The recurrence would be

, where and .

Note that if we fill the dp table in ascending order of , and in decreasing order of for the same values of , and set the unfilled entries of the dp table to 0, we can reduce the constraints into the above dp into:

, where .

The value of “, where ” can be computed efficiently in O(log N) time complexity using a binary indexed tree. The solution to the original problem is then for all i. So, the total time complexity of this solution is O(N log N).

**Direct Connections **(Accepted, 35/35 points)

The problem essentially asks for the sum of cable length for each pair of cities, where the cable length for a pair of city i and city j is .

Consider the cities in ascending order of . Now, the equation turns into the sum of , for all i and for all previous cities j of i. Moreover, the absolute sign can be removed by transforming the equation into the sum of , for all i and for all previous cities to the left of city i, plus , for all i and for all previous cities to the right of city i.

Let’s solve for the sum of (the right one can be solved in similar way). If there are previous cities to the left of city , the equation becomes .

Hence, for each city (again, considered in ascending order of ), we need to know two pieces of information:

- The number of previous cities to the left of it ()
- The sum of positions of all previous cities to the left of it (

These two values can be computed using (again) two binary indexed trees in O(log N) each. One BIT stores the number of cities to the left of a certain position, and the other BIT stores the sum of positions of all cities to the left of a certain position. By position I meant the “rank” of a city when the cities are sorted in ascending order of .

**Polygon** (Not Attempted, 0/40 points)

**dolphinigle** posted his solution in a TopCoder forum thread.

**Crab Graphs** (Not Attempted, 0/40 points)

I honestly had no idea on this problem. Several guys discussed this problem on the same thread as Polygon; please check that.

**Quora Nearby **(Accepted, 40/40 points)

At first I thought this problem must be solved using some sophisticated Kd-tree data structure, with some kind of nearest-neighbor search algorithm. But, when I decided to try a simple naive search (O(N) for topics and O(N^2) for questions), I got accepted!

**Fraud Prevention **(Wrong Answer, 15/30 points)

I submitted like 20+ solutions for this problem, but I couldn’t pass the last test case. I don’t know, may be I missed something in the problem. What I did is a simple O(N^2) search to look for all pairs of fraudulent orders (it didn’t get TLE, though). For each pair, I checked if they satisfy one of the fraudulent requirement.

===

That’s it. If anyone would add alternate solutions or anything, please add them in the comment section

]]>Honestly, we expected to become a world finalist this year :D. We had participated in nearly all college national programming contests before, and got pretty nice results. Each of us also practiced regularly in online judges, me especially in TopCoder (SRMs). So, we hoped that we got some luck and succeeded this year.

We were assigned a new coach, **Denny**. He participated in an ICPC regional in around 2000’s. My teammates were also the same as the previous year, i.e., **Alham Fikri Aji** and **Berty Tobing**.

The teams were selected by choosing the top 3 teams from my university in Indonesia National Contest. Then, our team was selected to participate in Manila, while the two other teams were selected to compete in Kuala Lumpur.

I told **Ilham Kurnia**, my programming contest trainer, that we were going to take the Manila regional. He immediately warned me that from his previous experience in competing in Manila twice, this site was always badly organized. The problem statements were ambiguous, the clarification was not so helpful, etc. So, he advised us to anticipate for every bad things that might happen during the contest.

We flew to Manila by Philippine Airlines. It took us about 4 hours to arrive in **Ninoy Aquino Airport**. Then, we took a taxi to get to our hotel, The Oracle Hotel in Quezon City. We could communicate with people easily as English is one of the national languages in Philippines, besides Tagalog. We didn’t feel like being abroad so much because the weather, the people faces, the traffic, are very similar to those of Jakarta.

We arrived in Manila one day before the contest days, so we were supposed to take enough rest for the next day. While I was lying in bed, surfing the internet, I accidentally ran into a blog of **Raffy Saldana**, the Manila Regional Contest Director. In his blog, Raffy posted the rules of a team notebook, which are rather hard to prepare (25-page letter-sized notebook, packed in a two-hole binder with 4 dividers, etc.). The annoying thing was, why he didn’t post it in the official Manila regional website.

The official website was way very simple and less informative. Before we departed, it didn’t say anything about the notebook, so we assumed that any simple 25-page notebook will do. After reading the blog post, bought all necessary materials in a bookstore.

The contest was held in **University of Philippines Diliman**. We had the opening ceremony in a large hall inside one of the university building. The opening ceremony was quite usual. We were in the same table with a Chinese team. They provided snacks, ice creams, and even a performance of two jugglers. The jugglers were very entertaining. But later, I found that this performance was the **only** nice thing of the contest!

There were many unusual things that I noticed. The first weird thing was… there were no runners/escorts for foreign teams!

Secondly, the MC for the opening ceremony often talked and joked in Tagalog, so foreign teams had no idea what he was talking about. His voice wasn’t loud enough to hear from the back.

Thirdly, the organizers requested us to fill a (very simple) form asking for our emails and T-shirt sizes. This is weird since this information should have been available in our profiles in ICPC website. I couldn’t understand. They had the team names, but they didn’t have the emails and T-shirt sizes.

After the opening ceremony, they picked us up to another building used for the practice session and of course the contest proper. We moved there by **Jeepney**, a local public transportation in Manila.

We entered our assigned room. The practice session and also the contest was not held in a large hall; just in ordinary classrooms installed with workstations. The bad thing was that each workstation table was too small for three persons and the gap between teams was too narrow. We were afraid that we might accidentally touch or break another team’s workstation.

So, the practice session began. We were given only a single task. The task was simple: You are given several test cases, each containing two nonnegative integers and an arithmetic operator (+, -, /, or *). For each test case, output the result of the expression. If the operation cannot be carried out, output “INVALID”.

The first bad impression was that the problem statement didn’t specify any constraint for the input! When one of the team asked for clarification, the judge said something like “assume a typical range for the constraints”. What? How could we know what the judge meant for “typical range”?

Finally, the judge broadcast additional clarification that the operands will be between -2,000,000,000 and 2,000,000,000. Even the clarified constraint was inconsistent because the statement said “nonnegative integers”. So, the judge corrected his previous clarification and then sent out another clarification that the operands will be between 0 and 2,000,000,000.

The statement also didn’t specify how to do the divide operation: integer division or real division? They had to sent many clarifications to finally make this problem unambiguous.

After we completely understood the problem, we coded the solution. Another unusual thing was that the input must be read from file, not from stdin. We submitted several times to the PC^2 interface. We waited and waited, but none of our submissions was judged until the end of the practice session! When we looked at the other teams’ monitors, it seemed that there were very few of our submissions that got judged. So what’s the point of this practice session? We couldn’t test the time limit, grader’s stack size, etc.

After the practice session was over, we handed in our team notebook. Apparently, they also accept plain team notebooks, i.e., without binder and tab dividers. Okay. They also gave the T-shirts. The T-shirt looked bad; it was only a plain white T-shirt with “ACM-ICPC” printed in it, without naming “Manila”, “2011”, or “University of Philippines”. Some contestants even received T-shirts with wrong sizes because they ran out certain sizes. Some coaches also received T-shirts with different colors. It was ridiculous.

Ah, there was also no excursion.

All teams gathered in front of the contest building on 9:00 AM. Although the contest program (printed in a plain yellow photocopy paper) stated that there should be an assembly meeting on 9:00 AM, no instruction was given to the teams. There were no escorts, so the teams ended up in confusion. So, all teams took initiative to enter their assigned room without instruction.

We sat down in our desk. The contest was planned to begin at 9:30 AM, but they were so slow in distributing the team notebooks so the contest was delayed. The real contest finally began at around 11:00 AM. In our room, the assigned contest proper runners were upset when we told them that the contest had begun (we simply noticed that the timer in PC^2 had started). After we told so, they started distributing the tasks to all teams in rush. In effect, the contest started late in our room for about five minutes.

Another strange thing: no available scoreboard for the contestants! This was my first international programming contest without scoreboard.

There were ten problems in the contest. Almost all problems required very difficult input parsing.

You can download the “underground” version of the problemset here, thanks to a local team who posted it on TopCoder Forum.

**A. Student Life**

A very easy problem, just a simple sorting problem based on several keys. The real challenge lies in parsing the input. The input format is very difficult. Another big challenge is to guess what output format the judge wants (!), because the output format section only says, “For each test case, output the arranged appointments accordingly”. Examining the sample output is not very helpful, as there are still some ambiguities, like whether we should output a blank line between test cases or after each test case, and in which appointments the “(Conflict)” mark should appear.

To resolve those ambiguities, we just gambled! We submitted, and got “Yes” response after like 20 – 30 minutes. The judge was so slow.

**B. Ant Maze**

This is also an easy BFS problem. This problem asks to find a path in a maze from the entry point to the exit point. The problem is that the problem statement doesn’t specify the constraints on R and C, the size of the maze. When a team asked for clarification on this, the judge replied, “assume that R and C fit in 32-bit signed integer representation.” This should be an impossible upper bound; how to store an array of 2 billion x 2 billion characters?

Later, the judge corrected the clarification and said that 1 <= R, C <= 200, a reasonable constraint.

We also got a “Yes” response on this problem.

**C. Gaussian Integers**

A math problem about complex number theory. None of us had learned complex number thoroughly, so we just skipped this problem.

This problem asks for GCD(s) of two complex numbers. Weirdly, the problem doesn’t define explicitly what “greatest common divisor(s)” in complex field is.

**D. Top Rank in Rectangular Array**

This should be a usual simulation problem using priority queue. For each number a in the list, we add to the priority queue a, a/2, a/3, …, until it is less than the requested integer.

We also got a “Yes” response on this problem.

**E. The Chipmunks’ Christmas**

This is a controversial problem. The problem seems to be easy. In a nutshell the problem simply wants us to convert a number into a special number system: 1, 2, 5, 6, 7, 8, 9, 11, 12, 15, …, 21, 22, 25, …, 111, 112, and so on. Since the input N is at most 500,000, we can simulate the number system and store the precomputation in an array. So, for each test case we can simply output the precomputed answer.

We got “No” responses many times in this problem though we were like 99% sure about the correctness of our solution. Later, it turned out that the judge’s solution was wrong!

**F. An Arrangement of Sorts**

The very small constraints of this problem (at most 8 x 8 grid) should be a hint that the problem is to be solved using pruned backtracking. It was indeed the case. We solved this problem using a simple backtracking without any fancy pruning, and it ran fast on several random large input.

We got a “Yes” response on this problem.

**G. What will I Ride?**

We didn’t have enough time to attack this problem, because we spent much time for problem E. Although the problem statement is rather ambiguous (lacks many required definitions), it should be a modified Dijkstra/Floyd Warshall with convex hull. We think we should have solved it if we abandoned problem E.

**H. Balanced String**

Aji solved this problem using dynamic programming. His state was (current string length, current difference of 0s and 1s, minimum difference of 0s and 1s so far, maximum difference of 0s and 1s so far). His solution worked perfectly for sample cases but not for large cases (it overflowed), so I convert his source code to Java to allow using BigInteger class.

We got “Yes” response for this problem.

**I. Multiset**

The most ambiguous problem in the contest. No constraints at all. The input and output format section do not match with the sample input and output. Indeed all sample outputs were wrong! These were caught by some teams during the contest.

**J. Hollow, Non-Hollow**

This problem is also ambiguous. The statement doesn’t define precisely what “empty spaces inside” means, and what “disjoint figures” means. We tried no to assume to much and coded a simple DFS solution, and it got accepted.

We got “Yes” response for this problem.

—

In total, we solved 6 problems in the contest. We thought we could have solved 7 (+ Problem G) if Problem E were fine

The closing ceremony was held outside the campus canteen. It was really a very simple closing! No stages, no performances, no MCs. That was a shame for an international contest. They provided late lunch dishes, but some teams (us too) sat down in the floor because they ran out of tables.

So, the winners of the contest are:

#1. **STAFF** (University of Tokyo, Japan) (**rng_58**‘s team)

#2. **Quiwarriors3** (University of the Philippines Diliman)

#3. **~~(Q_Q)~~** (National Taiwan University, Taiwan)

After the closing, we discussed with other teams about the controversial Problem E. It seemed that the problem indeed suspicious. Even the winner couldn’t solve it in-contest.

Our coach and several other teams sent an appeal email to the **Marsha Poucher** and **Raffy Saldana** regarding Problem E. We asked for rejudge for the problem.

Several days later, the official Manila Regional website posted the updated ranking. We Saklar Lhompat finally ranked 4th, solving 7 problems! But we lost to a local team, so the chance of advancing would be too small.

Despite getting increase in ranking, we thought that the rejudge is unfair, because they rejudged *all* submissions, including the submissions that got accepted during the contest. So, some teams got decrease in number of solved problems.

One day after the contest, University of Philippines Diliman teams invited Indonesian and Japanese teams to a small private “excursion” around the Manila city. **Eric Tambasacan**, the coach assistant, said that the excursion was as an apologize to foreign teams for the badly organized contest. We went to Rizal national park, national cathedral, and ended up with a nice dinner in a nice cafe.

Ilham was right; the contest was very badly organized. Nevertheless, we got some improvement this year. This (4th) is our highest rank in ICPC regionals

]]>So, here is my submission: Diglett Hunter. It has poor design; but well, at least the game works. You can choose on of the three themes for the interface. When you make a new high score, your score will be recorded (in browser cookies, not in server :D).

Here is a quick explanation on several parts of the game. Note that this explanation is not exhaustive. It is assumed that you know the basics of HTML DOM and Javascript.

The board consists of 5 x 5 unit squares, generated by the following JS code. This is actually a <table> that consists of 5 <tr>s, each consisting of 5 <td>s.

function genBoard() { document.write('<table id="tableBoard">\n'); for (var i = 0; i < 5; i++) { document.write('<tr>\n'); for (var j = 0; j < 5; j++) { document.write('<td id="tdCell' + i + j + ');">'); document.write('<a href="#"><img id="imgCell' + i + j + '" src="mouse.png" onclick="hitCell(' + i + ', ' + j + ');"/></a>'); document.write('</td>'); } document.write('</tr>\n'); } document.write('</table>\n'); }

Each cell has onlick attribute that specifies what to do if the user clicks on that cell. Please consult to scripts.js for more reference

It is pretty simple; just changing the href attribute of the <link> tag that specifies the stylesheet. The tag has id “linkTheme”.

function changeTheme(themeName) { document.getElementById('linkTheme').href = themeName + '.css'; }

The top scorers are stored in the cookies. The n-th top scorer’s name is stored as “topName*n=xxx*“, while the score is stored as “topScore*n*=*xxx*“.

First, retrieve the top 10 scorers from the cookies and save them in arrays.

function updateTopScorers(playerName, score) { var topNames = new Array(); var topScores = new Array(); for (var i = 1; i <= 10; i++) { topNames[i] = getCookie('topName' + i); topScores[i] = getCookie('topScore' + i); if (topNames[i] == '') topNames[i] = '?'; if (topScores[i] == '') topScores[i] = 0; else topScores[i] = parseInt(topScores[i]); }

Then, we take the new score into account. Just iterate all scores and find the first score that is lower than the new score. It is pretty much like the Insertion Sort algorithm.

for (var i = 1; i <= 10; i++) { if (score > topScores[i]) { for (var j = 10; j > i; j--) { topNames[j] = topNames[j-1]; topScores[j] = topScores[j-1]; } topNames[i] = playerName; topScores[i] = score; alert('Congratulations! You make a new top scorer!'); break; } }

After that, update the cookies and the top scorers list in the HTML page.

for (var i = 1; i <= 10; i++) { setCookie('topName'+i, topNames[i]); setCookie('topScore'+i, topScores[i]); document.getElementById('tdTopName'+i).innerHTML = topNames[i]; document.getElementById('tdTopScore'+i).innerHTML = topScores[i]; } }

The top scorers are shown in a table, in <td>s with ids tdTopName*n* and tdTopScore*n*.

—

For the rest of the game, you can take a look at the .js file (“script.js”). It has some documentation, but only in Indonesian.

I hope you like this lame game!

]]>