towersfreak2006's blog

Binary Search and Deletions?
By towersfreak2006, 4 weeks ago, In English

I'm looking for a data structure or subroutine that takes in a sorted list $$$L$$$ of $$$n$$$ integers and a list $$$Q$$$ of $$$n$$$ integers. For each element $$$q\in Q$$$, we should report the largest remaining element in $$$L$$$ smaller than $$$q$$$ and then remove it (or we can report $$$-1$$$ if no such integer exists). I would like the entire process to take $$$O(n \log n)$$$ time.

My understanding is that this approach is necessary for today's 2254E - Chronostasis, but many user-accepted Python solutions seem to implement Fenwick trees, which I believe might be too complicated for a Div. 3 contest and not the intended solution (though I could be wrong).

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

dsu i guess

→ Reply
»
4 weeks ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

std::multiset can do this.

multiset<int> st;

int query(int x) {
    auto it = st.lower_bound(x);
    if (it == st.begin()) return -1;
    --it;
    int res = *it;
    st.erase(it);
    return res;
}
→ Reply
  • »
    »
    4 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Hm, do you know if there's a similar data structure in Python?

    → Reply
    • »
      »
      »
      4 weeks ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      If I am not mistaken, Python does not have built-in structures similar to std::set or std::multiset unless you use external libraries (which isn't possible on Codeforces). I would recommend either solving the problem with a different language like C++, or if you really want to remain Python-only, you can implement something similar for your specific use case.

      For this specific scenario you provided, I would recommend either of the following:

      • Implicit/Dynamic Segment Tree — For this one, you can either implement a lower_bound function with binary search and query in log^2(n), or you can implement the search in the tree propagation itself in log(n) time, depending on whether you're willing to somewhat understand the tree structure rather than black-box it.

      Not sure if there is something easier for pure Python; would be curious to hear if there is, though.

      → Reply
      • »
        »
        »
        »
        4 weeks ago, hide # ^ |
         
        Vote: I like it +2 Vote: I do not like it

        There is actually something pure Python, but not native, it's called Sorted List and is available in a python module named "sorted_containers".

        This module is actually imported for you on Atcoder and Leetcode, it's not the case for codeforces tho. So what I usually do, is copy paste the implementation.

        → Reply
»
4 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

U need to use binary search + multiset, multiset supports deletions in O(log n).

→ Reply