TLE (Time Limit Exceeded) Error for Golang, but not Python using similar logic. But why?

Question

I wrote two solutions to the same simple problem for Google Kickstart. They are fundamentally the same solution. The problem link is this. I submitted two solutions, first in go and then python. But the python solution executed properly, wherein go solution had TLE. I am sharing both codes. I would appreciate feedback on the error.

Go:

package main

import (
    "fmt"
    "sort"
)

func main() {
    var N int
    fmt.Scan(&N)
    for i := 1; i <= N; i++ {
        var house, budget int
        fmt.Scan(&house, &budget)
        prices := make([]int, house)
        for j := 0; j < house; j++ {
            fmt.Scan(&prices[j])
        }

        sort.Ints(prices)
        j := 0
        for ; j < house; j++ {
            if prices[j] > budget {
                break
            }
            budget -= prices[j]
        }
        fmt.Printf("Case #%d: %d\n", i , j)
    }
}

An updated go solution with improved time complexity O(n):

package main

import (
    "fmt"
)

func main() {
    var N int
    fmt.Scan(&N)
    for i := 1; i <= N; i++ {
        var house, budget int
        fmt.Scan(&house, &budget)
        prices := make([]int, 1000)
        for j, val := 0, 0; j < house; j++ {
            fmt.Scan(&val)
            prices[val-1]++
        }

        count := 0
        for j := 0; j < 1000; j++ {
            if prices[j] == 0 {
                continue
            }
            cost := prices[j] * (j + 1)
            if budget >= cost {
                budget -= cost
                count += prices[j]
            } else {
                c := budget / (j + 1)
                count += c
                break
            }
        }
        fmt.Printf("Case #%d: %d\n", i, count)
    }
}

Python:

N = int(input())

for i in range(1, N + 1):
    house, budget = map(int, input().split())
    prices = list(map(int, input().split()))
    prices.sort()
    j = 0
    for price in prices:
        if price > budget:
            break
        budget -= price
        j += 1
    print("Case #", i, ": ", j, sep='')

_with no algorithmic difference._ I'd hesitate to say that without being more specific. _This doesn't make much sense._ Why not? As an aside, you should probably use a list comprehension instead of `map()`, and the `j` counter can be replaced by using `enumerate()`. — AMC, Apr 13 '20 at 03:09
@AMC, I removed my opinions. However, I tried to write the python code, as close as possible to the Go code. Also, I am not that proficient in Python either. — rafee, Apr 14 '20 at 12:44
@AMC Sorry but I have to disagree. This is the intended use case of `map` and [it's faster since `int` is not a lambda](https://stackoverflow.com/questions/1247486/list-comprehension-vs-map), and using `enumerate` will be confusing since the counter needs to be used outside the loop. Also, saying that there's no algorithmic difference is understood since both solutions are conceptually the same, but differ in their implementation. — Kevin Languasco, Apr 16 '20 at 16:29

Kevin Languasco · Accepted Answer · 2020-04-16T15:51:21.473

The slowness is in the input reading. The function fmt.Scan doesn't use buffered IO. You can fix this by using an explicit buffer and Fscan.

in := bufio.NewReader(os.Stdin)
fmt.Fscan(in, &N)

This way, even the algorithmicaly slow solution passes the tests (yes, it's that much better)

package main

import (
    "fmt"
    "sort"
    "bufio"
    "os"
)

func main() {
    var N int
    in := bufio.NewReader(os.Stdin)
    fmt.Fscan(in, &N)
    for i := 1; i <= N; i++ {
        var house, budget int
        fmt.Fscan(in, &house, &budget)
        prices := make([]int, house)
        for j := 0; j < house; j++ {
            fmt.Fscan(in, &prices[j])
        }

        sort.Ints(prices)
        j := 0
        for ; j < house; j++ {
            if prices[j] > budget {
                break
            }
            budget -= prices[j]
        }
        fmt.Printf("Case #%d: %d\n", i , j)
    }
}

If even this isn't fast enough for some other problem, there's another question here with an even faster solution.

An additional optimization is noting the unnecessary allocation of arrays on every iteration. Since you are given the maximum possible size, you could do

const maxAllocation = 10000
container := make([]int, maxAllocation)

and then just get a slice in each iteration

prices := container[0:houses]

and work with that. This official blog post explains the internals very nicely.

TLE (Time Limit Exceeded) Error for Golang, but not Python using similar logic. But why?

1 Answers1