Hello y'all! I'm new to Codeforces and I am trying to solve this 1974F
Here is my submission. My approach is to sort the points by the x- and y-axes and use a two pointers approach that slowly closes in on the grid to find the answer. My analysis says my solution should run in O(nlogn + n + m) time, but it appears to TLE on test 7 and takes quite a while for smaller inputs.
Is cache efficiency the reason here? My algorithm is pretty cache inefficient, but cache efficiency feels more like a constant-time optimization that wouldn't really impact an algorithm that TLEs. What are your thoughts on this?
Auto comment: topic has been updated by saadamin2006 (previous revision, new revision, compare).
In the lambda expression used for sorting, you are capturing chips by value. This causes the entire vector to be copied for each comparison. Capturing by reference should fix this issue.
Thanks! This solution worked.