Last div 2 problem D is quite difficult to implement. My solve after contest was over 150 lines submission:192414856 and in-contest I struggled to find an efficient way to implement the problem. Also recently, as I’m solving harder problems, the problems become more tedious and difficult to implement. To the point where I cannot reasonable be able to solve them in-contest(maybe I just type slow~60wpm for programming~100wpm normally). One problem is that I’m writing lots of similar code(but not similar enough) where I can’t find an efficient way to come up with an algorithm for all the copy and pasting. In the case of the problem mentioned previously, it’s very inefficient to write all possible pairs with w i and n. And if there are more characters, I would not be able to solve the problem practically. Sometimes as well, I’m not sure if there exists a data structure or method for a specific purpose. For example, E on last div 2 contest could be solved if I have a data structure with o(1) insertion and o(1) replacement(as well as being indexed). So I have three major questions:
Are there any data structures that I’m unaware of? I know ArrayLists(Java), arrays, stacks, priority queues and queues, as well as ordered and unordered maps and sets. I am also moderately aware of the functions of the LinkedList but I find very little usage with it.
Smart methods for handling strings, pairs, other misc data types. I am aware of StringBuilder.
How to maps solutions into code efficiently. I do read other people’s solutions but I usually don’t understand them very well. I understand that it comes down to practice(I solve a lot of problems across multiple platforms), but many times I find my solutions very impractical to implement.
Ex: https://codeforces.net/contest/1741/problem/F
Thank you all for sparing time out of your day for reading this post, hopefully I’m not the only person who has this problem since you are all speed gods.
Hello sir, I understand when ppl find implementation tricky because I find it extremely hard as well for certain problems. However, there are some things that you should consider.
If you find the implementation relatively easy but just long, then most of the time I would presume that you are unnecessarily considering many details that can be condensed into one piece of logic. However, this isn't much of a problem as the many lines of code is offset by the fact that writing each line of code should be easier
However, if you are constantly getting stuck in the implementation and can't write a single line of code for a significant amount of time, then most likely, you don't understand the solution to the problem well enough. What I mean by this is that you may have a solution, but it may not be very concrete. So for example say that you are implementing a greedy algorithm, then maybe u have a vague idea of the best choice at a certain position but you don't have it in your mind in concrete terms, so it can't be translated into an algorithm.
So maybe it would be helpful if you explain the solution to div.3 F in detail to me, and then I can help you implement it.
Hi, thanks for the feedback. It is often a combination of both things but I’m not sure if it has to do with my programming skill or that I don’t fully understand the problem. As for the solution my idea is as follows:
Sweep line for intersection: Sort all the start and end points, keep track of the start points and end points and their respective colors. Add colors if a point starts at the point, and remove it if it ends at that point. Keep track of the count of each color in a Map, and if multiple colors are present, all active elements will get an ans of 0(done in a separate queue). 2xn pointers + n possible points +n for removing+nlogn for sorting.
Binary search: For all points that haven’t been intersected, sort the end and start points separately. Also keep track of this for each color. Binary search the closest end point less than the start of the point do the same for that of the same color with the point your checking. If the number is greater for the total than that of the same color you should search left of it. Vice versa for the end point. N points * 2 * logn for the binary search.
Memory: About 12 x N.
Might be hard to understand, I’m not great at explaining and I’m not good at math so I can’t explain it in a mathematical standpoint.