Today marks the conclusion of the November 2020 Challenge on CodeChef, yet here I am, over a month late, talking about the October one. During the first few weeks of October, I was very invested in the monthly challenges. In fact, I spent quite a large amount of time on top of the schoolwork I’m already responsible for at uWaterloo. Earlier in the year, I imagined it to be more straining than it turned out to be. It definitely was not the ideal situation; but, with online school, allocating time to watch lectures and complete deliverables was easier than it was in prior terms, and I think this was a significant factor. Additionally, I haven’t been playing as many games or consuming as much media (Instagram, Netflix, anime, etc.), and so I think I also improved in terms of personal time management. I didn’t time myself, but if I were to estimate the amount of time I spent on this month’s challenge, I would guess about 25-30 hours across the 10-day span. I personally think this is a significant amount, especially compared to previous monthly challenges that I have completed while under significantly less workload; however, a lot of it was due to the unexpectedly awesome question that I encountered in the middle of the contest that I thought was very intriguing.
1.5-Month Recap
Before I discuss my favourite question on the contest, I’ll briefly recap what I’ve been doing for the last month. I wanted to write this blog immediately after the contest’s completion. However, Google KickStart Round G was right around the corner and so I was doing some preparation for that. Although I didn’t get too much prep done (wanted to look into the minimax algorithm that was used to solve Q3 on the previous Kickstart as well as understand the DP approach that separates KickStart Round A Q2 from the 0/1 Knapsack problem), I’d say it was still helpful as I was able to solve a few simpler problems that boosted my confidence. I went in with the goal of still completing 2/4 questions; however, to my surprise, this turned out to be a somewhat “easier” contest. I mark easier in quotes because I was only able to get 2/3 test cases pass on Q3, and 1/3 on Q4. But, this was significantly better than last time. It clearly showed an improvement in time management skills as I had time to read, understand and implement partial solutions where possible. I would also say that the remaining test cases implored unique concepts that I don’t think I could resolve, regardless of the time given. I was able to score in the top 1000, which is a significant milestone for me. I still intend to work harder to fully solve Q3 next time. That time, however, will be next year. Google KickStart Round H was yesterday and I was quite busy with school and was not comfortable going into it half-prepared. I’m not sure how missing the last Kickstart of the year may affect my chances for applying to Google for my sixth and last coop. What’s even worse is that Kickstarts don’t start until March, so even if I am considered for an interview, it will be long before I have another chance to prove myself in their monthly contest. If I do undergo significant improvement, I hope it is similarly perceived by a recruiter on their end if I demonstrate growth on platforms like CodeForces and CodeChef. Anyways, after Google Kickstart Round G, a period of momentary laziness was swiftly followed by a never-ending stream of significant deliverables that took up most of my time. Add on-going interviews for the next coop term to the list and there was very little room for me to squeeze coding into the mix. I have not seriously practised coding for about two and a half weeks, and so I intended to exit that hiatus with the November 2020 Challenge.
October 2020 Challenge
At the start of October, I was still very motivated about monthly contests. I recall watching one of Rachit Jain’s videos where he praises the long challenges as they allowed him to explore more advanced topics that he otherwise would not be able to implement in a time-constrained contest. I shared that sentiment and wanted to do as well as I could. I ended up prioritizing this over school for a bit too. I recall that during the week, I had not attended any of my lectures. Instead, I was spending time debugging and reading about graph traversal algorithms to find the minimum spanning tree. I should mention that the following week was reading week, and so I was confident in my ability to catch up. But even I was surprised at the amount of time I invested into this contest. Most of the problems were straightforward in their implementation. I don’t recall using any notable DSA for the first 4. This changed when I reached the fifth problem. The link to the problem is here.
The reason I was so excited when I encountered this problem is because it was my first CP graph problem. The only graph problems I had successfully completed were simple tree problems on LeetCode, and the most had I learned about MSTs up to this point was Abdul Bari’s video discussing Kruskal’s and Prim’s algorithms to find the minimum spanning tree. I thought this was my chance to reap the benefits Rachit talking about earlier. I rewatched the Bari video in attempt to understand the approach but modify the implementation to to work for a maximum spanning tree. I arbitrarily decided to use Kruskal’s algorithm but either would have sufficed. I accordingly calculated all potential edges between all n nodes and stored them within a max heap for efficient retrieval time. When selecting the maximum edges, I used DFS for cycle-checking. I noticed a spike in my runtime and after a little research, I found a neat data structure called Union Find. I optimized it using path compression and noticed a significant jump in runtime for local tests. However, upon submission, I wasn’t even passing the first test case. I was certain that my implementation of Kruskal’s algorithm was fine, and so I suspected that my O(n2) complexity for edge weight calculation was the issue. I was also able to notice that in one dimension, all the final edges were those that connect a node to one of the extreme nodes (minimum or maximum value). Alas, I was not able to figure out how to extend this to work in D-dimensions and so I left it there. I learned, programmed and brainstormed quite a bit and I would be satisfied by reading the editorial.
Upon reading the tutorial the following Monday, I had mixed feelings. On one hand, I was excited that I had done so many things right. My implementation of Union Find was correct and I was also right to suspect that it was the weight calculation that was preventing me from achieving a successful submission. I was amazed at the trick used to find the potential “extreme nodes” that we should be connecting all other nodes to achieve the maximum spanning tree. I found this video to be quite helpful. Up to this point, I was quite happy with my effort and the results I got back. However, after this, I ran into quite a tedious problem. Even after implementing it in exactly as described by the editorial and this video, I continued to receive TLE flags from the online judge. Regardless of how much I optimized my Python code, I could not pass all the test cases. Suspecting the problem simply was not optimized for Python, I decided to temporarily switch to the mother tongue of CP: C++. Even here, I continued to face the same issue upon submission; the last test case refused to comply. At this point, I was truly lost because I implemented everything to the best of my ability while adhering to the structure given to me by the editorial. I went through an ungodly number of submissions by other coders, both in Python and C++, to see where I was going wrong, but I could not find make any progress. Considering I spent about 25 hours programming while the contest was live, without exaggeration, I can confidently say I spent even more than that going through other people’s submissions, watching YouTube videos and rereading the editorial multiple times after the contest was over in an attempt to get closure by receiving AC. Finally, I realized that in my C++ implementation, I was using vector<vector
November 2020 Challenge
Although the blog post is named after it, I actually have quite little to say about the November 2020 Challenge. I quickly solved three problems and found the fourth one to be quite tedious. Although an important part about CP is being able to handle problems such as that, I was more motivated to learn different DSAs and techniques. For this reason, I realized that the long challenges aren’t what I’m looking for at the moment. Although Rachit is right in saying that they give you time to research and implement new solutions, I think that the required time commitment is too high and I’m learning quite little for the amount of time I invested in it. With no editorial or solution to refer to for over 10 days, the contests became a time sink for me. In an ideal world, I would like to spend hours and hours on every problem and solve it without seeking external resources and help. However, starting CP so late as it is, it is important that I approach this journey with the goal of being efficient. In addition to this, I have started to pick up other hobbies that demand a large portion of my free time as well.
What’s next?
I think the first step for me to efficiently improve is to take a proper breadth-first dive into DSAs. I’ve heard many terms and buzzwords such as segment trees, bucket sort, etc. that I would at minimum like to understand superficially. This will give me a larger number of options to filter through when first approaching a problem, and if further research is required, I expect the learning curve to be more forgiving. At the moment, I would like to learn more about dynamic programming. Due to its high versatility, it is often used in many programming problems and it would be nice if I could consistently solve problems that demand it. I have experience using DP in simple problems where tabulation is performed with an array, but I’m very intrigued on how it is extended to solve more complicated problems. For example, I know tree DP to be a very interesting topic.
Parting Words
I didn’t really think about frequency of posting when I first started this. For a brief moment in time, after posting the last one, I thought I could post weekly. How naïve! Evidently, as this post is over a month late, I think once a month is a healthy period of time for me to comfortably write blogs as well as have something notable to write about. But I’ll just wait and see how I feel about everything come mid-December.
And as always, thanks for reading!
Comments