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.
Sweep line to find intersection, binary search left and right if no intersection. Should be nlogn but I’m finding it very hard to implement this efficiently(spent 2 hrs just implementing and gave up. Also not ideal in-contest).
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.