Hello everyone,
Today, I'll be writing on the journey to qualifying for the ICPC World Finals 2020. This blogpost has been on my mind for a while, but we have been thinking of delaying it uptil after the actual world finals. However, with the coronavirus crisis going on, I thought it'd be a good time to get my (our) thoughts on paper while they're still relatively fresh in our minds!
I'll be talking about a few things in this post (it will be long) - How we prepared, our emotions and problem solving strategy during the contest (a replay, if you will). I will mostly cover the entire India ICPC cycle from October 2019 to January 2020. First, let's get a bit of background in our team structure:
1) Shubham - A 3rd year electrical engineering student.
Strengths: Fast to solve problems, good typing speed, maths background.
Weaknesses: Doesn't code heavy datastructures much, lacks knowledge in this area. Not comfortable with HLD/Centroid or suffix structures
2) Shriram - A 3rd year electrical engineering student.
Strengths: Can think of weird solutions which turn out to be correct.
Weaknesses: Does not practice writing code much. Sometimes this leads to hard-to-find bugs.
3) Tushar - A 3rd year computer science student.
Strengths: Can code hard and lengthy data structures. Has practiced many hard problems.
Weaknesses: Does not practice writing code much. Finds it very hard to parse problem statements and many times makes mistakes due to this. Form is somewhat variable.
So now you have a rough idea of our team structure. Our team is named "BhagwanBharose", which roughly translates to "dependent on god", which was exactly our mindset going in!
The first leg of the ICPC cycle was the Preliminary online qualifications on 18th October. We all gather in Shriram's room for the contest, with some nervous energy. The qualification was a bad experience for us in 2018 - we messed up a bit and ended up 84th, which was enough to only allow us to qualify for 1 regional. We haven't practiced for over a month as a team now, which means that we dread it will happen yet again. To lighten the mood, I put on some Korean pop (which both Shriram and Tushar consider their religion) and start doing some weird dance moves, and all of us end up getting pumped up for half an hour with Twice on full blast. Literally, this IS our entire preparation, I muse silently.
Qualification Round Replay
The above contest can be found here
The online contest starts and we're in. I immediately look at the first few problems. It takes me a few minutes to realize the easiest problem, which is TRAINSET. I code it up quickly, and spend a minute re-reading the code (We learnt the hard way that morale really matters at the beginning. You want to spend a minute more and get AC instead of getting WA then AC). I think it looks correct, and it ACs.
Meanwhile, Shriram does DISCSHOP which ACs, and I tell Tushar about PENS, which seems to me a simple bitmask question. He understands and starts coding it up, while I look at SEGDIR. I get it in 10 minutes and it ACs as well. I look at BEAUTPAR and Shriram starts trying SPS, which seems to be the hardest question in the contest. Both me and Tushar encourage him to do so because the other problems seem very our-style and we should dispose of them quickly enough.
I get the idea for BEAUTPAR quickly, and I know it's something of the LIS sort - you take the prefix sums, and try to find an LIS (with starting value 0), and if this LIS length >= k, you have your desired sequence. However, it seems he is still doing PENS. I decide to get a look at SUMOR. I get a greedy idea, and I tell it to Shriram. He agrees that it looks natural, and I decide to code it and test it out. It gets AC, and we celebrate quickly.
Tushar gets a WA on PENS and I decide to look at the code as I know the solution. It turns out he had missed a part of the solution I had in mind, and we correct that and get AC. I explain BEAUTPAR to him, and he starts coding it immediately. Meanwhile, I look at SPS, and Shriram moves to SHUFGRID.
It turns out that SHUFGRID is just a problem about maintaining some states in a markov chain type structure. Put simply, there are a few states - at the current square, in the same row, in the same column, and not in the same row or column. We just need to calculate transitions in these states.
I spend 30 minutes on SPS, not getting anywhere. Then, I start throwing everything and the kitchen sink at the problem, just trying out a lot of things and hoping that it gives the minimum. Meanwhile, 2 hours into the 3 hour contest, both Shriram and Tushar AC their problems, and we have 7 out of 8 with an hour to go. Both of them join me in SPS, where I already have a WA previously.
They find a case or two I missed, and I add some cases to cover that. I start adding more and more cases, and eventually I have some long code which works on every example we dream of. I keep submitting and getting WAs, and we don't solve it till the end of the contest. I think we have 9 WAs on this problem.
We end up 9th, which seems okay to us considering how rusty we are. We briefly celebrate with our friend Pranay, and vow to practice more from now on. Around 20 minutes later, my friends message me asking about my solution to SUMOR, saying that someone posted a counter-case on the forum which invalidates most solutions. I look at it, and my stomach sinks. It indeed fails our solution. I begin to get worried, wondering if we will only get to go to one regional again. I immediately call up other friends, and it turns out, their solutions fail too.
Soon, it turns out that there was a problem with the model solution, and thus this problem will be removed. After the ranklist released, we realize that we make both regionals anyway, thus it doesn't matter!
Anyway, this concludes part 1 of the blog. I decided to break this blog into 4 parts, wrt the 4 official contests we took part in this season, and also to increase anticipation. See you soon!
Today, I'll be writing on the journey to qualifying for the ICPC World Finals 2020. This blogpost has been on my mind for a while, but we have been thinking of delaying it uptil after the actual world finals. However, with the coronavirus crisis going on, I thought it'd be a good time to get my (our) thoughts on paper while they're still relatively fresh in our minds!
I'll be talking about a few things in this post (it will be long) - How we prepared, our emotions and problem solving strategy during the contest (a replay, if you will). I will mostly cover the entire India ICPC cycle from October 2019 to January 2020. First, let's get a bit of background in our team structure:
1) Shubham - A 3rd year electrical engineering student.
Strengths: Fast to solve problems, good typing speed, maths background.
Weaknesses: Doesn't code heavy datastructures much, lacks knowledge in this area. Not comfortable with HLD/Centroid or suffix structures
2) Shriram - A 3rd year electrical engineering student.
Strengths: Can think of weird solutions which turn out to be correct.
Weaknesses: Does not practice writing code much. Sometimes this leads to hard-to-find bugs.
3) Tushar - A 3rd year computer science student.
Strengths: Can code hard and lengthy data structures. Has practiced many hard problems.
Weaknesses: Does not practice writing code much. Finds it very hard to parse problem statements and many times makes mistakes due to this. Form is somewhat variable.
So now you have a rough idea of our team structure. Our team is named "BhagwanBharose", which roughly translates to "dependent on god", which was exactly our mindset going in!
The first leg of the ICPC cycle was the Preliminary online qualifications on 18th October. We all gather in Shriram's room for the contest, with some nervous energy. The qualification was a bad experience for us in 2018 - we messed up a bit and ended up 84th, which was enough to only allow us to qualify for 1 regional. We haven't practiced for over a month as a team now, which means that we dread it will happen yet again. To lighten the mood, I put on some Korean pop (which both Shriram and Tushar consider their religion) and start doing some weird dance moves, and all of us end up getting pumped up for half an hour with Twice on full blast. Literally, this IS our entire preparation, I muse silently.
Qualification Round Replay
The above contest can be found here
The online contest starts and we're in. I immediately look at the first few problems. It takes me a few minutes to realize the easiest problem, which is TRAINSET. I code it up quickly, and spend a minute re-reading the code (We learnt the hard way that morale really matters at the beginning. You want to spend a minute more and get AC instead of getting WA then AC). I think it looks correct, and it ACs.
Meanwhile, Shriram does DISCSHOP which ACs, and I tell Tushar about PENS, which seems to me a simple bitmask question. He understands and starts coding it up, while I look at SEGDIR. I get it in 10 minutes and it ACs as well. I look at BEAUTPAR and Shriram starts trying SPS, which seems to be the hardest question in the contest. Both me and Tushar encourage him to do so because the other problems seem very our-style and we should dispose of them quickly enough.
I get the idea for BEAUTPAR quickly, and I know it's something of the LIS sort - you take the prefix sums, and try to find an LIS (with starting value 0), and if this LIS length >= k, you have your desired sequence. However, it seems he is still doing PENS. I decide to get a look at SUMOR. I get a greedy idea, and I tell it to Shriram. He agrees that it looks natural, and I decide to code it and test it out. It gets AC, and we celebrate quickly.
Tushar gets a WA on PENS and I decide to look at the code as I know the solution. It turns out he had missed a part of the solution I had in mind, and we correct that and get AC. I explain BEAUTPAR to him, and he starts coding it immediately. Meanwhile, I look at SPS, and Shriram moves to SHUFGRID.
It turns out that SHUFGRID is just a problem about maintaining some states in a markov chain type structure. Put simply, there are a few states - at the current square, in the same row, in the same column, and not in the same row or column. We just need to calculate transitions in these states.
I spend 30 minutes on SPS, not getting anywhere. Then, I start throwing everything and the kitchen sink at the problem, just trying out a lot of things and hoping that it gives the minimum. Meanwhile, 2 hours into the 3 hour contest, both Shriram and Tushar AC their problems, and we have 7 out of 8 with an hour to go. Both of them join me in SPS, where I already have a WA previously.
They find a case or two I missed, and I add some cases to cover that. I start adding more and more cases, and eventually I have some long code which works on every example we dream of. I keep submitting and getting WAs, and we don't solve it till the end of the contest. I think we have 9 WAs on this problem.
We end up 9th, which seems okay to us considering how rusty we are. We briefly celebrate with our friend Pranay, and vow to practice more from now on. Around 20 minutes later, my friends message me asking about my solution to SUMOR, saying that someone posted a counter-case on the forum which invalidates most solutions. I look at it, and my stomach sinks. It indeed fails our solution. I begin to get worried, wondering if we will only get to go to one regional again. I immediately call up other friends, and it turns out, their solutions fail too.
Soon, it turns out that there was a problem with the model solution, and thus this problem will be removed. After the ranklist released, we realize that we make both regionals anyway, thus it doesn't matter!
Anyway, this concludes part 1 of the blog. I decided to break this blog into 4 parts, wrt the 4 official contests we took part in this season, and also to increase anticipation. See you soon!
Do you believe in God?
ReplyDelete