Qualifying for ICPC World Finals 2020 - An experience (Part 3 - Training for Amritapuri Regionals)

We said bye to Shriram, as he was going back home for now. Tushar and I headed over to my home, where he would be staying for the rest of December, as Amritapuri regionals was right after Christmas.

Cheers everyone, I'm back with the 3rd part in this 4-part series! This post will cover our training and experience uptil the end of Amritapuri regionals, with the Asia West finals to be covered in part 4. I realize I'm writing this over a year since the last blogpost, but there are some reasons for this I will talk about elsewhere. Anyway - with the regionals for ICPC 2021 coming up next month, it seems like the perfect time to finish what I promised! :)

After the Kharagpur regionals, it was clear that we had an outside shot at making the World Finals, no matter how outside the shot really was. We started solving problems on the train right from the way back from Kharagpur, to make up for the lost practice in the previous months. Even though we did not know much theory relative to the other top teams, with practice rounds we realized that our performance often suffered not because of some algorithm that we did not know (although this was sometimes the case), but more often because we had not seen some trick or had implementation problems in some question.

Thus, when Tushar and I got home, we decided to do something like an ICPC-type practice contest a day. Moreover, my parents had to leave us home alone due to exigent circumstances, and with no distractions, we had the ideal environment for practice.

Due to our sleep cycles not syncing up (at all), we decided on doing only about 1 contest a day as a team, and the rest of the time was spent in reading the editorials and pursuing other pass-times/hobbies. I had a conference to attend to in the middle of December as well (FSTTCS - I had a great experience there, as it was my first theoretical CS conference!), but that's for another time.

Both of us decided to give the Pune-Gwalior replay contest together on a single laptop, to simulate how we would perform on a regional. We got off to a very bad start, getting multiple WAs on easy problems and then in the 3rd-4th hour misreading and mis-solving DICITIES about 3 times, re-writing the code each time. We ended up with 8 problems solved, with me having almost coded the 9th, whose idea turned out to be correct. We were surprised to see that 9 problems would be good for clear 2nd place, with IIT Kanpur solving 10 problems and IIIT-Delhi solving 8. It seemed like we had hope at Amrita, where both of these teams would not be participating. 

In a few days, Shriram joined us, and we gave a few more team contests. Results were not very consistent, with us doing really well sometimes and getting stuck on something we needed to overcome (by, for eg, skipping problems or implementation practice) other times. Soon, it was time to leave for Bangalore. We were confident that we could do okay, but winning still seemed like a distant dream.

At the Bangalore train station, we were picked up by volunteers from the Amrita school of engineering. We left in a bus, reaching the school in about an hour. The Bangalore campus seemed to be much smaller than the Amritapuri campus, but just as lively! There was a large ground in which people were playing, and multiple canteens/eateries, etc. We made our way to our accommodations, and after settling down, immediately began looking for places to eat - we were a team of gluttons, after all! 

During and after lunch, we made friends with a few teams around us. Most of all, I was excited to meet the people beyond the handles I'd been talking to for the past year on my computer screen - for example, aryanc403, Taran_1407, and Ashishgup. There was to be an outing in the evening, so I decided to go, and sent a message to all of them to come to the trip - we could finally meet each other there! Turns out Ashish was busy with other work, so I, Aryan and Taranpreet went on the trip with various other teams. While Aryan and I got on the first bus, Taranpreet followed us on the next. There were many people missing, possibly because they were working on their preparations or team notebooks. Both my teammates decided not to come as well, as it was a trip to a local garden. 

Our bus ended up arriving early, so I and Aryan started looking around. It was already close to 4 pm, which meant it was time for another meal :P. We started looking around for eateries, and found one close to where we were - and we had a light meal there, before heading to the garden. It seemed that all the teams had split into their own clusters, with teams from a single institute banding together. Since none of us had teammates, we decided to talk to as many different people as we could! We ended up talking to a bunch of different people, asking about their ICPC experiences and future plans. One of these interesting conversations was with the teams from IIT-BHU, who had multiple strong teams, with one of them barely missing WF the previous year. IIIT-D had many teams on the trip as well, who were playing some games among themselves. We decided to snap a picture as a commemorative photo of our first meeting, and ended up posting it on social media with the clever caption "2 Gods and 1 Noob(?)"

, in the hopes of torturing some curious souls as to the identity of the "Noob" among us. (Yes, we did the imposter thing before it was cool :P). We added the hashtag #NotMyICPCTeam, as a play on the hashtag #MyICPCTeam which was supposed to trend. 

