saadamin2006's blog

Trying to figure out why my solution TLEs
By saadamin2006, history, 6 months ago, In English

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?

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by saadamin2006 (previous revision, new revision, compare).

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply