# Codility – Number of Disc intersections problem

This is a training problem. Advanced one in sorting. Their classification of advanced is Respectable, as against Painless (which I presume means Easy)

On my 3rd try, I got a perfect score. After applying the lesson learnt in prefix summation, an earlier lesson of Codility. Which brought down the time complexity to O(N) from O(N^2)

This is the link to my results.

https://app.codility.com/demo/results/trainingBGF5A3-KW5/

Also my program in Golang below

package solution

// you can also use imports, for example:

//import “fmt”

import “sort”// import “os”

// you can write to stdout for debugging purposes, e.g.

// fmt.Println(“this is a debug message”)type CirclePoint struct {

X int

CircleId int

IsLeft bool

}// ByLeftX implements sort.Interface for []*CirclePoint based on

// the Left x value field.

type ByLeftX []*CirclePointfunc (a ByLeftX) Len() int { return len(a) }

func (a ByLeftX) Swap(i, j int) { a[i], a[j] = a[j], a[i] }

func (a ByLeftX) Less(i, j int) bool {

// a crucial logic is that if there is a clash of left and right circle

// then we should return the left one first, as touching counts as intersection

ret := false

if a[i].X < a[j].X {

ret = true

} else if a[i].X == a[j].X {

if a[i].IsLeft {

ret = true

}

}

return ret

}func Solution(A []int) int {

// write your code in Go 1.4

var cparr []*CirclePoint

N := len(A)

for i := 0; i < N; i++ {

cpl := CirclePoint{i – A[i], i, true}

cpr := CirclePoint{i + A[i], i, false}

cparr = append(cparr, &cpl)

cparr = append(cparr, &cpr)

}// sort the left and right points on the cricle starting from left to right

sort.Sort(ByLeftX(cparr))

//fmt.Printf("cparr: %+v\n", cparr[0])// Now we do some prefix sum to avoid time complexity run to O(N^2)

// we just keep the sum of left edges of a circle enountered so far

pref_sum := make([]int, 2*N)

for i := 0; i 0 {

pref_sum[i] = pref_sum[i-1]

}

cp := cparr[i]

if cp.IsLeft {

pref_sum[i]++

} else {

pref_sum[i]–

}

}// Find the intersections of all left sides with the already encountered left sides,

// as we move from left to right

// we keep a track of the circles we are in

ret := 0

for i := 0; i 10000000 {

return -1

}

}

}return ret

}Advertisements