remonhasan's blog

By remonhasan, history, 7 weeks ago, In English

Greetings, esteemed Codeforces community!

As an avid participant on this platform, I've found myself proficient in solving A and B level problems, yet I often struggle when attempting the more challenging C and D level tasks. Despite my best efforts, I frequently encounter the dreaded "Time Limit Exceeded" verdict.

I'm reaching out to seek guidance from fellow Codeforces enthusiasts who have successfully navigated through these higher difficulty problems. What strategies do you employ to enhance efficiency when tackling C and D level challenges? How do you approach problem-solving, algorithm design, and code optimization to ensure timely execution within the given constraints?

Furthermore, I'm curious to learn about effective practice strategies for honing skills specifically geared towards solving C and D level problems. How do you structure your practice sessions, and what resources do you find most beneficial in preparing for these challenges?

Any insights, tips, or personal experiences you can share would be immensely appreciated. Let's embark on this journey together and strive towards mastering the art of solving Codeforces C and D problems with finesse and efficiency.

Thank you for your time and wisdom.

Warm regards, remonhasan

  • Vote: I like it
  • -6
  • Vote: I do not like it

»
7 weeks ago, # |
Rev. 2   Vote: I like it +34 Vote: I do not like it

It's hard for me to give more general advice about structuring practice and such, but there is something I can say about getting "time limit exceeded".

Do you know what the words "time complexity" mean? I looked at a couple of your recent submission and I suspect that you don't. If you don't, you can read for example chapter 2 here.

Let's take 1807D - Odd Queries as an example, which is a problem you recently got TLE on. All you do is iterate over the entire array for each query. There are $$$n$$$ elements in the array and $$$q$$$ queries, both numbers can be up to $$$2 \cdot 10^5$$$, that means you hit your sum += arr[i] or sum += k line $$$4 \cdot 10^{10}$$$ times. You can as a rule of thumb assume that about $$$10^8$$$ such operations fit in a second. This means that your program needs to become 200 times faster.

Now, I think it's really important to note this: problems like this aren't solved by micro-optimizations like changing long long to int. Is it faster? Maybe. But it's not 200 times faster. And these micro-optimizations don't really "add up" either. A very skilled person might theoretically be able to make that $$$O(nq)$$$ algorithm work, but that would be far harder than solving the problem in the intended way, and I'm not even sure if it is possible.

No, your problem is that you are still doing 40 billion additions. You need actual clever ideas to get rid of this problem.

Hint 1
Hint 2

"Time limit exceeded" should practically never happen. If you know what time complexity means, you should have a pretty good idea of whether your solution is fast enough without submitting. There are exceptions to this, yes, sometimes it is really on the edge, sometimes silly mistakes happen and so on. But these are exceptions.