risingStark's blog

Followup of problem B in recent Goodbye 2024 contest.
By risingStark, history, 3 days ago, In English

In the recently conducted Goodbye 2024 contest, there was a problem(B) regarding intervals.

In the official solution and the submissions I saw, the fact that played a major role was that 1 <= l <= r <= 2*n.

This allowed us to make an array of size 2*n and then use prefix sums to find how many intervals of size 1 completely occupy some interval having size > 1.

What if the limit would have been 1e9 instead of 2*n?

For this modification, I was thinking, we can first store all the intervals of size 1 in a new array (let's say b). Then loop over b and merge intervals and at the end we will have some non-overlapping intervals. Now, taking these new intervals from array b, we need to find out how many intervals of size > 1 from the original array are completely contained in these newly built intervals from array b.

Is there a fast way to check this? In other words, we have two arrays a and b and we want to find out which intervals from a are completely contained in some interval from array b (where intervals in b are non-overlapping). Both a and b can be of the size of O(n) with 1 <= n <= 1e5. How can we solve this problem in atmost O(nlogn)?

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

»
3 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

you can use ordered set. 298957423

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

you can use ordered set or indexed set in order to find the number of points that are bad between li,ri. if there are ri-li+1 bad points then answer[i]='0' else answer[i]='1'.

x is bad -> there exist a li=ri=x pair in the problem.

here's my submission without using prefix sum and the fact that li<=ri<=n.

https://codeforces.net/contest/2053/submission/298824583

→ Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is quite cool. I didn't think of it before that we can just keep all points in a set and see how many are within a range. So, that is for this problem problem specifically.

    What if the intervals were of varying size? Is it possible to check overlapping of intervals within one another quickly?

    → Reply
»
3 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Why downvotes? Is it bad to ask modification of previous problems?

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Using ordered set. If li == ri, then insert them into the set.

→ Reply
»
3 days ago, # |
  Vote: I like it +5 Vote: I do not like it

I would put all intervals which have l==r to another array but if there are same instances of them just put one. Like {1,1}, {3, 3}, {1, 1}, you put {1, 1}, {3, 3}. Then sort that array.

Intervals which have l==r, and are repeating more than once are not unique, others are. Then for intervals where r-l>0, interval is not unique only if for every i, where l<=i<=r, there is interval of {i, i}. So just binary search on array that we formed and check if no. of them is equal to r-l+1.

→ Reply