From left to right: Aryan, me, Taranpreet

As is tradition, there was a feast in the evening to celebrate the event itself. And fittingly, as is tradition, there was some tension in the air, with the big contest coming up next morning! We ate dinner quickly, and went back to revise some ideas that we hadn't had time to look at before. Right from various Combinatorial games such as Hackenbush to some Jacobi symbol properties and group theory, we nervously rushed through a lot of content until we decided it was better to sleep and conserve our energy. No team is free from nerves, it seems. During this time, we also made friends with the neighbouring teams in our dorm, who had also been in the Kharagpur regionals.

We rose early on the day of the contest, with me having a restless sleep as is usual when I'm nervous. After getting ready quickly (so that I could come back and wake the others), I realized yet again that there was no need to wake my teammates, especially today. Everybody was taking this seriously - they were already up, despite all of us having a habit of sleeping in whenever possible. We got ready significantly early, and this time, we didn't make the mistakes from our previous regionals - I made sure to shave, since last time I had sworn it was the reason we hadn't won! Moreover, we decided to spend 30 minutes dancing to K-pop songs (read this for the reference) - we were not taking any chances when it came to winning. 

ICPC Amritapuri Regionals 2019 

The above contest can be found here. The live commentary blog can be found here, but I recommend you see it after reading this blog. I also highly recommend giving the contest on your own before reading the below - it contains heavy spoilers, as you would expect.

With our hearts in our mouths, we headed to the regional area, and sat down at our computer. As is standard, there was a small delay with the regional starting time. I quickly started typing our template out, while Tushar was looking over my shoulder and reading lines from our template that I should add. Finally, everything was in place and the contest started.

I found myself in front of the keyboard, as is usual in the starting hour for our team - having the best typing and comprehension speed, I usually got the easy problems out of the way quickly. This time, it was clear the easiest problem was USANBOLT - being something like a div2A, I quickly coded it and got AC. Having spent a few seconds making sure everything was typecasted correctly and there were no issues, we were definitely not the first AC this time, unlike the previous contest. Meanwhile, Shriram got the solution to SDIFFSTR and Tushar was looking at EXPCAN. I started looking at the other problems.

Shriram coded up SDIFFSTR, which was an easy Div2A-level problem that has a greedy solution. After Shriram got AC, Tushar coded up EXPCAN while I and Shriram discussed COLPOLLY, which I thought was the next easiest problem. I had the strong intuition that a very small number of colours is necessary, and we come to the conclusion that 3 is enough, since you can triangulate the graph. However, how to get this colouring? I proposed starting from a random node and giving colours iteratively - we agreed to try this, since it seemed that if the solution wasn't this, then we need to find the triangles, which will take us more than 20 minutes anyway - so the penalty is fine. Tushar got WA, printed his solution, and I took over and coded this solution to COLPOLLY. It got WA, and meanwhile Tushar and Shriram figured out the mistake in his solution to EXPCAN. He proceeded to fix the code, and was rewarded with a shining AC. Actually, his solution to EXPCAN is interesting - the problem's constraints allow an n^2 solution to pass, but we can do it in O(n). The main observation to solve it in O(n) is that states which are "unbalanced" in terms of the number of elements removed from the left and right (for eg, 30 elements removed from the left and 70 from the right) have very low probabilities of occurring. I couldn't find anyone who had already submitted this solution on Codechef, so I added my code for this idea here. This idea is not that easy and probably is already worth about a Div 2D-E rating; however, since the original problem did not require this, it is only about a Div 2C.

Meanwhile, I had started looking at other problems, since we got WA in COLPOLLY. To be specific, I believed COLINT and MORTAGE looked doable. Meanwhile, Shriram explained to Tushar the idea about atmost 3 colours in COLPOLLY, and I came up with a counter example to the original algorithm. We knew the actual algorithm for this would be just to write down the triangles and solve it iteratively, which would be a little painful to code. However, Tushar almost immediately claimed that a priority queue where you choose nodes with highest number of assigned nodes as neighbours will work. In a few minutes, he is convinced this is correct. Since this is much easier to code, we let him type it out. Meanwhile, I am convinced that COLINT has a greedy solution. 

Tushar surprisingly got AC on COLPOLLY, and we were stunned for a moment! No other team had done that problem so far, whereas all other problems had been done by more than 1 team - hence, we had an "advantage" in that we had to catch up on the easier problems. I told Tushar my greedy solution on COLINT, and he was unconvinced. However, I believed I had a proof, and my teammates just decided to trust me on it and let me code it. I coded it up quickly and we get AC. So, we had about 5 ACs in slightly more than an hour. From this point on the problems were harder, and hence we took more time on each problem. 

