Skip to content

Codility – Number of Disc intersections problem

May 4, 2018

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 []*CirclePoint

func (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

From → Uncategorized

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: