1 / 5
Dec 2019

I am trying to solve this problem: https://www.spoj.com/problems/EKO/21

i think I have optimal binary search solution but running into TLE :frowning:

Here is my code:

'''
https://www.spoj.com/problems/EKO/
'''


def chopped_off(heights, t):
    return sum(max(i-t, 0) for i in heights)


def search_optimal_height(heights, threshold):
    lo = min(heights) - threshold
    hi = max(heights)
    while lo <= hi:
        mid = (hi + lo)//2
        if chopped_off(heights, mid) >= threshold:
            lo = mid+1
        else:
            hi = mid - 1
    return hi


n, m = map(int, raw_input().split())
heights = [int(i) for i in raw_input().split()]
ans = search_optimal_height(heights, m)
print ans

Please help! :slight_smile:

  • created

    Dec '19
  • last reply

    Aug '20
  • 4

    replies

  • 978

    views

  • 3

    users

  • 1

    like

  • 1

    link

You can, you should, read coments under problem:

jkelava6: 2015-10-23 21:02:20

I think that time limit is too strict for Python, if you are using the solution that is meant to be used on this problem!
I mean, I have accepted it on C++… Now getting TLE with Python 3, using the SAME idea.

sonudoo: 2017-01-29 19:31:06

Same logic. Accepted in C++. TLE in Python

I see :frowning:

It would be great if it were possible to recalibrate the time limits for a language submission. Can you do that as a mod?

It seems to be quite a bit of an issue.

8 months later

submit the solution using pypy(2.7). Syntax is almost same as python 3. i got AC using pypy but was getting tle using python 3