Ximo's Blog

My Twitter profileMy Telegram profileMy Codeforces profileMy LinkedIn profileMy Google+ profile

Saturday, 08 Aug 2015 - 21:20

Using Go in programming contests

In the last few weeks I've been trying to learn more about Go. I was bored of the examples in the book I was reading, so I decided to solve a few easy problems in Codeforces.

I'll share a few issues here about using Go for programming contests.

Go is a verbose language

A program in Go requires more characters than in other languages such as C++ or Python. At least is not as verbose as Java. This is cause by some design decisions made by the authors of the language:

I usually spend much more time thinking/debugging than coding so is not a big problem for me.

fmt.Scanf() is sloooooow

For some reason I don't know, fmt.Scanf() is terribly slow. You should alway use bufio and fmt.Fscanf() instead.

I tried to solve the Codeforces problem 567A - Lineland Mail in various languages and these are the results:

Go with fmt.Scanf() is three times slower than Python3? Really? Why they don't put the bufio implementation as default?

Here is my solution using bufio. Notice you need to create a bufio.NewReader and pass it as argument to fmt.Fscanf(). The rest of the I/O remains the same.

package main
import (
    "bufio"
    "fmt"
    "os"
)

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    stdin := bufio.NewReader(os.Stdin)
    var n int
    fmt.Fscanf(stdin, "%d\n", &n)

    cities := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Fscanf(stdin, "%d", &cities[i])
    }

    fmt.Println(cities[1]-cities[0], cities[n-1]-cities[0])
    for i := 1; i < n-1; i++ {
        lo := min(cities[i]-cities[i-1], cities[i+1]-cities[i])
        hi := max(cities[n-1] - cities[i], cities[i] - cities[0])
        fmt.Println(lo, hi)
    }
    fmt.Println(cities[n-1]-cities[n-2], cities[n-1]-cities[0])
}

fmt.Scanf() behaviour is slightly different than scanf() from C

At least in Codeforces and maybe because they use Windows machines, fmt.Scanf() won't consume all the blanks before reading a token.

Suppose you need to read the size of a vector and then vector itself in the next line:

5
1 2 3 4 5

In C/C++, scanf will ignore the spaces and new lines:

scanf("%d", &n);
for (int i = 0; i < n; ++i)
    scanf("%d", &v[i]);

In Go (at least in Codeforces), you'll have to consume the \n. For some reason if is able to consume the spaces by itself but not the new line character. This does not happen on my laptop (Ubuntu) so must be something related to the Codeforces server.

fmt.Scanf("%d\n", &n)
for i := 0; i < n; i++ {
    fmt.Scanf("%d", &v[i])
}

If we use "%d" instead, the first iteration of the for loop will try to read a \n and v[0] will be 0. The second iteration will read the first value of the vector and will put it at v[1].

This might be problematic is you are in a contest and you can't see the result of your submission. The only thing you get is Wrong answer but it may be a problem with you input reading or a fault in your solution's logic.

Goroutines

Goroutines can be used in Codeforces. I still don't know if the judge accumulates the CPU used across all the threads or if it checks the real time. I couldn't find a good problem where parallelism could be exploited to check if using goroutines is worthy.

I solved the problem 551 - GukiZ and Contest using an \(O(n^2)\) solution, then I added "go" in front of the inner function call to execute the calls in parallel. The linear and goroutine solutions took almost the same time. The goroutine-based solution finish 1ms earlier, 61 ms vs 62 ms, but it is not significant.

This is the code for my solution with goroutines. Notice you need to create a WaitGroup to wait for all the goroutines to finish before printing the final result.

package main

import (
    "fmt"
    "sync"
)

func main() {
    var n int
    fmt.Scanf("%d\n", &n)

    a := make([]int, n)
    r := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Scanf("%d", &a[i])    
    }

    var wg sync.WaitGroup

    solve := func(i int) {
        defer wg.Done()
        cnt := 0
        for j := 0; j < n; j++ {
            if a[i] < a[j] {
                cnt++
            }
        }
        r[i] = cnt+1
    }

    wg.Add(n)
    for i := 0; i < n; i++ {
        go solve(i)
    }
    wg.Wait()

    for i := 0; i < n; i++ {
        if i != 0 {
            fmt.Printf(" ")    
        }
        fmt.Printf("%d", r[i])
    }
    fmt.Println("")
}

For contests where you execute your own solution (Code Jam, Hacker Cup) using goroutines might be useful. I'm not sure for Codeforces.

Reasons to use Go in programming contests

I don't see strong reasons to use Go in programming contest other than learning the language itself.

With Python you now that you can do a lot in just a few lines but your solution will be much slower. Go is slower than C++ but does not provide us anything that we don't have in C++, actually a solution in Go will probably have more lines of code.

The stuff that makes Go great (goroutines, quick compilation, etc) are not very useful in a programming contest.