I and Tushar discussed MORTGAGE for a bit, and I told him to leave it to me. He and Shriram discuss TRGRPH and POLCON. At this point in time, MORTGAGE was the problem we had't done which has been done by some teams. I thought about it for some time, and soon I had a solution which could be proved via exchange arguments, which we had looked at recently. I told Tushar about it and he was again unconvinced - he is a bit skeptical about greedy algorithms in general!

I did believe it was correct though, and I started coding it. The nervousness of being close to the top of the ranklist got to me a bit, and as a result I was a bit slow at writing the code, wanting to not make any mistakes. The solution to this problem involves a binary search, followed by a greedy idea. I used a fixed epsilon, and stopped whenever the absolute error is smaller than epsilon (which as we will learn soon, is a very bad idea!).

Meanwhile, Tushar and Shriram had gotten a solution to TRGRAPH. I submitted MORTGAGE after finishing my code, and we received our second WA at the contest. Surprised, I printed the code quickly and gave up the computer so that they could code up TRGRAPH. I looked at my code, and was unable to find any mistakes as such. I asked Shriram to go over my code, and he found a mistake in one of my loops - I had not handled one of the edge cases correctly. I took over the computer for a bit, fixed this bug, and resubmitted. Only to receive a TLE!

At this point, we were a bit tilted because MORTGAGE had been solved by several other teams, and although we are the only ones who have solved COLPOLLY, we could feel the lead slipping away. Moreover, a Codechef representative came up to us, and told us that our solution to COLPOLLY may be wrong - and we may be hacked as they might add testcases between the contest, to make our solution fail! Meanwhile, Tushar looked over my MORTGAGE code for a bit, and quickly noticed my epsilon idiocy - it is much better in general to use a fixed number of iterations, especially when both absolute and relative error are involved. To be safe, he also rewrote some more of my code such as fast exponentiation to be iterative instead of recursive. He finally pressed the "Submit" button, to get another WA! This felt like the ultimate disaster.

We started looking at other problems, while rotating looking for mistakes in the code of MORTGAGE in the three of us. Tushar finally got AC on TRGRAPH, and he and Shriram realized that POLCON is just a direct application of Dilworth's theorem of maximal anti-chains. Tushar told me this, while Shriram looked at PERMDIST. I coded up the geometry part, only to realize that I made a mistake the previous night. We had decided that we should add "check if a point is inside a convex polygon in O(logN)" to our notebook, but it being late at night before the contest, I just decided to add the pseudo-code in our notebook, thinking that on the off-chance it appeared in the contest, we could reproduce it. Now, we are looking at a problem with n = 100, where we need to find whether n convex polygons are pairwise within each other or not, and the convex polygon algorithm brings the complexity down to O(n^3logn) from O(n^4). We lamented this for a bit, before deciding just to write the O(n^4) and pray to god that it passes.

...And of course, it got TLE, because what can go wrong does go wrong, doesn't it?

Tushar looked over the code, and saw a couple of places where early exits could be added, and resubmitted immediately before we could tell him he wrote a bug while we were looking on. So, we had another immediate resubmit after fixing that bug, and finally the code passes! That was lucky. Later, we learned that it was possible to solve this in O(n^3) by simply creating the convex hull of pairwise 2 polygons, and checking if it is one of the polygons. 

At this point, other teams had started getting ACs on COLPOLLY. We had to figure out the mistake on MORTGAGE - fast, if we wanted to have even an outside shot of winning. I started looking at PERMDIST again, since I had solved a similar problem before, but there were still some significant differences. Tushar looked at MOBCNT - I quickly decided that LALALANT is not worth looking at, and we just threw the problem away (it is way too case-worky). With the 4-hour mark close by, Shriram finally noticed a bug in MORTGAGE - when Tushar had changed my fast exponentiation to iterative, he ended up writing (x>>1) instead of (x<<1) - which meant x was being divided by 2 instead of multiplied by 2. Thus, we almost threw away our whole contest on just a stupid mistake of opposite operators! How frustrating. Finally, after 7 wrong attempts and with the time on the clock as 3:47, we got AC on MORTGAGE. Around this time, a representative from Codechef came and told us that our solution to COLPOLLY was no longer being considered for hacking, and it would be considered as AC. (Later, in the solution session they said that "some team" had submitted it and they managed to prove it by looking at some papers).

