My CP Journey - Part 2

Here is the first part. So I joined NUS (National University of Singapore). The competitive programming environment in NUS is competitive to say at the very least.

The main driving force for CP in NUS is Prof. Steven Halim, who is the head coordinator for the ICPC within NUS + Author of CP3 book + Involved in IOI as Singapore head coach. His efforts + the good reputation of NUS attracts a few medallists from different olympiads every year. This ensures a regular supply of smart and competitive students interested in ICPC.

Now let me first explain how ICPC regionals work in South East Asia. In South East Asia, you are allowed to attend at most two regionals in a single year and you are NOT restricted by national boundaries. That is you are allowed to compete in regionals of other countries. I think the reason behind this is that countries in South East Asia are not big, especially Singapore (which only has 4 - 5 technical universities) so you cannot conduct a regional with only teams from a single country. Also most regional sites have a quota for international teams, for example say Jakarta, Indonesia regional will have 30% quota of international teams where say NUS got allocated 4 slots (by the regionals administration team), then this means that the NUS coach can send any 4 team he wants (based on NUS’s internal selection rules) to represent NUS at this regional. Unlike India, the international teams more often than not, don’t have to sit in any sort of official prelims conducted by the regional site. Instead NUS has its own internal selection contest of some sort.

In my batch we had 5-6 new IOI kids (Me, Bernard, Ranald, Sergio, Robin, Kwee Lung, Minh).

1st Year: The ICPC selection process was as follows: An individual contest happened with students from all batches that do CP and let the ranklist obtained via it be represented as a set S. Then,

int team_id = 1;
while(!S.empty()) {
  int leader = *S.begin();
  S.erase(S.begin());
  pair<int, int> x = teammate_picks_of(leader);
  S.erase(S.find(x.first));
  S.erase(S.find(x.second));
  cout<<"Team "<<team_id<<": "<<leader<<" "<<x.first<<" "<<x.second<<endl;
  team_id++;
}

In my first year with the competitive pool of students in NUS I got a rank of 15ish in the above mentioned contest and was selected by Bernard into his team and our team formed was Me, Bernard and Si Wei. Our team name was 3body (motivated by an astronomial problem of 3 body systems)

We didn’t really do a lot of practice contests before competing for our one and only regional this year (we competed in only one regional because we were 5th team in the ranking algorithm) in Jakarta, Indonesia. Surprisingly we did fairly well at Jakarta (from our expectaions) and got 5th position in that regional.

Later on this semester I also took the course CS3233 (a course on Competitive Programming, taught by Prof. Steven) along with all the other IOI kids from my batch and was introduced to Bay Wei Heng. The course itself is a very fast paced version of how one should go about CP and most (i.e 80%) of the students in the course have prior background either through school olympiads or by acquiring a lot of points on Kattis (an online judge, which is very trendy in our university). The course is fun, it is quite competitive though with weekly contests in a high-pressure 1:15 minute environment consisting of good problems and cash prizes. The course also attracts a few companies which are scouting for students for internships, which makes getting internships a slightly easier process.

2nd Year: For our next year, we changed our team slightly and now the combination was Me+Bernard+Wei Heng. Our team name was 3body2 (= 3body + 1). We did a fair number of practice contests (Mainly on CF Gym) during this period and realised our strengths and weaknesses + how to collaborate as a team. The TLDR; version of our team combination was that Wei Heng did most of the math and flow related questions, Bernard was particularly good at constructive algorithms/geometry/greedy and I was responsible for primarily data structural questions (segment trees, hld, lca, hashing) and dps. We did overlap in dp, greedy and graph a lot like most of the other teams would since these are the topics in which almost all people are good. My background in data structures is to be honest at most above average/reasonably good from an Indian Competitive Programming scene standpoint, because we use so much data structures in India and so everyone is quite proficient in DS, however coming to university I realised that the South East Asian programming culture is more balanced with a good mix of mathy + constructive + geometry + flowy questions too. Because of this balancedness my same skill set that I had in India, now got portrayed and exploitable as a Data Structures guy since the level of data structures here was relatively lower.

The rule for internal tie-breaking within our university this year to select a team for WF (ICPC World Finals) was to minimize the following:

Rank at Singapore regional * constant_1 + Rank at 2nd regional * constant_2 + Rank in internal contest * contest_3

I don’t remember the constants as of now, but the important thing is constant_1 > constant_2 > constant_3.

