This is gonna be a LONG post, because I want to document my entire ACM - ICPC experience for posterity here.
I participated in ACM-ICPC Chennai Regionals 2016 this December. The dates of the Regional were 20th December 2016, and our hosts were Hindustan University. I was in a team with Shikhar and Princu, two of the best guys I’ve ever met, and even though, our result in the end could have been much better, the experience was great and we had a LOT of fun. Because of our fascination and extensive experience with Segment Trees, we named our team LazyLeaves (well we also didn’t want to miss a chance to call ourselves lazy). Our mentor was Dr. Lokesh Chouhan, faculty at NIT-H, who had previously taught us Computer Organization.
Online Qualifiers
We had registered for both Amritapuri and Chennai Regionals, but this time, there was only one qualifier for each site taking place on the 22nd of October, 2016. During the run up to the qualifier, me and Princu had taken part in a few practice contests as a team, and our performance had been, in my opinion, pretty good. We’d done a Codeforces ICPC training round in the Gym in which we’d been able to solve 6 problems and we had also done the practice contest organized by the Amritapuri people in which we solved 3 problems out of 5. I expected a good performance in the Qualifiers, especially with Shikhar also being there.
But nothing went our way during the qualifiers. The Codechef site could not handle the pressure of ~3000 teams participating apparently and each and every one of our submissions, except the first one for the cakewalk problem, took around 10-15 minutes to be judged. We solved A and C pretty easily with no penalties, but as we’re prone to, we submitted a buggy solution for B, which was pretty much a problem that only involved handling corner cases. During the time we were waiting for our buggy solution to be judged, we move on to D, which was a pretty easy DP problem, but we thought up a completely incorrect solution for that too. So now we have 2 penalties on B and D, and are ranked 2nd in the college, at which point I’m having doubts as to whether we’ll even be able to qualify for the regionals.
Luckily, we found the bug in B. However there was some ambiguity in the problem statement, due to which we weren’t able to agree on whether the answer to a trivial case would be “YES” or “NO”. We were desperate and it was taking ~20 minutes for each solution to be judged, so Princu came up with the idea of submitting two solutions, one with “YES” for the trivial case and the other with “NO”. Stuff like this is what makes me feel that we might not be the best coders but our skills cannot be duplicated. :)
After some time, we’ve solved A, C, B and D and we move on to F which is a really easy constructive algorithms problem. With around 15 minutes left, Shikhar begins implementing the problem while me and Princu try to look for bugs in the code he’s writing. When he’s done implementing, there’s around 5 minutes left and we try to open the Codechef page to submit, only to find out that Codechef has logged us out and is acting up. We get plenty of 502 Gateway errors and in the end, we’re not able to submit the solution for F, even though it was easier than D and solved by more people.
We end with a rank of 460, which is quite literally the worst performance we’ve ever had in a team contest.
It is my opinion that Codechef should work on making sure that their site doesn’t act up so much, during a contest of such large proportions. Their site was a major reason why more teams from our college weren’t able to qualify for the onsites.
Before the Regionals
The qualifiers had me pretty disappointed, so I made the decision of only going to one regional and not two. After discussion with my teammates, we decided on Chennai (mostly because we were sure no matter how bad it went for us in Chennai, we’d get a rank under 75 at least ;) )
Practice went on as much as it could, with me doing Codeforces rounds and hovering around a rating of mid-1800’s the entire time. Me and Princu stayed back after examinations to get some team practice in. We tried to virtually participate in one of the past Amritapuri regionals almost every day, but the lazy atmosphere of holidays and an empty hostel made it a little difficult to get much done.
Our flight to Chennai was from Delhi, and we had decided to reach Delhi a day earlier to make sure that we didn’t miss it. So we roamed around Delhi on the 17th of December. We went to Qutub Minar and then turned back to go watch Fantastic Beasts after seeing the crowd at Qutub Minar (again something that only we would do :D ).
On the 18th, we reached Chennai, with its warm weather. Coming from Delhi in the middle of night, this change of weather made me look like an idiot wearing three layers of clothing and sweating like a pig. Hindustan University is around 40 km away from the airport, so we called a cab which got us there in what seemed like the longest time. Chennai had been hit by a cyclone just a week earlier, so there were fallen trees all around. The hostels at Hindustan University must have been hit by the cyclone also, because they made us stay in the Lecture Hall with three other teams. Co-incidentally one of the teams was from Lucknow also. I’ve noticed that people from Lucknow are everywhere and mostly all of them are really cool.
Let me get to the most important thing, the goodies we got :D. Each one of us got the following:
- 1 ACM-ICPC T-Shirt (courtesy Hindustan University)
- 1 ACM-ICPC Bag (courtesy Hindustan University)
- 1 ACM-ICPC T-Shirt (courtesy CodeChef)
- 1 Codechef notebook of sorts
- 1 ball pen (courtesy Codechef)
Of course, Codechef took a photo of us, with their choice of props and our choice of writing. Lucknow and NITH represent!
There was a talk by CodeChef head (?), Anup Kalbalia, in which he talked about why India doesn’t perform well in the World finals. He talked about the fact that it is mostly because people here begin coding at the age of ~18 in their first year of college generally while in other places, they start programming much earlier. He said that we need to get competitive coding into schools and make sure that children code from the very beginning. I think that this cause of getting kids to code is great but the motives behind this seem a little suspect to me. It reminded me a little of China getting kids to do only one thing to prepare for the olympics, which always looked bad to me as it seemed the kid doesn’t even have a chance to discover other things she likes. But I digress, as this is the topic of another post.
Anyways, there was a “dry-run” contest of one hour for Codechef to check that their setup was working well. It consisted of problems from previous online contests, which we had never even looked at. A was easy and I got AC for it in a short amount of time. B was some kind of math, which we’re unfortunately not very good at, so we weren’t able to solve that in the time period. However, we got C done, which was an easy DP problem. I began seeing a pattern here, we could easily solve DP problems that other people might find difficult but bring us topics that we didn’t know and we were useless. This came up later in the actual contest also.
We decided to roam around a little and went to Kolavam Beach that night, which was around 30 minutes away from the college. Really beautiful place. Me and Shikhar ate crab at the beach (Rastogi is a vegetarian) and then, we came across some of the best sweet corn there.
The Competition
The competition started the next day at 10:30 AM. We had been provided with a print of the notebook we had sent the Chennai guys in advance and a printout of the problems themselves. You can view the problems here.
Problem G was the first problem that I solved. All you had to do was count the number of distinct elements in an array, so you put the numbers in a std::set and then print its size. While I was solving this, Shikhar was going through the problem set and Princu had come up with the solution for F, which was the second easy problem of the contest. Problem F involved filling a matrix with consecutive numbers going top to bottom and left to right. Pretty easy implementation problem, but I tried to make sure that there weren’t any bugs in the code that I wrote. Me and Shikhar double-checked the code and later submitted it. Two submissions, both accepted, same as the qualifiers. I was hoping against hope that this time we won’t trip up at our third submission but it wasn’t meant to be.
The third problem was Problem C. The problem was simple, it involved finding the modular inverse for a given number \(n\) mod \(p\). The modular inverse of any number \(n\) mod \(p\) is \(n^{-1}\) such that
\[n n^{-1} \equiv 1\ (\textrm{mod}\ p)\]This is an extremely easy problem when \(p\) is prime because of Fermat’s Little Theorem which states that:
\[a^{p} \equiv a\ (\textrm{mod}\ p)\]What this implies is that the modular inverse of any number \(a\) mod \(p\) is equal to \(a^{p - 2}\) mod \(p\) or
\[a^{p - 2} \equiv a^{-1}\ (\textrm{mod}\ p)\]This is really basic number theory every competitive coder knows and we did too. In our hurry to get a third AC, we missed out on thinking that this stuff only works when \(p\) is prime. I wrote a solution implementing exponentiation by squaring to find \(a^{p - 2}\) and we checked it for bugs and submitted. As soon as I saw the wrong answer, I realized (once again) that we were idiots. I say that we’ll have to find the answer for when \(p\) is not prime and me and Princu start working on using Euclid’s method somehow.
Meanwhile Shikhar has found a easy problem of the trie data structure. This was problem I. A short version of the problem is this: “Given a two set of strings \(A\) and \(B\), for each string \(s\) in A, find out the maximum size of subset of \(B\) \((b_1, b_2, \dots b_k)\) such that for each \(i\) the first \(i\) characters of \(s\) and \(b_i\) are equal.”
The solution is pretty simple, you put all strings in \(B\) in a trie and then for each string in \(A\), you run a dfs while keeping track of how many branches of the trie have been used. Me and Shikhar discuss the approach, he codes it up and we debug it to make sure it is correct. We get our third AC on the easy-medium problem, while the easy one remains unsolved. (See the pattern?)
The solution to the modular inverse problem is pretty simple, you assert that \(gcd(a, p) = 1\) (if this is false, there’s no solution) and use Euclid’s Extended Algorithm to find a solution to the equation \(ax + py = 1\). Then you print out \(x\ \textrm{mod}\ p\) as the answer. Me and Princu know all this, but somehow under pressure no one is able to think of this. Just as we had almost lost all hope, our real skills shined through.
Somehow, I remember that Java’s BigInteger class has a modInverse function. As soon as I tell this to them, we realize that someone’s gonna have to write Java. I try to recall as much as I can from my 11th class and we use the docs provided to us to somehow write a solution to C. As we submit it, me and Shikhar note that stuff like this only we can do. I still believe that this type of jugaad is what our specialty is. This is why we do well in long challenges also. Maybe it’s the Lucknow upbringing of ours. :P
Anyways, we get our fourth AC, which was the last we would get. We tried to solve problem B also. The abridged version of the problem (taken from CodeChef’s blog): “Given a set of mixtures with two different types of solutes each having a cost associated with it, find the minimum cost to prepare all of them. You can either prepare one from scratch incurring the respective cost or use a linear combination of previously prepared mixtures without incurring any additional penalty. “ This seemed like another math problem to me and we tried to find something that would give us a solution but nothing came to us then. We spent around 1:30 hours sitting around doing nothing. :/
Later, when I came to know that B was a geometry problem, needing to be solved by finding the Convex Hull, I had mixed feelings. It was a really easy problem that we would easily have been able to solve if we knew any computational geomtry at all. 5 questions would have given us a great rank but it was all luck though. I’m sure if the 5th question was a topic that we’d worked on, we would have gotten a much better rank.
We ended the contest ranked 49, which was pretty good considering how we’d solved problem C. I guess if we’d known some geometry we could have been in the top 20. Ah well, next time we’ll do better!
Aftermath
The contest had made us tired and after eating and roaming around a little, we decided to head back to the lecture hall and sleep. People were discussing the problems and that made me a little uncomfortable because it brought back memories of exams like JEE Mains and Advanced etc. I think that the laid-back way in which we do competitive coding and the way some others do it is pretty different.
The next day we took the flight from Chennai to Lucknow and the event was over. On to the next thing!