We were 3rd in the ranklist - the top 2 teams being "AlwaysReadyToOverkill" from IIT Delhi and "Laila" from IIT Roorkee, with all of us being tied on 8 problems, and the 4th team having 7 problems with a small penalty. We were sure that the other teams would do atleast one problem, since they had about 90 minutes from their last AC to do a problem. Because our penalty was so bad, we needed to do 2 problems to have a shot at winning. We hunkered down and got to business. I started looking at COMPLEXG and started getting ideas, while Tushar got the idea for MOBCNT. After discussing with Shriram, he was convinced he had the correct idea, and started coding it immediately. Miraculously, within about 15 minutes, Tushar got AC on his first try! Thus, with about 55 minutes left, we had to do one more problem to have a shot at winning.

None of us got any ideas on PERMDIST, so we decided to focus on COMPLEXG completely. I had gotten the idea that we could represent everything in terms of directions, which was also independently reached by my other teammates when they had seen the problem. Thus, it was clear how to solve the problem with DP when the graph was a DAG. Tushar started coding this part, while we watched and continued to think about how to solve the problem when the graph is a general directed graph. During this point, a representative from Codechef decided to come by and take a picture of the "top teams" for their Twitter page, and he alerted us and told us to smile at the camera. It is my personal opinion that such things should be done with minimal disturbances to the contestants - what if we had missed ACing this problem by a few seconds (a very real possibility)? Obviously, Codechef would not have taken responsibility, and we would have been robbed of a World Finals opportunity. Either way, we were unable to figure out how to fix the issues for general directed graphs by making the SCC graph in time, and we resigned ourselves to our fate of 9 problems. I am attaching another photo CC had taken below (the one where we are looking at the camera was ugly, partly because we were nervous wrecks). 

A picture taken by a CC representative

 After the end of the contest, we were left with the bittersweet taste of defeat in our mouths. We were sure that the teams "Laila" and "AlwaysReadyToOverkill", which were the top 2 teams before the ranklist froze (we were third, all three tied on 8 problems) had done atleast one more problem in the final hour, and we had an absolutely terrible penalty because of our 7 WAs on MORTGAGE.

To confirm our fears, we decided to ask all the top teams about their performance as soon as possible, to confirm our loss. The first team to ask was the team "Hold Right There Sparky!" from IIT Roorkee, who were just 2 rows diagonally ahead of us in the contest hall (since Amrita is a big regional, even in just the Bangalore site there were something like 3-4 halls). 

..and it turned out that Hold Right Sparky had done 9 problems! One thing I notice about this team is that they are very "clutch" - they tend to not do that well in the first 3-4 hours, and then go on an absolute tear in the final hour. In Amrita, they had I believe 7 problems when the ranklist froze, and they jumped to 9. Either way, we decided to quickly compute our penalty to confirm our worst fears and begin the coping process. However, it turned out by our calculations that... we were a little bit better on penalty! Their teammate said they were slightly better, but after a more detailed investigation we found out that we indeed had a slightly better penalty. We felt this was just prolonging the suffering at that point.

Hold Right There Sparky found out that Laila ended up with 8 problems, failing to do anything in the last hour... and suddenly, there was hope. Did everyone really brick everything in the last hour? Was it possible?

We tried looking for the team "AlwaysReadyToOverkill", but were unable to find them anywhere. In the lunch area, Aryan told us they were only able to do 8 problems! We were stunned, and afraid to believe only to be let down. We started realising we might have won the whole thing - however, it wasn't done till it was done. There might have well been another team like Hold Right There Sparky, which could have gotten 2-3 problems in the final hour due to our high number of penalties.

After talking with the teams who had lesser penalty than Hold Right There Sparky on 7 problems, we started realizing that they had been unable to do 9 either. Moreover, we realised that not many teams could overtake us since we got COLPOLLY extremely quickly in comparison to other teams! With bated breath, barely able to hold our excitement, we went to the prize distribution ceremony. Tushar had a train immediately after, but he was willing to cut it close for the possible moment of glory. And soon, starting from the ICPC for schools prizes and so on, we started counting down the top 10 teams at ICPC Amrita. Most of them were strong teams whom I recognised as top competitors in the country. We were just praying to not hear our name until the very end. Soon, rank 3 was announced as "AlwaysReadyToOverkill" with 8 problems, and rank 2 was announced as..... "HoldRightThereSparky" with 9 problems! With a sigh of relief, we walked up to the stage in disbelief as we finally lifted the trophy, only seen before in our dreams. If you had told me in the morning that this would actually happen, I would have called you a crackpot. As the cards were dealt, it actually happened and it was an unbelievable moment. We were congratulated by many of our friends and some strangers on winning. Unfortunately, Tushar had to leave, but the rest of us decided to have a fun evening, and since we were (persistently) pestered for a party, we decided to oblige.