This year we ranked 4th in the internal contest and were competing in two sites: Yangon, Myanmar and Singapore. Yangon, Myanmar as an ICPC site had the reputation of having erratic results because of problems with weak test data + problem statements sometimes not written clearly enough. Because of the erraticity of results, a team like ours also did have a good shot at getting a good rank and fortunate for us we did end up getting 1st rank. (Can read about our experience here). Our second and final site was Singapore, where our team + SendBobsToAlice + Pandamio, all had a chance of securing a slot for world finals. In the Singapore regional, we did okayish and got rank 11. Our rank wasnt that good, but it made us second in the tally (within us + SendBobsToAlice + Pandamio). Also SendBobsToAlice (first in the tally) decided not to go this year (since some of their teammates had already gone to WF before, and they wanted to save their second and final chance to WF for a future iteration, when their team is more prepared and could potentially secure a very good rank). So because of the pass by SendBobsToAlice, our team got the slot and we represented NUS at Portugal, ICPC World Finals 2019.

Before the World Finals I got to attend Moscow Workshop conducted by MIPT, the workshop was a 1-week long workshop in the heart of Russia at Moscow. Each day we used to have a contest with quite tough problems (out of 8-10 problems, me and my teammates were able to solve 3 on average) and later on an analysis discussion of the problems. We also got to see some touristy spots of Russia and the snowy weather was also a different experience. The contests consisted of high quality problems involving novel techniques and very strong teams participating (we generally used to end up in the middle of the rank table). The accomodation and recreational activities were also good. The camp itself was funded by NUS-ICPC (through the generous donations that Prof Steven Halim acquires from various companies) so we didnt have to fund our flight/camp fee. But incase anyone does plan to compete in the camp using their personal funds, then I would recommend to go for remote participation for a better worth-your-money experience.

The world finals itself is an enjoyable event and a kind of reunion for me, where I got to meet my friends from Indian universities after a long while. I met Rajat De, Pratyush Aggarwal two students from my high school. Along with Kushagra, Sreejata, Debjit, Sampriti, Xorfire, Parth, Hanit all of us having been to Indian IOI-TC (India IOI Training Camp) at some point or the other. The contest itself was good and we did okayish, we got 4 problems solved but for two of the problems we wasted a lot of time debugging our solution costing us a potential solve at another problem. The scope for improvement in this contest was to have made fewer bugs and/or debug them faster so we could have solved more problems. In the end we performed below our expectations, getting a joint rank of 60ish whereas we believed our best case hypothetical scenario was under 30.

3rd Year: We stick with the same team combination and name ourselves 3body3 (3body2 + 1). We did two regionals again this year, one in Bangkok, Thailand where we ranked 4th and missed out on a potential second position because of a last minute bug on one of the problems. And the second one in Kaula Lampur, Malaysia (our experience here) probably our best performance till date, where we finished the entire problem set at around 4:30 mark and secured the first position comfortably. The internal tie breaking rule this year was sum of ranks at the two regionals. Our sum was 4 + 1 = 5. After some 3 - 4 regionals in different regions of South East Asia had happened, the list for potential WFists from our univeristy was reduced to us or SendBobsToAlice (who came 1st in Jakarta, Indonesia). Now the Vietnam site was left where SendBobsToAlice ranked > 4, therefore making their sum > 5 (i.e ours), and we got lucky again. Do let me clarify that SendBobsToAlice is a stronger team than ours on an average day, i.e in > 70% of the contests where we and SendBobsToAlice both sat together they have beaten us. Howver, luck happened to be on our side this time around and we got through. This just shows that ICPC selection mechanism is high variance and involves some luck for things to go your way. We did secure our slot for WF this year which was supposed to be conducted in Moscow in mid-June 2020. But because of the entire COVID-19 situation it got postponed and got scheduled for 2021. Let’s see what happens then :)

Camps attended: I mainly attended the Moscow camp during my university education. Once in Moscow before first WF. Second time they came to Singapore before the next year regionals season. And the last time in April 2020 (Before the “original” WF 2020 dates) remotely. I would say everytime the problem set was high quality. Relatively speaking the Singapore one was more doable and the other two were much harder. You get to see plenty of new techniques. Only thing which I feel they dont put an effort to improve is the analysis discussions, where they can be more lucid in explaining and actually discuss implementation details for questions with hard implementations.

