2018-1B Problem C

Wrong solution

// Works for: Test set 1 and 2

// This approach use binary search, answering the question "can we make n lead"?
// package, import, etc...

func start() {
  // read T, repeat test() T times...
}

type Metal struct {
	ing1, ing2 int
	hasAmount  uint
}

var metals []Metal
var totalSupply uint

func test() {
	var M int
	mustReadLineOfInts(&M)
	metals = make([]Metal, M)
	for i := 0; i < M; i++ {
		var ing1, ing2 int
		mustReadLineOfInts(&ing1, &ing2)
		metals[i].ing1 = ing1 - 1
		metals[i].ing2 = ing2 - 1
	}
	line := strings.Split(mustReadLine(), " ")
	assert(len(line) == M)
	for i := 0; i < M; i++ {
		ps, err := strconv.ParseUint(line[i], 10, 32)
		if err != nil {
			panic(err)
		}
		metals[i].hasAmount = uint(ps)
		totalSupply += metals[i].hasAmount
	}

	var l, r uint
	r = totalSupply + 1
	for r-l > 1 {
		m := (l + r) / 2
		if check(m) {
			l = m
		} else {
			r = m
		}
	}
	fmt.Fprintf(stdout, "%d\n", l)
}

func check(m uint) bool {
	wants := make(map[int]uint)
	wants[0] = m
	totalWanted := m
	for {
		unsatisfied := -1
		for want, amount := range wants {
			if metals[want].hasAmount < amount {
				unsatisfied = want
				break
			} else {
				metals[want].hasAmount -= amount
				delete(wants, want)
			}
		}
		if unsatisfied == -1 {
			return true
		}
		additionalWantedAmount := wants[unsatisfied] - metals[unsatisfied].hasAmount
		assert(additionalWantedAmount > 0)
		wants[unsatisfied] = wants[unsatisfied] - additionalWantedAmount
		if wants[unsatisfied] == 0 {
			delete(wants, unsatisfied)
		}
		wants[metals[unsatisfied].ing1] += additionalWantedAmount
		wants[metals[unsatisfied].ing2] += additionalWantedAmount
		totalWanted += additionalWantedAmount
		if totalWanted > totalSupply {
			return false
		}
	}
}

// boilerplate omitted...

Solution that only works for the small input

// Works for: Test set 1

// package, import, etc...

func start() {
  // read T, repeat test() T times...
}

type Metal struct {
	ing1, ing2 int
	hasAmount  uint
}

var metals []Metal

func test() {
	var M int
	mustReadLineOfInts(&M)
	metals = make([]Metal, M)
	for i := 0; i < M; i++ {
		var ing1, ing2 int
		mustReadLineOfInts(&ing1, &ing2)
		metals[i].ing1 = ing1 - 1
		metals[i].ing2 = ing2 - 1
	}
	hasAmounts := mustReadLineOfIntsIntoArray()
	assert(len(hasAmounts) == M)
	for i := 0; i < M; i++ {
		metals[i].hasAmount = uint(hasAmounts[i])
	}
	collectedZeroMetals := 0
	for {
		has := takeMetal(0, 0)
		if has {
			collectedZeroMetals++
		} else {
			break
		}
	}
	fmt.Fprintf(stdout, "%d\n", collectedZeroMetals)
}

type ExclusionList map[int]bool

func takeMetal(metal int, depth int) bool {
	target := &metals[metal]
	if target.hasAmount > 0 {
		target.hasAmount--
		return true
	}
	if depth > len(metals) {
		return false
	}
	tookIg1 := takeMetal(target.ing1, depth+1)
	tookIg2 := takeMetal(target.ing2, depth+1)
	if tookIg1 && tookIg2 {
		return true
	}
	if tookIg1 {
		metals[target.ing1].hasAmount++
	}
	if tookIg2 {
		metals[target.ing2].hasAmount++
	}
	return false
}

// boilerplate omitted...

// Works for: Test set 1 and 2

/*
Referring to small-1...

The first idea of improvement here is that, if we already have, let's say, 100 x and 100 y, and lead requires x and
y, we can directly duduct 100 from each of the supply of x and y, and add 100 to leadCollected, rather than calling
takeMetal 100 times.

The second idea here is to "cache" the result of going through the deep calling stack of `takeMetal`. For example, if
we had already found out that in order to get 1 we need 2 and 3, and in order to get 2 we need 4 and 5, next time we
can just say in order to get 1 we need 3, 4, and 5, one of each.

These two optimizations enables us to reduce needing to repeatly call takeMetal as much as possible...

But really, a better way to do it is the method in the analysis - maintain a optimal "recipe". Therefore this file
implements that approach.

Disclaimer: the above ideas are produced only after reading the analysis, in an attempt to learn how I can go about
improving an algorithm during a real contest.
*/

// package, import, etc...

func start() {
  // read T, repeat test() T times...
}

type Metal struct {
	ing1, ing2 int
	hasAmount  uint
}

var metals []Metal

