After the confirmation of qualifying for our 2 regionals, we breathed a sigh of relief - which was surprisingly short-lived. This was the perennial "calm before the storm".
Hello everyone, I'm back with the second part of this 4-part series. This will be significantly longer than the last post, as there are a lot more things to describe here. So, let's get right into it!
After the qualification round, we had vowed to practice more for the upcoming regionals - we knew we had a chance, however slight, of actually qualifying for WF. However, there were some changes in the WF selection criteria this year. You could go to upto 2 regionals out of 4, and only the top team from each regional would be selected. Around 40 top teams in total would be invited to Asia West as well, to decide the Asia West champions and also to offer additional WF slots.
We came to know about these changes before applying for regionals, and accordingly we choose Kharagpur and Amritapuri regionals - Kharagpur because it was the weakest field of any regional according to the people who were planning to attend, and Amritapuri in case we did badly in the online round, since with good probability they will choose teams on merit. Thus, it turned out that our first regional was Kharagpur, to be held on 7th December.
It turned out that all 3 of us had sufficiently different schedules such that we usually had practice sessions available only from 10pm - 3am, and post-contest discussions from 3am - 5 or 6am, and thus it turns out that I missed some classes in the morning because of these sessions (you win some, you lose some, I guess). We started getting good results around the start of November, winning an old regional by solving all the problems in the 5th hour, and placing top 3 on a few other regionals as well. We started believing that we might have a fighting chance this year.
However, exam time was soon upon us in late November, and we temporarily stopped team practice completely. After the end of exams, Shriram and Tushar were somehow able to arrange temporary accomodations in their hostels, and with me living at home in Mumbai, we continued to practice in IIT-B itself until the time came to leave for Kharagpur.
NERC 2019-20 finals
Note: Contest analysis ahead. Try the problems in this contest here yourself before you read the following.
The above contest was a morale boost for us, as we performed quite well here. We were also using the contest environment by this point in all our contests, which meant - no pre-written code, and a single laptop for writing code. Actually, what we did is - only one person would write code on their laptop, while the others could only use their laptops for looking at code (basically the same as on-paper debugging).
Here is a short discussion of the above contest:
After the start of the contest, I started coding B immediately, as it was a cakewalk problem. I got a WA, and asked someone to look over my code. We found one error, and I submitted again, to get WA. Meanwhile, Shriram took over and started coding E, while I looked over my B and Tushar went over the other problems. I found my error, changed it and got AC, and in the next minute Shriram submitted as well, and we had 2 ACs in 32 minutes. This was an extremely slow start to the contest, and we were already behind.
Tushar got the idea for L and started coding it, while me and Shriram spent a good amount of time looking at K. I remember that I overcomplicated the problem a lot, using some dp ideas for number of matchings to get some idea which did not fit in the time limit. Meanwhile, Tushar failed on L and Shriram decided to help him debug. I started looking at other problems since I was unable to proceed on K. I got the idea for A immediately, which seemed to be a classical interval scheduling type problem with some casework. All of us looked at the problem and the universal consensus was that I should code this problem, as the other two were unsure of getting it right in the given time. However, it turned out that Tushar had already gotten the idea for J as well, so after ACing L he continued on to do J. With nothing better to do after Tushar ACed J, I got down to work on A.
Tushar and Shriram figured out that we were being idiots and missing a simple idea on K which finishes the problem, while I got our first WA on A. However, I quickly noted that most top teams failed a very early testcase on A, and I failed testcase 11 - meaning that I must be doing something right. Tushar started implementing K, and he got WA 3 times before he and Shriram corrected all the bugs and we got AC.
At this point, we had 5 ACs with 7 penalties and 2 hours 30 minutes had passed. We were way behind in the standings, and had lost all hope of doing well. However, we reckoned that we had nothing to lose, and these were situations we had to learn to deal with - in last year's Amritapuri regionals, we were near the top of the standings after half the contest, and proceeded to choke until the end to end up 24th. Thus, it was extremely crucial for us to be able to keep our morale and motivation high until the end of the contest to hope to win - a foreshadowing of events to come in the near future, indeed.
I got down to work on A, getting 3 more WAs in quick succession. Tushar took a look at F, which was a Prufer code problem. With Shriram, he was able to get a solution, which he wanted to code, but I told him to wait as I had some good idea on A. I corrected A, and submitted it - to get TLE on test 45! Clearly, my solution was just a bit too slow, and I needed to prune it a bit to pass in the time limit.
While I thought about how to do that in my mind, Tushar started with J, and the next few minutes were me intermittently changing something to submit, and he continuing to write J. I got 4 more WAs, with TLEs on testcase 49, and we were visibly frustated about what to do. I decided to write a heurestic-type change, which would not change the worst case for my algorithm but on average would be much faster. It was very unlikely that they would have actually found a worst case for what I had written, and voila - it passed! (with 545ms out of a 3s time limit, I may add). 10 minutes after my A, Tushar ACed J as well.
We celebrated quickly, and the standings had changed a bit. We were the top Indian team at this point, as it seemed the other teams had struggled with the harder problems, like F and A. We spent a while going through the problems left, and me and Tushar decided to go for G, while Shriram went for I. We spent 15-20 minutes getting a few observations, but getting nowhere to the complete solution. Meanwhile, Shriram said he was unable to complete I, and he was moving to D. I took a look at I, and it seemed exactly like my kind of problem. I told Tushar to look at G and Shriram to look at D, while I would solve I.
While I was thinking about I, Tushar gave up on G and joined me on I as well, as it seemed much more doable than G. I told him my thoughts - the small cases seemed to offer an insight into the problem. Greedy solutions clearly didn't work - it failed for n = 3 or 4. How do we solve this?
Suddenly, an idea struck me - how do we find the kth largest number in O(n) time? The standard quicksort algorithm works - find medians of the first 5 numbers, etc (If you are unaware of this, see the algorithm here). Thus, why not divide everything into pairs, then compare the top ones and the bottom ones in some way?
Me and Tushar started getting excited as this did seem to lead to a legit solution. Shriram said he also had progress on D which might lead to a solution. Tushar started coding the solution up while I told him the details, as I was more familiar with what the algorithm should look like, and we didn't want to make any mistakes. We coded it up to get a wrong answer on test 1, which was bemusing. We changed something, and got a wrong answer on test 1 again - why? It seemed that we made a bug with 0-indexing and 1-indexing, and submitted it again to get AC with no penalties - as fails on test 1 are not counted as penalties!
Tushar started helping Shriram on D, while I took a look at G. Shriram finished the code in 10 minutes, but had some bugs, and I was dreading that we wouldn't complete before the end of the contest. I also started looking at D and the code.
Shriram finished debugging 4 minutes before the end of the round, and submitted. We sat and looked at the progress with bated breath. Testcase 4,5,6... WA on 7. Damn.
Shriram cussed and started looking at the code quickly. He changed something and resubmitted to get WA7 again, and with that, the contest ended. It was still a very good result for us (definitely not time-wise, but number of problems solved-wise), but an AC on D would have been cherry on the cake.
We spent a few minutes looking at other problems and comments by teams who had done problems we couldn't, while Shriram found the bug in D. He submitted, and it indeed AC-ed!
Thus, this contest was a turning point for us, where we actually maintained our composure despite a very bad start to end up in a decent place at the end.
The start of the Trip
We woke at 4 am in the morning and got into the train at 6 am on the big day. We were going to take a 40-hour train journey to reach Kharagpur, which promised to be boring. However, I met an old friend in the train, and it turned out to be a fine journey after all!
The 4 of us took a manual rickshaw (i.e, someone pulled us) to the IIT campus (yes, apparently they don't have gas vehicles there - a bit of a shocker to us!). Soon enough, we reached the campus and almost immediately all three of us were sprawled on the floor, trying to get some sleep. A note about the accomodations - there were 2 beds in 1 room for 3 people, on the floor - so it was a bit uncomfortable, also with all the mosquitos around. However, it was still livable, and the food was quite decent.
Later in th evening, we spent some time formatting our notebook, and did some practice problems as well. We made friends with another team quite quickly - "Team Breadjam", from NIT Silchar. Soon, it was evening, we found a decent place to grab dinner, and we decided to get some sleep.
Next morning, it was finally time for official registrations and notebook submission. I helped our friends out with formatting their notebook, as we were already done with our final changes the day before. After registration, I decided to chill by stretching on the grass, and at some point ended up playing chess with some other team's players. Since our team didn't get any pictures last year, we decided to overcompensate this year by making sure to get pictures of everything.
As quick as that, it was time for lunch, and then the practice round! We decided to split the practice time between us to get a good feel of the keyboard by typing out our templates.
During the practice round, we had a team right behind us who were typing out templates at breakneck speed. This really affected the concentration of my teammates, as it seemed like they were implementing suffix structures by memory, which none of us could do in a short time without prewritten code. We just hoped that it wouldn't matter much tomorrow (spoiler: it didn't). By the time the practice round ended, there were barely a few teams left.
After the practice round, we headed to a Codechef session to know about the rules for the contest - in case there was something interesting in there this year. While Anup was talking about the various initiatives of Codechef (aka mostly irrelevant to us), looking through my folder I realized that I may have forgotten our food coupons at our room. Considering that Kharagpur is the biggest IIT, it was definitely a feat to get to our room and back with our coupons in time for dinner, and none of us was willing to do it.
Me and Tushar teamed up to pressure Shriram to get the coupons, and Shriram being the good sport he is, he accepted and left to get our tickets to a full stomach. Just as he left, Anup said that there would be an interactive problem and I got somewhat excited, as I considered us to be strong in these type of problems. Tushar commented that we should go through parallel binary search once again after returning to the room, and just then, I finally found the coupons - lying in the middle of papers in my folder!
Finally checking our phones to contact Shriram, we saw that both of us had multiple missed calls from him - he had reached and found nothing there! I called him to let him know that we had the coupons, and he was extremely bemused, as anyone would be. To his credit, he was very cool about the whole thing, except that a consensus was reached that I would not be in charge of coupons for this and any future trips to occur.
Finally, we had a good dinner, and left to get some practice and sleep before the main event.
ICPC Kharagpur 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.
As the contest started, we were extremely nervous. We either had to come first, or come in the top five to qualify for Asia West finals - there was absolutely no in-between. This was all or bust.
We had about 20 minutes to allow us to write down our code snippets that we would use during the contest. I quickly typed out our template, and we decided to write Disjoint Set Union, a power function with MOD operations and a segment tree implementation before the event, as these seemed to be the most likely to actually appear. We had decided on a rough strategy before - I would do maybe the first two problems, around which point Shriram/Tushar would have done some medium problems, and all problems after the first few would have one person overseeing the code, in case of doubts (called "pair programming").
1st hour
As the contest starts, I am on the computer with Tushar and Shriram going through the printouts. I quickly notice that WALKFAST seems like a Div 2A problem, with a simple if-else condition to check. I code it up quickly and go through the code once. I submit and we get the first AC of the contest! We quickly celebrate and throw the printout of the question down (This is to save time finding questions later).
I start looking at the other questions, and for a few minutes we don't solve anything else. Shriram asks me to look at MAXDIVER, and I see that people have already solved MAXDIVER and BALLCOL as well. MAXDIVER seems like a simple problem of the level of Div 2B, where we need to sort the array and change values accordingly. The main observation is that diversity increases the most when you change the value of an element from a group with the maximum number of equal values. I quickly code this up with Tushar looking on, and I submit to get AC.
Shriram is looking at AWKMINI, and Tushar looks at RANDID while I look at BALLCOL. I find a weird solution, but then me and Tushar simultaneously realize that we can do what I was thinking of in sorted order. Thus, the difficulty is a Div 2B at best, and he ends up coding it. As both he and Shriram have had a go at AWKMINI, I start working on that problem while Tushar gets AC, and both of them start working on RANDID.
I bounce a few ideas off them for AWKMINI, but then they get some idea for RANDID (which seems like a Div 2C-2D problem) and start furiously jotting down the math. I just start coding up my idea for AWKMINI (another Div 2C - 2D problem) - if this doesn't work, it will take us more than 20 minutes to come up with another solution anyway - so there's no harm in trying this out. Tushar takes over and starts coding RANDID as he has a simple formula for the answer. He gets AC on the problem, and he starts looking at ANAJOBS. Meanwhile, Shriram is looking at SEGDIR2 (cannot be classified in codeforces rating, as this is geometry - but maybe Div 2D for the idea, and 2E for the implementation).
2nd hour
I finish my code for AWKMINI, test it a bit, and submit it, expecting WA. To my pleasant surprise, we get AC and with 5 problems in our pocket without penalties in 70 minutes, we are second on the leaderboard. Tushar starts looking at RECARR (a Div 2D problem), which really seems like some easy problem which can be solved with randomization - the constraints really point towards that. I talk to Shriram and surprisingly, it seems that he solved SEGDIR2 almost immediately - it is just 2-SAT rephrased with line segment intersection.
Since I am the only one on the team who has done problems on geometry recently, I volunteer to code this up when we have nothing left to solve and some free computer time. I start copying some of our template geometry code already, when Tushar says that he thinks he has ANAJOBS. I immediately move out and start working on RECARR, which seems like the next problem we should solve. Shriram starts working on BALLSUM, where I point out we should find the answer for all colours seperately in a subset, and then sum over all subsets. We try rewriting this in a series, but we are unsuccessful.
3rd hour
Tushar gets AC on ANAJOBS, and we are 3rd, Laila having overtaken us in the meanwhile. I continue to code SEGDIR2 while Tushar and Shriram look at BALLSUM and GRAPHCON. I finish coding, ask Tushar to look over my code, and submit with a short prayer to god. It WAs, and we groan - our first WA of the contest. I find a bug almost immediately - I had copied the template incorrectly at a place, and I change it to resubmit. This also gets WA - I print out the code and start looking at it piece-by-piece. I find a few bugs, while Shriram starts coding GRAPHCON with Tushar looking on. They get WA, and they immediately print and start looking for bugs while I correct my code to resubmit. I get WA, and they have found the bug - they forgot to print the output, which was not in the samples!
They add this, and indeed - we get AC! Temporarily buoyed, they begin doing BALLSUM while I am left to deal with the broken remnants of my SEGDIR2 code.
4th hour
Shriram gets an idea for VARMIN, which Tushar helps complete - it is some sort of line sweep from left to right, taking the elements which are closest. I allow him to take over once again, and I start looking at RECARR once again. The scoreboard situation is grim - FacelessMen has done 10 problems, whereas we have done 7 so far, with Laila on 8 as well - we are 3rd on the leaderboard. I calculate that if I can correct SEGDIR2 and Tushar can AC VARMIN, and Shriram can solve BALLSUM - I still need to do RECARR, since there is no chance that the other teams miss SEGDIR2, as it is a very easy problem.
Shriram also looks over the code of SEGDIR2, while I do RECARR, not understanding what is wrong with SEGDIR2. Meanwhile, Tushar ACs VARMIN in the first try! I immediately take to the computer to test some bug I found on SEGDIR2, and now I reread the entire code again. It seems absolutely perfect to me. I submit, and another WA. Now, I am seriously confused as to what is going on.
5th hour
It is the final hour, and the leaderboard has frozen. We are in 3rd place with 8 problems, whereas both FacelessMen and Laila have solved 10 problems - they have solved BALLSUM and RECARR, which we haven't. However, since we expect them to solve SEGDIR2, in effect they have done 11 problems in our minds.
Tushar starts furiously working on BALLSUM and sees that it is a convolution. I code up the FFT and he adds a few lines of code, and we get another AC. He looks at my SEGDIR2, and cannot find any mistake as well. With just a few minutes left, I change a few things and keep submitting SEGDIR2, hoping to get AC, but we end up getting around 11 WAs on this problem instead.
Aftermath
Immediately after the contest, lunch is provided. All 3 of us are in a bad mood, and I feel extremely guilty for missing what should have been the problem that should have given us a lead. But since we also missed RECARR, it seems that it didn't matter that much, and to their credit my teammates don't blame me.
Yash from FacelessMen confirms that they did do 11 problems, and it turns out that RECARR has an extremely simple randomized solution. All 3 of us hang our heads in shame for a few moments - this is one of those problems where we should have really gotten the solution. We quickly eat lunch and head back to our room for some well-deserved rest before problem discussion.
As we head back, Tushar asks me why my method of solving 2-SAT works. Basically, what had happened is - I had told him to code up 2-SAT by telling him the way you solve it, and proceeded to do something else. I think about it and realize that it doesn't - and that was the mistake! All 3 of us didn't question this obviously wrong idea, even when we had gone through the code multiple times. We shake our heads and just hope that we placed top - 3.
i.d.
Sitting in our rooms, I see that Codechef is livestreaming KGP problem discussion! I fail to understand - we hadn't been informed about this! I convince my teammates that we should go, as I've heard that sometimes they start prize distribution early, and we shouldn't miss that.
We reach the problem discussion arena almost as soon as they are wrapping up. Jatin asks if anyone has any comments, and I immediately pipe up to say that I did not enjoy the geometry problem. As the adage goes: "If you can't solve em, criticize 'em". 😛
It is abundantly clear that FacelessMen has won, no matter how hard Codechef tries to keep an atmosphere of mystery - and literally everyone in the room knows it. They do start the prize distribution ceremony, and we wait with bated breath - it turns out that we do end up 3rd, with 9 problems!
Hello everyone, I'm back with the second part of this 4-part series. This will be significantly longer than the last post, as there are a lot more things to describe here. So, let's get right into it!
After the qualification round, we had vowed to practice more for the upcoming regionals - we knew we had a chance, however slight, of actually qualifying for WF. However, there were some changes in the WF selection criteria this year. You could go to upto 2 regionals out of 4, and only the top team from each regional would be selected. Around 40 top teams in total would be invited to Asia West as well, to decide the Asia West champions and also to offer additional WF slots.
We came to know about these changes before applying for regionals, and accordingly we choose Kharagpur and Amritapuri regionals - Kharagpur because it was the weakest field of any regional according to the people who were planning to attend, and Amritapuri in case we did badly in the online round, since with good probability they will choose teams on merit. Thus, it turned out that our first regional was Kharagpur, to be held on 7th December.
It turned out that all 3 of us had sufficiently different schedules such that we usually had practice sessions available only from 10pm - 3am, and post-contest discussions from 3am - 5 or 6am, and thus it turns out that I missed some classes in the morning because of these sessions (you win some, you lose some, I guess). We started getting good results around the start of November, winning an old regional by solving all the problems in the 5th hour, and placing top 3 on a few other regionals as well. We started believing that we might have a fighting chance this year.
However, exam time was soon upon us in late November, and we temporarily stopped team practice completely. After the end of exams, Shriram and Tushar were somehow able to arrange temporary accomodations in their hostels, and with me living at home in Mumbai, we continued to practice in IIT-B itself until the time came to leave for Kharagpur.
NERC 2019-20 finals
Note: Contest analysis ahead. Try the problems in this contest here yourself before you read the following.
The above contest was a morale boost for us, as we performed quite well here. We were also using the contest environment by this point in all our contests, which meant - no pre-written code, and a single laptop for writing code. Actually, what we did is - only one person would write code on their laptop, while the others could only use their laptops for looking at code (basically the same as on-paper debugging).
Here is a short discussion of the above contest:
After the start of the contest, I started coding B immediately, as it was a cakewalk problem. I got a WA, and asked someone to look over my code. We found one error, and I submitted again, to get WA. Meanwhile, Shriram took over and started coding E, while I looked over my B and Tushar went over the other problems. I found my error, changed it and got AC, and in the next minute Shriram submitted as well, and we had 2 ACs in 32 minutes. This was an extremely slow start to the contest, and we were already behind.
Tushar got the idea for L and started coding it, while me and Shriram spent a good amount of time looking at K. I remember that I overcomplicated the problem a lot, using some dp ideas for number of matchings to get some idea which did not fit in the time limit. Meanwhile, Tushar failed on L and Shriram decided to help him debug. I started looking at other problems since I was unable to proceed on K. I got the idea for A immediately, which seemed to be a classical interval scheduling type problem with some casework. All of us looked at the problem and the universal consensus was that I should code this problem, as the other two were unsure of getting it right in the given time. However, it turned out that Tushar had already gotten the idea for J as well, so after ACing L he continued on to do J. With nothing better to do after Tushar ACed J, I got down to work on A.
Tushar and Shriram figured out that we were being idiots and missing a simple idea on K which finishes the problem, while I got our first WA on A. However, I quickly noted that most top teams failed a very early testcase on A, and I failed testcase 11 - meaning that I must be doing something right. Tushar started implementing K, and he got WA 3 times before he and Shriram corrected all the bugs and we got AC.
At this point, we had 5 ACs with 7 penalties and 2 hours 30 minutes had passed. We were way behind in the standings, and had lost all hope of doing well. However, we reckoned that we had nothing to lose, and these were situations we had to learn to deal with - in last year's Amritapuri regionals, we were near the top of the standings after half the contest, and proceeded to choke until the end to end up 24th. Thus, it was extremely crucial for us to be able to keep our morale and motivation high until the end of the contest to hope to win - a foreshadowing of events to come in the near future, indeed.
I got down to work on A, getting 3 more WAs in quick succession. Tushar took a look at F, which was a Prufer code problem. With Shriram, he was able to get a solution, which he wanted to code, but I told him to wait as I had some good idea on A. I corrected A, and submitted it - to get TLE on test 45! Clearly, my solution was just a bit too slow, and I needed to prune it a bit to pass in the time limit.
While I thought about how to do that in my mind, Tushar started with J, and the next few minutes were me intermittently changing something to submit, and he continuing to write J. I got 4 more WAs, with TLEs on testcase 49, and we were visibly frustated about what to do. I decided to write a heurestic-type change, which would not change the worst case for my algorithm but on average would be much faster. It was very unlikely that they would have actually found a worst case for what I had written, and voila - it passed! (with 545ms out of a 3s time limit, I may add). 10 minutes after my A, Tushar ACed J as well.
We celebrated quickly, and the standings had changed a bit. We were the top Indian team at this point, as it seemed the other teams had struggled with the harder problems, like F and A. We spent a while going through the problems left, and me and Tushar decided to go for G, while Shriram went for I. We spent 15-20 minutes getting a few observations, but getting nowhere to the complete solution. Meanwhile, Shriram said he was unable to complete I, and he was moving to D. I took a look at I, and it seemed exactly like my kind of problem. I told Tushar to look at G and Shriram to look at D, while I would solve I.
While I was thinking about I, Tushar gave up on G and joined me on I as well, as it seemed much more doable than G. I told him my thoughts - the small cases seemed to offer an insight into the problem. Greedy solutions clearly didn't work - it failed for n = 3 or 4. How do we solve this?
Suddenly, an idea struck me - how do we find the kth largest number in O(n) time? The standard quicksort algorithm works - find medians of the first 5 numbers, etc (If you are unaware of this, see the algorithm here). Thus, why not divide everything into pairs, then compare the top ones and the bottom ones in some way?
Me and Tushar started getting excited as this did seem to lead to a legit solution. Shriram said he also had progress on D which might lead to a solution. Tushar started coding the solution up while I told him the details, as I was more familiar with what the algorithm should look like, and we didn't want to make any mistakes. We coded it up to get a wrong answer on test 1, which was bemusing. We changed something, and got a wrong answer on test 1 again - why? It seemed that we made a bug with 0-indexing and 1-indexing, and submitted it again to get AC with no penalties - as fails on test 1 are not counted as penalties!
Tushar started helping Shriram on D, while I took a look at G. Shriram finished the code in 10 minutes, but had some bugs, and I was dreading that we wouldn't complete before the end of the contest. I also started looking at D and the code.
Shriram finished debugging 4 minutes before the end of the round, and submitted. We sat and looked at the progress with bated breath. Testcase 4,5,6... WA on 7. Damn.
Shriram cussed and started looking at the code quickly. He changed something and resubmitted to get WA7 again, and with that, the contest ended. It was still a very good result for us (definitely not time-wise, but number of problems solved-wise), but an AC on D would have been cherry on the cake.
We spent a few minutes looking at other problems and comments by teams who had done problems we couldn't, while Shriram found the bug in D. He submitted, and it indeed AC-ed!
Thus, this contest was a turning point for us, where we actually maintained our composure despite a very bad start to end up in a decent place at the end.
The start of the Trip
We woke at 4 am in the morning and got into the train at 6 am on the big day. We were going to take a 40-hour train journey to reach Kharagpur, which promised to be boring. However, I met an old friend in the train, and it turned out to be a fine journey after all!
The 4 of us took a manual rickshaw (i.e, someone pulled us) to the IIT campus (yes, apparently they don't have gas vehicles there - a bit of a shocker to us!). Soon enough, we reached the campus and almost immediately all three of us were sprawled on the floor, trying to get some sleep. A note about the accomodations - there were 2 beds in 1 room for 3 people, on the floor - so it was a bit uncomfortable, also with all the mosquitos around. However, it was still livable, and the food was quite decent.
Later in th evening, we spent some time formatting our notebook, and did some practice problems as well. We made friends with another team quite quickly - "Team Breadjam", from NIT Silchar. Soon, it was evening, we found a decent place to grab dinner, and we decided to get some sleep.
Next morning, it was finally time for official registrations and notebook submission. I helped our friends out with formatting their notebook, as we were already done with our final changes the day before. After registration, I decided to chill by stretching on the grass, and at some point ended up playing chess with some other team's players. Since our team didn't get any pictures last year, we decided to overcompensate this year by making sure to get pictures of everything.
From left to right: Tushar, Shriram, me
As quick as that, it was time for lunch, and then the practice round! We decided to split the practice time between us to get a good feel of the keyboard by typing out our templates.
During the practice round, we had a team right behind us who were typing out templates at breakneck speed. This really affected the concentration of my teammates, as it seemed like they were implementing suffix structures by memory, which none of us could do in a short time without prewritten code. We just hoped that it wouldn't matter much tomorrow (spoiler: it didn't). By the time the practice round ended, there were barely a few teams left.
After the practice round, we headed to a Codechef session to know about the rules for the contest - in case there was something interesting in there this year. While Anup was talking about the various initiatives of Codechef (aka mostly irrelevant to us), looking through my folder I realized that I may have forgotten our food coupons at our room. Considering that Kharagpur is the biggest IIT, it was definitely a feat to get to our room and back with our coupons in time for dinner, and none of us was willing to do it.
Me and Tushar teamed up to pressure Shriram to get the coupons, and Shriram being the good sport he is, he accepted and left to get our tickets to a full stomach. Just as he left, Anup said that there would be an interactive problem and I got somewhat excited, as I considered us to be strong in these type of problems. Tushar commented that we should go through parallel binary search once again after returning to the room, and just then, I finally found the coupons - lying in the middle of papers in my folder!
Finally checking our phones to contact Shriram, we saw that both of us had multiple missed calls from him - he had reached and found nothing there! I called him to let him know that we had the coupons, and he was extremely bemused, as anyone would be. To his credit, he was very cool about the whole thing, except that a consensus was reached that I would not be in charge of coupons for this and any future trips to occur.
Finally, we had a good dinner, and left to get some practice and sleep before the main event.
In high spirits on the morning of the contest
All of us woke very early, around 6 am on the morning of the contest - even Tushar, for which this is highly unusual (possibly could be classified as suspicious activity), woke by 7 am. We decided to take a group photo for luck before heading to meet destiny head-on.
ICPC Kharagpur 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.
As the contest started, we were extremely nervous. We either had to come first, or come in the top five to qualify for Asia West finals - there was absolutely no in-between. This was all or bust.
We had about 20 minutes to allow us to write down our code snippets that we would use during the contest. I quickly typed out our template, and we decided to write Disjoint Set Union, a power function with MOD operations and a segment tree implementation before the event, as these seemed to be the most likely to actually appear. We had decided on a rough strategy before - I would do maybe the first two problems, around which point Shriram/Tushar would have done some medium problems, and all problems after the first few would have one person overseeing the code, in case of doubts (called "pair programming").
1st hour
As the contest starts, I am on the computer with Tushar and Shriram going through the printouts. I quickly notice that WALKFAST seems like a Div 2A problem, with a simple if-else condition to check. I code it up quickly and go through the code once. I submit and we get the first AC of the contest! We quickly celebrate and throw the printout of the question down (This is to save time finding questions later).
I start looking at the other questions, and for a few minutes we don't solve anything else. Shriram asks me to look at MAXDIVER, and I see that people have already solved MAXDIVER and BALLCOL as well. MAXDIVER seems like a simple problem of the level of Div 2B, where we need to sort the array and change values accordingly. The main observation is that diversity increases the most when you change the value of an element from a group with the maximum number of equal values. I quickly code this up with Tushar looking on, and I submit to get AC.
Shriram is looking at AWKMINI, and Tushar looks at RANDID while I look at BALLCOL. I find a weird solution, but then me and Tushar simultaneously realize that we can do what I was thinking of in sorted order. Thus, the difficulty is a Div 2B at best, and he ends up coding it. As both he and Shriram have had a go at AWKMINI, I start working on that problem while Tushar gets AC, and both of them start working on RANDID.
I bounce a few ideas off them for AWKMINI, but then they get some idea for RANDID (which seems like a Div 2C-2D problem) and start furiously jotting down the math. I just start coding up my idea for AWKMINI (another Div 2C - 2D problem) - if this doesn't work, it will take us more than 20 minutes to come up with another solution anyway - so there's no harm in trying this out. Tushar takes over and starts coding RANDID as he has a simple formula for the answer. He gets AC on the problem, and he starts looking at ANAJOBS. Meanwhile, Shriram is looking at SEGDIR2 (cannot be classified in codeforces rating, as this is geometry - but maybe Div 2D for the idea, and 2E for the implementation).
2nd hour
I finish my code for AWKMINI, test it a bit, and submit it, expecting WA. To my pleasant surprise, we get AC and with 5 problems in our pocket without penalties in 70 minutes, we are second on the leaderboard. Tushar starts looking at RECARR (a Div 2D problem), which really seems like some easy problem which can be solved with randomization - the constraints really point towards that. I talk to Shriram and surprisingly, it seems that he solved SEGDIR2 almost immediately - it is just 2-SAT rephrased with line segment intersection.
Since I am the only one on the team who has done problems on geometry recently, I volunteer to code this up when we have nothing left to solve and some free computer time. I start copying some of our template geometry code already, when Tushar says that he thinks he has ANAJOBS. I immediately move out and start working on RECARR, which seems like the next problem we should solve. Shriram starts working on BALLSUM, where I point out we should find the answer for all colours seperately in a subset, and then sum over all subsets. We try rewriting this in a series, but we are unsuccessful.
3rd hour
Tushar gets AC on ANAJOBS, and we are 3rd, Laila having overtaken us in the meanwhile. I continue to code SEGDIR2 while Tushar and Shriram look at BALLSUM and GRAPHCON. I finish coding, ask Tushar to look over my code, and submit with a short prayer to god. It WAs, and we groan - our first WA of the contest. I find a bug almost immediately - I had copied the template incorrectly at a place, and I change it to resubmit. This also gets WA - I print out the code and start looking at it piece-by-piece. I find a few bugs, while Shriram starts coding GRAPHCON with Tushar looking on. They get WA, and they immediately print and start looking for bugs while I correct my code to resubmit. I get WA, and they have found the bug - they forgot to print the output, which was not in the samples!
Shriram ends up coding one problem in this contest, and luckily for him, that's when they choose to take our photo!
P.S. Shriram is an extremely good looking guy who always has your back, with an amazing outlook on life. He is also not in a relationship currently. He most certainly did not ask me to write this.
P.S. Shriram is an extremely good looking guy who always has your back, with an amazing outlook on life. He is also not in a relationship currently. He most certainly did not ask me to write this.
They add this, and indeed - we get AC! Temporarily buoyed, they begin doing BALLSUM while I am left to deal with the broken remnants of my SEGDIR2 code.
4th hour
Shriram gets an idea for VARMIN, which Tushar helps complete - it is some sort of line sweep from left to right, taking the elements which are closest. I allow him to take over once again, and I start looking at RECARR once again. The scoreboard situation is grim - FacelessMen has done 10 problems, whereas we have done 7 so far, with Laila on 8 as well - we are 3rd on the leaderboard. I calculate that if I can correct SEGDIR2 and Tushar can AC VARMIN, and Shriram can solve BALLSUM - I still need to do RECARR, since there is no chance that the other teams miss SEGDIR2, as it is a very easy problem.
Shriram also looks over the code of SEGDIR2, while I do RECARR, not understanding what is wrong with SEGDIR2. Meanwhile, Tushar ACs VARMIN in the first try! I immediately take to the computer to test some bug I found on SEGDIR2, and now I reread the entire code again. It seems absolutely perfect to me. I submit, and another WA. Now, I am seriously confused as to what is going on.
5th hour
It is the final hour, and the leaderboard has frozen. We are in 3rd place with 8 problems, whereas both FacelessMen and Laila have solved 10 problems - they have solved BALLSUM and RECARR, which we haven't. However, since we expect them to solve SEGDIR2, in effect they have done 11 problems in our minds.
Tushar starts furiously working on BALLSUM and sees that it is a convolution. I code up the FFT and he adds a few lines of code, and we get another AC. He looks at my SEGDIR2, and cannot find any mistake as well. With just a few minutes left, I change a few things and keep submitting SEGDIR2, hoping to get AC, but we end up getting around 11 WAs on this problem instead.
Aftermath
Immediately after the contest, lunch is provided. All 3 of us are in a bad mood, and I feel extremely guilty for missing what should have been the problem that should have given us a lead. But since we also missed RECARR, it seems that it didn't matter that much, and to their credit my teammates don't blame me.
Yash from FacelessMen confirms that they did do 11 problems, and it turns out that RECARR has an extremely simple randomized solution. All 3 of us hang our heads in shame for a few moments - this is one of those problems where we should have really gotten the solution. We quickly eat lunch and head back to our room for some well-deserved rest before problem discussion.
As we head back, Tushar asks me why my method of solving 2-SAT works. Basically, what had happened is - I had told him to code up 2-SAT by telling him the way you solve it, and proceeded to do something else. I think about it and realize that it doesn't - and that was the mistake! All 3 of us didn't question this obviously wrong idea, even when we had gone through the code multiple times. We shake our heads and just hope that we placed top - 3.
i.d.
Sitting in our rooms, I see that Codechef is livestreaming KGP problem discussion! I fail to understand - we hadn't been informed about this! I convince my teammates that we should go, as I've heard that sometimes they start prize distribution early, and we shouldn't miss that.
We reach the problem discussion arena almost as soon as they are wrapping up. Jatin asks if anyone has any comments, and I immediately pipe up to say that I did not enjoy the geometry problem. As the adage goes: "If you can't solve em, criticize 'em". 😛
It is abundantly clear that FacelessMen has won, no matter how hard Codechef tries to keep an atmosphere of mystery - and literally everyone in the room knows it. They do start the prize distribution ceremony, and we wait with bated breath - it turns out that we do end up 3rd, with 9 problems!
It may not have been our best performance, but it felt good.
There are a few positives from this contest - We realize that we have qualified for Asia West finals already, so in Amritapuri regionals only winning matters for us, which is great - because it is a low pressure situation (i.e., all or bust). I swear to shave before our next contest, and I claim that it is a certainty that we didn't win because I forgot to shave. Shriram strongly feels it is because we did not listen to enough K-pop, and we take a solemn oath to devote ourselves to K-pop until the end of regionals. Tushar takes it particularly seriously, with his internship in Samsung Korea coming up as well. We have some fun on the train back, messing around and discussing many problems in preparation for the next regionals.
We say bye to Shriram, as he is heading back home for a short while, while Tushar has decided to stay over at my place to practice. Shriram also plans to come to my home after a while, so that we can stay at the same place and practice without any other worries. We recognize that our dreams are now a truly possible reality - only time will tell.
It was awesome Sir 👍
ReplyDeleteWaiting for next part if you are going to write it !
ReplyDelete