Why My Simple Go Map Solution Timed Out and How I Fixed It

Introduction

Hello everyone, I am Xiao Lou. Last week I participated in a regional programmer skill competition, essentially an algorithm contest similar to ACM. Although I passed the preliminary round, the experience was quite challenging because my algorithm skills are weak.

Problem Statement

The task is to read a series of scores. For each score, output perfect if it exceeds the best score of the whole class, great if it exceeds the individual's previous best, otherwise output bad.

First Attempt (Map Solution)

I started with a straightforward Go solution using a map[string]float32 to store each student's best score and a variable for the class maximum.

package main

import (
    "fmt"
)

func main() {
    var n int
    var name string
    var x float32
    var max float32
    scores := make(map[string]float32, n)
    fmt.Scan(&n)
    for i := 0; i < n; i++ {
        fmt.Scan(&name, &x)
        if x > max || i == 0 {
            fmt.Println("perfect")
            max = x
            scores[name] = x
        } else {
            if s, ok := scores[name]; ok {
                if x > s {
                    fmt.Println("great")
                    scores[name] = x
                } else {
                    fmt.Println("bad")
                }
            } else {
                fmt.Println("great")
                scores[name] = x
            }
        }
    }
}

This solution seemed correct, but it timed out on a few hidden test cases.

Timeout Diagnosis

The problem imposed a 2‑second limit for non‑C/C++ languages and a memory limit of 512 MB. I suspected the map's performance might be the bottleneck due to possible hash collisions.

Optimizing Map Performance

Considering that each name consists of at most six lowercase letters, I explored converting the name into a base‑27 number (using 0 as a placeholder) and using the result as an array index, achieving O(1) look‑ups.

27‑Base Array Approach

The maximum index is

26*27^5 + 26*27^4 + 26*27^3 + 26*27^2 + 26*27 + 26 = 387420488

, requiring an array of about 3.9 × 10⁸ elements. Assuming 4 bytes per element, the memory consumption would be roughly 1.5 GB, exceeding the limit.

package main

import (
    "fmt"
)

func main() {
    var n int
    var name string
    var x int32
    fmt.Scan(&n)
    var scores [387420488]int32
    var exist [387420488]int32
    var max int32
    for i := 0; i < n; i++ {
        fmt.Scan(&name, &x)
        idx := mapIndex(name)
        if x > max || i == 0 {
            fmt.Printf("perfect
")
            max = x
            scores[idx] = x
            exist[idx] = 1
        } else {
            if exist[idx] == 0 || x > scores[idx] {
                fmt.Printf("great
")
                scores[idx] = x
                exist[idx] = 1
            } else {
                fmt.Printf("bad
")
            }
        }
    }
}

var index27 = [6]int32{1, 27, 27*27, 27*27*27, 27*27*27*27, 27*27*27*27*27}

func mapIndex(x string) int32 {
    var index int32
    for i := len(x) - 1; i >= 0; i-- {
        index = index + int32(x[i]-96)*index27[len(x)-1-i]
    }
    return index
}

This version failed because it exceeded the memory limit.

Memory Optimization Attempts

I reduced the auxiliary array to a boolean and stored scores as int16, cutting memory roughly in half, but the total still surpassed the allowed 512 MB.

Trie Solution

Another idea was to build a prefix‑tree (trie) for the names, limiting each lookup to at most six steps.

package main

import (
    "fmt"
)

type treeNode struct {
    max  float32
    next [26]*treeNode
}

func main() {
    var n int
    var name string
    var x float32
    fmt.Scan(&n)
    var max float32
    tree := new(treeNode)
    for i := 0; i < n; i++ {
        fmt.Scan(&name, &x)
        if x > max || i == 0 {
            fmt.Println("perfect")
            max = x
            insert(tree, name, x)
        } else {
            if tmp := searchAndStoreMax(tree, name, x); tmp != -1 {
                if x > tmp {
                    fmt.Println("great")
                    insert(tree, name, x)
                } else {
                    fmt.Println("bad")
                }
            } else {
                fmt.Println("great")
                insert(tree, name, x)
            }
        }
    }
}

func insert(node *treeNode, name string, x float32) {
    for i := 0; i < len(name); i++ {
        idx := int32(name[i] - 'a')
        if node.next[idx] == nil {
            node.next[idx] = new(treeNode)
        }
        node = node.next[idx]
    }
    node.max = x
}

func searchAndStoreMax(node *treeNode, name string, x float32) float32 {
    for i := 0; i < len(name); i++ {
        idx := int32(name[i] - 'a')
        if node.next[idx] == nil {
            return -1
        }
        node = node.next[idx]
    }
    if x > node.max {
        tmp := node.max
        node.max = x
        return tmp
    }
    return node.max
}

This version also timed out.

Input Handling Pitfall

The breakthrough came from realizing that the online judge (牛客网) expects each line to be read as a whole string and then split, rather than using the default Go scanner that reads tokens. Using bufio.Scanner with manual splitting fixed the issue.

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

func main() {
    var n int
    var name string
    var x float64
    input := bufio.NewScanner(os.Stdin)
    if input.Scan() {
        n, _ = strconv.Atoi(input.Text())
    }
    scores := make(map[string]float64, n)
    var max float64
    for i := 0; i < n; i++ {
        if input.Scan() {
            arr := strings.Split(input.Text(), " ")
            name = arr[0]
            x, _ = strconv.ParseFloat(arr[1], 32)
        }
        // processing logic (same as map version)
        if x > max || i == 0 {
            fmt.Println("perfect")
            max = x
            scores[name] = x
        } else {
            if s, ok := scores[name]; ok {
                if x > s {
                    fmt.Println("great")
                    scores[name] = x
                } else {
                    fmt.Println("bad")
                }
            } else {
                fmt.Println("great")
                scores[name] = x
            }
        }
    }
}

With the correct input method, the original map solution passed within the limits.

Final Results

Map version – Passed (315 ms, 10 MB)

27‑base array – Failed (memory exceeded)

Trie version – Passed (433 ms, 43 MB)

Conclusion

The journey highlighted the importance of understanding judge I/O requirements and demonstrated several optimization techniques, but ultimately a simple map with proper input handling was sufficient to solve the problem.