2017-1A Problem B

Final solution

// package, import, etc...

func start() {
	var t int
	mustReadLineOfInts(&t)
	for i := 0; i < t; i++ {
		fmt.Fprintf(stdout, "Case #%d: ", i+1)
		if i == 27 {
			stdout.Flush()
		}
		fmt.Fprintf(stdout, "%d\n", test())
	}
}

type Package struct {
	qty      int
	canDoMin int
	canDoMax int
	circled  int
}

func (p *Package) calc(req int) {
	p.canDoMax = int(math.Floor(float64(p.qty) / (0.9 * float64(req))))
	p.canDoMin = int(math.Ceil(float64(p.qty) / (1.1 * float64(req))))
	if req*(p.canDoMax+1)*9/10 <= p.qty {
		p.canDoMax++
	}
	if req*(p.canDoMin-1)*11/10 >= p.qty {
		p.canDoMin++
	}
	if p.canDoMax == 0 {
		p.canDoMin = 0
		p.canDoMax = -1
	}
}

type Packages []Package

func (p Packages) Len() int {
	return len(p)
}

func (p Packages) Less(i int, j int) bool {
	return p[i].qty < p[j].qty
}

func (p Packages) Swap(i int, j int) {
	p[i], p[j] = p[j], p[i]
}

func test() int {
	var N, P int
	mustReadLineOfInts(&N, &P)
	reqs := mustReadLineOfIntsIntoArray()
	assert(len(reqs) == N)
	packages := make([]Packages, N)
	for i := 0; i < N; i++ {
		pkgs := make(Packages, P)
		q := mustReadLineOfIntsIntoArray()
		assert(len(q) == P)
		for j := 0; j < P; j++ {
			pkgs[j].qty = q[j]
			pkgs[j].calc(reqs[i])
		}
		sort.Sort(pkgs)
		newPkgs := make(Packages, 0, P)
		for _, pkg := range pkgs {
			if pkg.canDoMin <= pkg.canDoMax {
				newPkgs = append(newPkgs, pkg)
			}
		}
		packages[i] = newPkgs
	}
	for _, pkgs := range packages {
		if len(pkgs) == 0 {
			return 0
		}
	}
	debug(fmt.Sprintf("%v", packages))
	if N == 1 {
		return len(packages[0])
	}
	for i := 1; i < N; i++ {
		prevRow := packages[i-1]
		thisRow := packages[i]
		for {
			if len(prevRow) == 0 || len(thisRow) == 0 {
				break
			}
			if thisRow[0].canDoMax < prevRow[0].canDoMin {
				thisRow = thisRow[1:]
				continue
			}
			if thisRow[0].canDoMin > prevRow[0].canDoMax {
				prevRow = prevRow[1:]
				continue
			}
			if prevRow[0].circled != 0 && thisRow[0].canDoMax < prevRow[0].circled {
				thisRow = thisRow[1:]
				continue
			}
			if i != 1 {
				if prevRow[0].circled != 0 {
					assert(prevRow[0].canDoMin <= prevRow[0].circled)
					prevRow[0].canDoMin = prevRow[0].circled
					assert(prevRow[0].canDoMax >= prevRow[0].canDoMin)
				} else {
					prevRow = prevRow[1:]
					continue
				}
			}
			if thisRow[0].canDoMin < prevRow[0].canDoMin {
				prevRow[0].circled = prevRow[0].canDoMin
				thisRow[0].circled = prevRow[0].canDoMin
			} else {
				thisRow[0].circled = thisRow[0].canDoMin
				prevRow[0].circled = thisRow[0].canDoMin
			}
			assert(thisRow[0].circled >= thisRow[0].canDoMin)
			assert(thisRow[0].circled <= thisRow[0].canDoMax)
			assert(prevRow[0].circled >= prevRow[0].canDoMin)
			assert(prevRow[0].circled <= prevRow[0].canDoMax)
			thisRow = thisRow[1:]
			prevRow = prevRow[1:]
		}
	}
	lastRow := packages[N-1]
	debug(fmt.Sprintf("%v", packages))
	kits := 0
	for _, p := range lastRow {
		if p.circled != 0 {
			kits++
		}
	}
	return kits
}

// boilerplate omitted...

Sample test cases given in question

6
2 1
500 300
900
660
2 1
500 300
1500
809
2 2
50 100
450 449
1100 1101
2 1
500 300
300
500
1 8
10
11 13 17 11 16 14 12 18
3 3
70 80 90
1260 1500 700
800 1440 1600
1700 1620 900

Other files

2
2 2
5 10
45 50
110 111
2 3
50 100
449 450 500
1000 1100 1101