hashcode-2018/main.go

package main

import (
	"fmt"
	"math/rand"
	"os"
	"sort"
)

var input *os.File
var output *os.File

var R int
var C int
var F int
var N int
var B int
var T int

var Rides []*Ride

var Cars []*Car

var Sched Scheduler

type Ride struct {
	ID int

	a, b, x, y, s, f int

	used bool
}

func (r Ride) Length() int {
	xdist := r.a - r.x
	if xdist < 0 {
		xdist = -xdist
	}
	ydist := r.b - r.y
	if ydist < 0 {
		ydist = -ydist
	}

	return xdist + ydist
}

func abs(x int) int {
	if x < 0 {
		return -x
	} else {
		return x
	}
}

func (r *Ride) length() int {
	return abs(r.a-r.x) + abs(r.b-r.y)
}

type ByEndtime []*Ride

func (rs ByEndtime) Len() int      { return len(rs) }
func (rs ByEndtime) Swap(i, j int) { rs[i], rs[j] = rs[j], rs[i] }
func (rs ByEndtime) Less(i, j int) bool {
	return rs[i].f < rs[j].f || (rs[i].f == rs[j].f && rs[i].length() < rs[j].length())
}

type Scheduler interface {
	Add(*Car)
	RemoveAtIndex(k int) *Car
	Pop() *Car
}

type Car struct {
	ID    int
	Rides []int

	Arrival int
	X       int
	Y       int

	score   int
	pqindex int // used for removal in prority queue
}

func (c *Car) Update(r *Ride) {
	c.moveTo(r.a, r.b)
	if c.Arrival <= r.s {
		c.Arrival = r.s
		// count bonus points for being on time
		c.score += B
	}
	c.moveTo(r.x, r.y)
	c.score += r.length()
	c.Rides = append(c.Rides, r.ID)
}

func (c *Car) EarliestFinish(r *Ride) int {
	copy := &Car{
		Arrival: c.Arrival,
		X:       c.X,
		Y:       c.Y,
	}
	copy.moveTo(r.a, r.b)
	if copy.Arrival < r.s {
		copy.Arrival = r.s
	}
	copy.moveTo(r.x, r.y)
	return copy.Arrival
}

func (c *Car) moveTo(x, y int) {
	xdist := c.X - x
	if xdist < 0 {
		xdist = -xdist
	}
	ydist := c.Y - y
	if ydist < 0 {
		ydist = -ydist
	}

	c.Arrival += xdist + ydist
	c.X = x
	c.Y = y
}

func (c *Car) distanceTo(x, y int) int {
	return abs(c.X-x) + abs(c.Y-y)
}

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

var bestTotalScore int

// invariant : when entering and leaving function,
// Sched has the "same" heap. Same means successive
// popped values will be the same (but the internal
// ordering of nodes may be different)
func Choose(cumulativeScore int, depth int) {
	if cumulativeScore > bestTotalScore {
		bestTotalScore = cumulativeScore
	}
	c := Sched.Pop()
	if c == nil {
		// Stop recursion, empty car list,
		// could not match cars to rides
		return
	}

	var bestRides []struct {
		r         *Ride
		lenOfRide int
		total     int
	}
	// fmt.Printf("car %d\n", c.ID)
	for _, r := range Rides {
		if r.used {
			continue
		}
		if r.Length() > 6000 {
			continue
		}
		if r.f < c.EarliestFinish(r) {
			continue
		}
		// fmt.Printf("%d %d -> %d %d\n", r.a, r.b, r.x, r.y)
		lenOfRide := r.length()
		total := max(c.distanceTo(r.a, r.b), r.s-c.Arrival) + lenOfRide
		// fmt.Printf("%d/%d\n", lenOfRide, total)
		if len(bestRides) == 0 || lenOfRide*bestRides[len(bestRides)-1].total > total*bestRides[len(bestRides)-1].lenOfRide {
			bestRides = append(bestRides, struct {
				r         *Ride
				lenOfRide int
				total     int
			}{r, lenOfRide, total})
			// shitty sort-of-correct-but-quite-incorrect way
			// of picking next best n rides
			n := 1
			if rand.Intn(max(1, int(N/5))) == 0 {
				n = 3
			}
			if len(bestRides) > n {
				bestRides = bestRides[len(bestRides)-n:]
			}
		}
	}
	// if bestRide != nil {
	// 	fmt.Printf("Picking %d %d -> %d %d\n", bestRide.a, bestRide.b, bestRide.x, bestRide.y)
	// }
	if len(bestRides) != 0 {
		for _, br := range bestRides {
			r := br.r
			r.used = true
			oldC := *c
			c.Update(r)
			Sched.Add(c)
			// recursion 101
			Choose(cumulativeScore+c.score-oldC.score, depth+1)
			Sched.RemoveAtIndex(c.pqindex)
			// pqindex is meaningless now but it's ok
			// it will be fixed when c is added again
			*c = oldC
			r.used = false
		}
	} else {
		// another car may still have other rides
		Choose(cumulativeScore, depth)
	}
	// add back the one we popped at beginning of function
	Sched.Add(c)
}

