[Fixed] C++ lower_bound causes TLE, fixed by copying lower_bound from cplusplus.com


  • 1
    V

    My solution is to sort the ranks, and then use binary search to determine the position. There is a better solution that sorts indexes instead, but I wanted something simpler to code for the contest. It's still O(n log n), so it should be accepted.

    However, I got TLE, and I was able to fix it by just using lower_bound code I found at cplusplus.com (presumably, that's how it should be implemented in the standard library).

    I was able to troubleshoot this quickly since I have faced this problem with OJ. Nevertheless, it entailed 600 seconds of penalty, plus some extra time to do the fix.

    template <class FI, class T>  FI my_lower_bound (FI first, FI last, const T& val) 
    {
      auto count = distance(first,last);
      while (count > 0)
      {
        auto it = first; auto step=count/2; advance (it,step);
        if (*it<val) {
          first=++it;
          count-=step+1;
        }
        else count=step;
      }
      return first;
    } 
    vector<string> findRelativeRanks(vector<int>& nums) {
        vector<string> res;
        vector<int> sorted(nums.begin(), nums.end());
        sort(sorted.begin(), sorted.end());
    
        for (auto n : nums) {
            // TLE if replace with standard lower_bound
            auto pos = nums.size() - distance(sorted.begin(), my_lower_bound(sorted.begin(), sorted.end(), n));
            if (pos == 1) res.push_back("Gold Medal");
            else if (pos == 2) res.push_back("Silver Medal");
            else if (pos == 3) res.push_back("Bronze Medal");
            else res.push_back(to_string(pos));
        }
        return res;
    }
    

  • 0
    K

    @votrubac
    This is a real interesting problem if lower_bound is not working properly on OJ. Maybe one of the admins can look into this?


  • 0
    V

    JFYI, this is the related topic I posted earlier: https://discuss.leetcode.com/topic/77535/oj-run-time-calculation-problem.

    I did not got TLE In that case, but lower_bound's run-time was 150 ms vs. 3 ms when using a hand-coded binary search.


  • 0

    Hi,

    This has been fixed. The reason is being _GLIBCXX_DEBUG flag was enabled previously, which cause STL methods to be very slow, since it does some assertion checks such as bounds checking etc... I have disabled that flag since it's causing more trouble than good. Did this affect your contest submission? If so, please let me know as I am considering to rejudge all C++ submissions again for the contest.


  • 0

    @1337c0d3r Can you tell since when debugging was turned on?

    Rejudging C++ contest submissions might indeed be a good idea. I think I've seen several other topics about C++ being unreasonably slow in the past few days which could be attributed to this. And likely there were more cases, as I'm not reading everything and as people might've been affected but not said something because they just thought their code is bad.


  • 0
    V

    @1337c0d3r The solution with STL lower_bound is now accepted, and the run-time is the same (15 ms) as with hand-coded binary search. I noticed this problem for the first time 2 days before the contest. I did not notice anything before that, though I was pretty active last few months.


  • 0

    @StefanPochmann said in [Fixed] C++ lower_bound causes TLE, fixed by copying lower_bound from cplusplus.com:

    @1337c0d3r Can you tell since when debugging was turned on?

    This was turned on about 22 days ago.


  • 0

    @votrubac I have rejudged your contest submission and updated your ranking.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.