EugeneJudo's blog

By EugeneJudo, history, 3 years ago, In English

I'm attempting to solve https://cses.fi/problemset/task/2168, and I believe I have the right idea, but i'm getting TLE for all large test cases. My algorithm is to:

  1. Transform inputs so that they're constrained to the range [0,400000]
  2. For every interval start, keep track of the smallest and largest interval ending.
  3. Build a sparse table to solve Range Minimum Queries on the minimum array.
  4. Build simpler (cheaper) array to solve RMQ with L=1 fixed for max array.
  5. Finally itterate through all queries and solve (one $$$O(1)$$$ call to the sparse table per query.)

Implementation: https://cses.fi/paste/cec69737a6649398283c56/

My main thought is to use an offline query method instead, but nothing here seems like it should exceed the 1 second time limit.

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

| Write comment?
»
3 years ago, # |
  Vote: I like it +34 Vote: I do not like it

Ok I solved this, for anyone interested it was an implementation difference. I downloaded one of the large test cases and commented out my code to find it was the preprocessing that was too slow! I made the change from inserting one at a time into a set (~500ms) to putting everything into a vector, sorting it, and then loading a new vector with unique elements (~200ms). The other big change was switching from map (~600ms) to unordered_map (~100ms!). The rest of the code was all comfortably less than 500ms.

Revised implementation: https://cses.fi/paste/9e806894689f8489283d05/

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

you don't require any pre processing or sparse table stuffs I believe. Sort every range on the basis of start point.

for finding if [l,r] contains any other range find the minimum ending point with starting point >=l, this can be done by maintaining suffix min on ending points and binary search in $$$O(log(n))$$$. If that min ending is <=r then you can print 1 otherwise 0.

for finding if [l,r] is contained in any other range find the max ending point for all starting point<=l, this can be done by maintaining prefix max on ending point and binary search in $$$O(log(n))$$$. if that max ending point>=r, you print 1 else 0.