Trying to figure out why my solution TLEs

Revision en2, by saadamin2006, 2024-06-28 07:59:35

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?

Tags need help, optimization, cache, two pointers

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English saadamin2006 2024-06-28 07:59:35 1 Tiny change: 'on the grind to find ' -> 'on the grid to find '
en1 English saadamin2006 2024-06-28 07:59:17 763 Initial revision (published)