Hello everyone,
I have been taking part in Codechef’s long challenges for about 3 months now. I have been able to solve the initial 3 to 4 questions. But, when it comes to the next questions, I get stuck sometimes because of not knowing what are the prerequisites of the problem. So, I want to know how to know what topics are being covered for a particular question so that I can look up and learn that topic so as to solve the question.
Thank you for your time.
Telling from my past long challenge experiences, I always tried to think what I am missing ( is it knowledge of some theory, or is it not being able to observe some important fact).
Like for example, the first time I learned segment tree. From problem : ZOMCAV
The problem was basically something like this : You had to make many range queries. But I didn’t know how to do range queries in under O(N) time. So I looked up resources that can help me understand how to do this in under O(N) time.
(PS: that problem is solvable in O(N) time and with much easy implementation using Difference Array)
Another example is where I learnt mergesort tree : From problem : LAZER
After thinking for hours I concluded that ,I had to kind of get the Kth largest element in the range. And again I looked up everywhere how to implement that (found PBDS but it was too slow), then came to merge sort tree in the end.
(PS: again, that problem is solvable more easily by making some observations and using sweep-line event based approach)
Now…
One example where observation plays a role is : LAZERST
This one had me scratching my head for days. Ultimately I came to the conclusion that it’s not possible using any DS/Algo I had known of. So I started making some other observations and finally managed to solve it.
Now finally…
What helped me during these times is I had already gone through https://cp-algorithms.com/ and cp-handbook (CSES) theory once. Don’t misunderstand these points, I never actually understood how those algorithms worked at first. I just had kind of remembered what is possible to implement and what is not. And that kind of helped me a lot in distinguishing whether I am missing theory knowledge or some crucial observation.
So I think , you should pick up some good resource and go through all of it . No need to immediately try to understand all implementations , just keep in mind what is possible and what is not. That helped me a lot and I hope it will also help you a lot too.
Thank you for such a detailed response. So, while solving a question, if I cannot solve a question based on my current knowledge, I should find the limitations in my approach and search on Google based on it.
Thank you again.
Yeah, that is the whole point of long challenge. Codechef is helping you learn new algos and ds by these long challenges. And rewarding you with rating for learning and implementing those to solve problems.
The rules of long challenge are also made to support that. You are allowed to use any already-available resource on internet to help yourself learn the concept.