EugeneJudo's blog

By EugeneJudo, history, 7 weeks 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

»
7 weeks 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/

»
7 weeks 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.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks, this is definitely more succinct than my code. I saw the prefix max idea, but didn't see that it was actually symmetric with the other kind of query via suffixes. This also looks to extend better to the harder problem of counting rather than checking nestings.