In the evening, everyone gathered and out of the people invited, exactly 10 of us decided to go: Me and Shriram from our team, Taranpreet Singh, Udit Sanghi, Aryan's team (Aryan, Umang and Abhay) and Jeel's team (Jeel, Sparsh and Ashish). Since we were really feeling like doing something fun, we decided to play laser tag at a close-by game centre. On with the games!

It turned out that laser tag had a long waiting time of about an hour, so we bought tickets and decided to have dinner somewhere while waiting. It turned out that a decent restaurant was on the 2nd floor of the game center, and so we decided to have dinner (consisting of noodles, pizza and pasta, of course - what did you expect a bunch of teenagers to eat?) there. We had a fun time, with everyone talking about their ICPC experiences, what they were doing and planned to do ahead, and laughing and making jokes in general. Although it was my first time meeting all of these people, I had interacted with them online and it was great to meet up and party like this.

Finally, we moved on to the actual laser tag game, right on time. We were divided into two teams, and put into a maze. We had to score points by shooting the opposing team's people at certain positions (a target was placed at various places on each person's body) to gain points. There were also targets around the maze which granted points, including each team having a "main target" they had to protect, which gave much more points than the normal ones.

At the start, my team went with a conservative approach, guarding the target and prioritizing personal safety (you would get timed out for a bit if you were shot) over scoring points quickly. However, as some members of the opposing team started using more aggressive approaches, beating our defenders and heading to our goal target, we started becoming more brazen in our attack as well. After a point, it became pretty much about quick instincts and precise shooting rather than smart play and hiding. As expected, in real life I am as bad at shooting games as I am on PC games, and hence I ended up nearly at the bottom of my team's scorecard in terms of points. However, our team ended up winning, since all of us contributed a good amount of points to slightly edge out the opposing team. Meanwhile, Umang carried the opposing team, racking up a monstrous score and the individual highest!

After this fun activity, we head back to our dorms where we decide to play cards and stay awake all night, as many people have flights early in the morning. Naturally, my room was chosen as the target, as Tushar had already left, and various beds are brought in from other rooms to make space for a larger gathering. We were joined by our friends from BITS Pilani (aka Ashishgup and friends). We ended up making a huge racket, and the security guard literally runs to catch us red-handed making noise. We get warned a couple of times about making too much noise as the other students are trying to sleep, and soon we became smarter in our ways of making noise.

We started placing someone closer to the door to warn us if he sees the guard on his rounds, as well as moved a bit farther from the door and made louder noises only at periodic intervals to pass under the radar. We still got called out about 5 more times, but as more and more people left for their flights and trains, we start to change the games to dumb charades and so on until Shriram left and I decided to get some sleep. We finally disbanded, and I fell asleep on the floor with a pillow under my head, exhausted by all that happened and still in a bit of disbelief - just hoping that it wasn't all a dream. I woke up a little past 12, and posted an Instagram status asking if anyone wanted to meet in Bangalore. 

After freshening myself up a bit, I saw that a friend had replied, so I went to the mall to meet her and spend some time hanging out. She told me a bit about the area, and I left early because I was excited to meet a PhD student I had been working with on a cool project for a while, who works at DRDO Bangalore. I packed my bags and headed to their place, and I wound up staying there for dinner while meeting his wonderful wife and son, who made my visit memorable. We also discussed some research ideas, and soon after this visit 3 papers from our research group get accepted - perhaps this visit was super lucky somehow (yay!).

Finally, I left for Bangalore airport in a bus - apparently, Bangalore airport is far outside the city, so it takes more than an hour (possibly 2) to reach. Having some time to myself, I finally reflected on our performance at ICPC Amrita. I feel like Tushar with his quick solution of MOBCNT and Shriram with the quick 3 colour COLPOLLY idea had their standout moments. I knew I could do better - I decided to view Asia West regionals as a chance to do my best. Moreover, while all 3 of us decided to take a break from programming for a while - practice had really been tiring, and we were saturated - we also realized that our win in Amrita was somewhat influenced by a bit of luck, not solving any problem that was significantly hard but still winning. Thus, Asia West was a place to prove, once more, that we as a team deserved to qualify for the World Finals. With these positive thoughts in my mind, I got on my flight and looked forward to a week-long break...