Problem Setting: During my high school period, I wasn’t much into problem setting and had only set a few codechef long challenge problems. But coming to college I was give much more opportunities at Indian IOI Training Camp, Indian ICPC Regionals, NUS Course Curriculum and Singapore IOI Selection tests. I find problem setting pretty fun. My way to go about setting problems would be to maintain some sort of .txt file on my PC with all the new ideas I see or interesting observations I make in some problems/theory I read (may it be CS coursework, some theorem I read on wikipedia or even some Math coursework problem) and later when some contest (say ICPC Regionals) is nearing, then I would try to form some sort of problem using those ideas. I am glad to say that I improved reasonably as a problem setter and tried my best to provide novel problems to the community. The collection of problems I have made can be seen here. I also must add that problem setting is rewarded well in terms of monetary compensation atleast for Indian ICPC Regionals and NUS Course Curriculum which is a bonus as it gives you a good feeling of being productive. It also helps you in thinking how to design test data of certain problems effectively.

Losing Interest in CP: My interest towards CP has declined over the years and now I am not that fascinated by solving questions / getting ACs. I still like to solve problems every once in a while and am still excited when I see a new CF blog with a new random technique, but yeah my interest in the domain has decreased definitely. I find things to be somewhat repetitive at some level and finding novelty becomes harder when you have seen so many questions/similar stuff before. I think that is part and parcel of any hobby/interest one has. I can only hope that I still finding CP interesting in the years to come. I would say my algorithmic curiosity has not decreased but branched off to other domains that I got to know about in university, mainly Randomised algorithms, Sampling/Streaming algorithms, etc. These kinds of algorithmic courses change our fundamental assumptions on how accurate we want our answers to be, how much memory we have to store the data and how much computation power we have (might be a distributed setting for example). These variants of algorithms allow you to think about algorithms in different ways, at the heart it is still doing logical reasoning to solve a problem but now the tools to solve and the constraints specified are in a different format. I have tried introducing some of these ideas to the CP problems I have set (Ex. I have set a question for which I came up with randomised solution first and then a deterministic one (Relay Marathon) and have set a question about a simple distributed algorithm (Boruvksa’s Algorithm) (Spanning Tree)). I hope these kinds of domains are tested more in CP in the years to come and become more mainstream.

Personal Practice: I didnt really do a lot of individual practice during my university life. We mainly did CF gym as a team a few times every year and used to compete in the moscow workshops. Apart from these I didn’t explicitly practice a lot on CF or any other judge for that matter. I was able to reach Yellow on CF (and hope to reach Red someday in future), but didnt sit in a lot of contests primarily because of lost of interest in CP + constant academic commitments in university + Singapore time zone doesnt really suit well with CF. I also got this takeaway that there is a law of diminishing returns in terms of how much you gain by practicing as you become better in a certain domain. Even if I practice a lot or reasonably enough, it is hard to see the effect now compared to when I was in School when that effect was much more visible.

Giving back: I have been fortunate enough to learn so much about CS and Algorithms through CP and friends I made from CP. As a way of imparting my knowledge to other students, I have contributed to CodeChefs learning series (Kind of like a weekly structured course, aimed to get novice students interested in CP to pace with what kind of theory is expected to be known, etc). Also helped a few students in the Indian school coding scene with resolving their doubts and queries about CP.

In the end I would like to say that I have been more fortunate than smart in my CP journey. Since I am not the smartest CP guy in my college, my two other teammates were hands down better problem solvers than me. And even other teams had better people than us in terms of individual CP skills. But we were fortunate to have a been to regionals which were easier to crack + had a good team combination where we complemented each other strenghts and weaknesses well, i.e we weren’t significantly bad in any sort of problems category and all of us are decentish at implementation so we didnt have the high risk of having a single implementation guy who by mistake might have a bad day.

Also I would like to thank Prof Steven, the main driving force behind NUS ICPC. He went out of his way to conduct internal contests, discuss team stratergies, helped me gain TA experience, etc. He also ensured that NUS ICPC had enough sponsors so that we could attend regionals, WFs and camps without spending a single cent of our own.

Internal Scoreboard in 2017 Internal Scoreboard in 2020

One of the achievements unlocked by the end of my Year 3 is moving to first position on the internal scoreboard that Steven maintains. Not that it reflects that I was the best, since it takes into account CS3233 grade + Kattis pts + CF rating, etc, which a lot of good people dont put enough effort into.

Well, this post was long overdue. Now I am only left with WF2020 (which I hope happens as expected in 2021) and maybe I will add an update to this post once it happens. But that’s it folks.

It ain't much, but it's honest work

Photographs of all the main events I could collect

Written on April 9, 2020