func solve() {
	rand.Seed(1)

	sort.Sort(ByEndtime(Rides))

	Sched = &prioq{}

	// create cars
	for i := 0; i < F; i++ {
		c := &Car{
			ID:      i,
			Arrival: 0,
			X:       0,
			Y:       0,
		}
		Cars = append(Cars, c)
		Sched.Add(c)
	}

	// start recursion
	Choose(0, 0)

	for _, c := range Cars {
		fmt.Fprintf(output, "%d", len(c.Rides))
		for _, ri := range c.Rides {
			fmt.Fprintf(output, " %d", ri)
		}
		fmt.Fprintf(output, "\n")
	}
	fmt.Printf("%d\n", bestTotalScore)
}

func main() {
	sample := os.Args[1]
	fileIn := sample + ".in"
	fileOut := sample + ".out"

	var err error
	input, err = os.Open(fileIn)
	if err != nil {
		panic(fmt.Sprintf("open %s: %v", fileIn, err))
	}
	output, err = os.Create(fileOut)
	if err != nil {
		panic(fmt.Sprintf("creating %s: %v", fileOut, err))
	}
	defer input.Close()
	defer output.Close()

	// Global
	R = readInt()
	C = readInt()
	F = readInt()
	N = readInt()
	B = readInt()
	T = readInt()

	for i := 0; i < N; i++ {
		Rides = append(Rides, &Ride{
			ID: i,
			a:  readInt(),
			b:  readInt(),
			x:  readInt(),
			y:  readInt(),
			s:  readInt(),
			f:  readInt(),
		})
	}

	solve()
}

func readInt() int {
	var i int
	fmt.Fscanf(input, "%d", &i)
	return i
}

func readString() string {
	var str string
	fmt.Fscanf(input, "%s", &str)
	return str
}

func readFloat() float64 {
	var x float64
	fmt.Fscanf(input, "%f", &x)
	return x
}

// Prioq

// Invariant: both children are bigger

type prioq struct {
	bintree []*Car
}

func (pq *prioq) Add(car *Car) {
	pq.bintree = append(pq.bintree, car)
	pq.bintree[len(pq.bintree)-1].pqindex = len(pq.bintree) - 1

	// Rebalance tree to respect invariant
	var i = len(pq.bintree) - 1
	var p = (i - 1) / 2
	for p >= 0 && pq.bintree[p].Arrival > pq.bintree[i].Arrival {
		pq.bintree[p], pq.bintree[i] = pq.bintree[i], pq.bintree[p]
		pq.bintree[p].pqindex = p
		pq.bintree[i].pqindex = i
		i = p
		p = (i - 1) / 2
	}
}

func (pq *prioq) RemoveAtIndex(k int) *Car {
	if len(pq.bintree) == 0 {
		return nil
	}

	if k == len(pq.bintree)-1 {
		elem := pq.bintree[k]
		pq.bintree = pq.bintree[:k]
		return elem
	}

	pq.bintree[k].pqindex = -1
	elem := pq.bintree[k]
	// Put last element at hole
	pq.bintree[k] = pq.bintree[len(pq.bintree)-1]
	pq.bintree[k].pqindex = k
	// Remove last element
	pq.bintree = pq.bintree[:len(pq.bintree)-1]

	//        1                  9
	//    10     9	         10     12
	//  11 12   13 14  ->  11 12   13 14
	// 12

	// Rebalance tree to respect invariant
	len := len(pq.bintree)
	i := k
	left, right := 0, 0
	for {
		left = 2*i + 1
		right = 2*i + 2
		if left < len && right < len { // Two children
			if pq.bintree[left].Arrival <= pq.bintree[right].Arrival {
				if pq.bintree[i].Arrival <= pq.bintree[left].Arrival {
					break // Inferior to both children
				} else {
					pq.bintree[i], pq.bintree[left] = pq.bintree[left], pq.bintree[i]
					pq.bintree[i].pqindex = i
					pq.bintree[left].pqindex = left
					i = left
				}
			} else {
				if pq.bintree[i].Arrival <= pq.bintree[right].Arrival {
					break // Inferior to both children
				} else {
					pq.bintree[i], pq.bintree[right] = pq.bintree[right], pq.bintree[i]
					pq.bintree[i].pqindex = i
					pq.bintree[right].pqindex = right
					i = right
				}
			}
		} else if left < len { // One child (left)
			if pq.bintree[i].Arrival <= pq.bintree[left].Arrival {
				break // Inferior to only child
			}
			pq.bintree[i], pq.bintree[left] = pq.bintree[left], pq.bintree[i]
			pq.bintree[i].pqindex = i
			pq.bintree[left].pqindex = left
			i = left
		} else { // No child
			break
		}

	}

	return elem
}

func (pq *prioq) Pop() *Car {
	return pq.RemoveAtIndex(0)
}

func (pq *prioq) empty() bool {
	return len(pq.bintree) == 0
}