func test() {
	var M int
	mustReadLineOfInts(&M)
	metals = make([]Metal, M)
	for i := 0; i < M; i++ {
		var ing1, ing2 int
		mustReadLineOfInts(&ing1, &ing2)
		metals[i].ing1 = ing1 - 1
		metals[i].ing2 = ing2 - 1
	}
	line := strings.Split(mustReadLine(), " ")
	assert(len(line) == M)
	var totalAmountHas uint = 0
	for i := 0; i < M; i++ {
		ps, err := strconv.ParseUint(line[i], 10, 32)
		if err != nil {
			panic(err)
		}
		metals[i].hasAmount = uint(ps)
		totalAmountHas += metals[i].hasAmount
	}
	recipe := make(map[int]uint) // recipe to make metal 0
	recipe[0] = 1                // requires 1 metal 0 to produce 1 metal 0 (initially)
	var zeroMetalsProduced uint
a:
	for {
		limitingMetals := make([]int, 0)
		var produceAmount uint = (1 << 32) - 1
		var totalNumRequired uint = 0
		for metalRequired, amountRequired := range recipe {
			totalNumRequired += amountRequired
			hasAmount := metals[metalRequired].hasAmount
			if hasAmount < amountRequired {
				limitingMetals = append(limitingMetals, metalRequired)
				produceAmount = 0
			} else {
				canProduceAmount := hasAmount / amountRequired
				if canProduceAmount < produceAmount {
					produceAmount = canProduceAmount
				}
			}
		}
		if totalNumRequired > totalAmountHas {
			break
		}
		if produceAmount == 0 {
			for _, mtLacking := range limitingMetals {
				metalLacking := metals[mtLacking]
				hasAmount := metalLacking.hasAmount
				additionalRequiredAmount := recipe[mtLacking] - hasAmount
				if hasAmount == 0 {
					delete(recipe, mtLacking)
				} else {
					recipe[mtLacking] = hasAmount
				}
				if metalLacking.ing1 == mtLacking {
					break a
				} else {
					recipe[metalLacking.ing1] += additionalRequiredAmount
				}
				if metalLacking.ing2 == mtLacking {
					break a
				} else {
					recipe[metalLacking.ing2] += additionalRequiredAmount
				}
			}
		} else {
			for metalRequired, amountRequired := range recipe {
				deduction := amountRequired * produceAmount
				assert(metals[metalRequired].hasAmount >= deduction)
				metals[metalRequired].hasAmount -= deduction
				totalAmountHas -= deduction
				assert(totalAmountHas >= 0)
			}
			zeroMetalsProduced += produceAmount
		}
	}
	fmt.Fprintf(stdout, "%d\n", zeroMetalsProduced)
}

// boilerplate omitted...

// Works for: Test set 1 and 2

// This approach use binary search, answering the question "can we make n lead"?
// package, import, etc...

func start() {
  // read T, repeat test() T times...
}

type Metal struct {
	ing1, ing2 int
	hasAmount  uint
}

var metals []Metal
var totalSupply uint

func test() {
	var M int
	mustReadLineOfInts(&M)
	metals = make([]Metal, M)
	for i := 0; i < M; i++ {
		var ing1, ing2 int
		mustReadLineOfInts(&ing1, &ing2)
		metals[i].ing1 = ing1 - 1
		metals[i].ing2 = ing2 - 1
	}
	line := strings.Split(mustReadLine(), " ")
	assert(len(line) == M)
	for i := 0; i < M; i++ {
		ps, err := strconv.ParseUint(line[i], 10, 32)
		if err != nil {
			panic(err)
		}
		metals[i].hasAmount = uint(ps)
		totalSupply += metals[i].hasAmount
	}

	var l, r uint
	r = totalSupply + 1
	for r-l > 1 {
		m := (l + r) / 2
		if check(m) {
			l = m
		} else {
			r = m
		}
	}
	fmt.Fprintf(stdout, "%d\n", l)
}

func check(m uint) bool {
	want := make(map[int]uint)
	want[0] = m
	totalWanted := m
	for {
		unsatisfied := -1
		for want, amount := range want {
			if metals[want].hasAmount < amount {
				unsatisfied = want
				break
			}
		}
		if unsatisfied == -1 {
			return true
		}
		additionalWantedAmount := want[unsatisfied] - metals[unsatisfied].hasAmount
		assert(additionalWantedAmount > 0)
		want[unsatisfied] = want[unsatisfied] - additionalWantedAmount
		want[metals[unsatisfied].ing1] += additionalWantedAmount
		want[metals[unsatisfied].ing2] += additionalWantedAmount
		totalWanted += additionalWantedAmount
		if totalWanted > totalSupply {
			return false
		}
	}
}

// boilerplate omitted...

Sample test cases given in question

3
3
2 3
1 3
1 2
5 2 3
5
3 4
3 4
4 5
3 5
1 3
0 8 6 2 4
4
3 4
2 3
2 3
2 3
0 1 1 0

Other files

--- wrong-1/cmd.go      2019-05-04 10:14:06.360786578 +0800
+++ cmd.go      2019-05-04 10:12:48.562777456 +0800
@@ -92,18 +92,23 @@
                }
                if produceAmount == 0 {
                        for _, mtLacking := range limitingMetals {
-                               requiredAmount := recipe[mtLacking]
-                               delete(recipe, mtLacking)
                                metalLacking := metals[mtLacking]
+                               hasAmount := metalLacking.hasAmount
+                               additionalRequiredAmount := recipe[mtLacking] - hasAmount
+                               if hasAmount == 0 {
+                                       delete(recipe, mtLacking)
+                               } else {
+                                       recipe[mtLacking] = hasAmount
+                               }
                                if metalLacking.ing1 == mtLacking {
                                        break a
                                } else {
-                                       recipe[metalLacking.ing1] += requiredAmount
+                                       recipe[metalLacking.ing1] += additionalRequiredAmount
                                }
                                if metalLacking.ing2 == mtLacking {
                                        break a
                                } else {
-                                       recipe[metalLacking.ing2] += requiredAmount
+                                       recipe[metalLacking.ing2] += additionalRequiredAmount
                                }
                        }
                } else {