Hi, I was trying to solve 702F — T-Shirts. These are four interesting submissions:
Use the "Compare" tool on CF to see the diff between these submissions and notice for yourself that the changes are only in the sign of inequality of split_by_val and insert_by_val! In fact, the AC is in <500ms whereas TLE is on 4000ms, quite significant difference!
I do not understand why the signs of inequality actually matter. Here are my thoughts:
- Splitting by value and insertion by value should be able to operate independent of each other. The only prerequisite for both of them is that the treap should be BST ordered, which it always is. Therefore, the correctness of split should not depend on whether insert uses < or <= (and vice-versa).
- The only reason it may TLE is because of unbalancedness in the treap. But for the purpose of balancing we are using a random priority which should rebalance the treap everytime we insert by value.
So, either this an actual theoretical issue in treaps that I have not seen mentioned anywhere before (unlikely), or I have made another error in implementation due to which this issue shows up (likely) [Although I have cross checked my implementation with my friend's] Regardless, I don't understand why it TLEs!
Please help me understand the issue, thanks!
