2018-1B Problem B

Final solution

// package, import, etc...

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

type Sign struct {
	d               int
	a, b            int
	m, n            int
	mLen, nLen      int
	setWithThisMLen int
	setWithThisNLen int
}

func test() {
	var numSigns int
	mustReadLineOfInts(&numSigns)
	signs := make([]Sign, numSigns)
	for i := 0; i < numSigns; i++ {
		var d, a, b int
		mustReadLineOfInts(&d, &a, &b)
		m := d + a
		n := d - b
		signs[i] = Sign{d, a, b, m, n, 0, 0, 0, 0}
		// debug(fmt.Sprintf("m=%v, n=%v", m, n))
	}
	maxValidSetLen := 0
	maxSetCount := 0
	// mLen pass
	for i := 0; i < len(signs); {
		currentM := signs[i].m
		mLen := 0
		for ; i+mLen < len(signs) && signs[i+mLen].m == currentM; mLen++ {
		}
		for j := i; j < i+mLen; j++ {
			signs[j].mLen = mLen - (j - i)
		}
		i += mLen
	}
	// nLen pass
	for i := 0; i < len(signs); {
		currentN := signs[i].n
		nLen := 0
		for ; i+nLen < len(signs) && signs[i+nLen].n == currentN; nLen++ {
		}
		for j := i; j < i+nLen; j++ {
			signs[j].nLen = nLen - (j - i)
		}
		i += nLen
	}

	for i := 0; i < len(signs); i++ {
		startSign := &signs[i]
		var setSize, m, n int
		var mSet, nSet bool
		continueWith := func(checkM bool) int {
			initCheckM := checkM
			sLen := 0
			for i+sLen < len(signs) {
				s := &signs[i+sLen]
				if checkM {
					if s.setWithThisMLen != 0 {
						sLen = s.setWithThisMLen
						return sLen
					}
					if mSet && s.m != m {
						break
					} else if !mSet {
						m = s.m
						mSet = true
					}
					sLen += s.mLen
				} else {
					if s.setWithThisNLen != 0 {
						sLen = s.setWithThisNLen
						return sLen
					}
					if nSet && s.n != n {
						break
					} else if !nSet {
						n = s.n
						nSet = true
					}
					sLen += s.nLen
				}
				checkM = !checkM
			}
			// set setWithThisM/NLen
			checkM = initCheckM
			newSLen := sLen
			nextFlip := -1
			if checkM {
				nextFlip = i + signs[i].mLen
			} else {
				nextFlip = i + signs[i].nLen
			}
			for j := i; j < i+sLen; j++ {
				s := &signs[j]
				if j == nextFlip {
					checkM = !checkM
					if checkM {
						nextFlip += s.mLen
					} else {
						nextFlip += s.nLen
					}
				}
				if nextFlip >= i+sLen {
					break // ignore last segment.
				}
				if checkM {
					s.setWithThisMLen = newSLen
				} else {
					s.setWithThisNLen = newSLen
				}
				newSLen--
			}
			return sLen
		}
		m = startSign.m
		mSet = true
		nSet = false
		a := continueWith(true)
		n = startSign.n
		nSet = true
		mSet = false
		b := continueWith(false)
		setSize = max(a, b)
		if maxValidSetLen < setSize {
			maxValidSetLen = setSize
			maxSetCount = 1
		} else if maxValidSetLen == setSize {
			maxSetCount++
		}
	}
	// debug(fmt.Sprintf("%v", signs))
	fmt.Fprintf(stdout, "%d %d\n", maxValidSetLen, maxSetCount)
}

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

// boilerplate omitted...

Wrong solutions

wrong-1

// package, import, etc...

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

type Sign struct {
	d          int
	a, b       int
	m, n       int
	mLen, nLen int
}

func test() {
	var numSigns int
	mustReadLineOfInts(&numSigns)
	signs := make([]Sign, numSigns)
	for i := 0; i < numSigns; i++ {
		var d, a, b int
		mustReadLineOfInts(&d, &a, &b)
		m := d + a
		n := d - b
		signs[i] = Sign{d, a, b, m, n, 0, 0}
		// debug(fmt.Sprintf("m=%v, n=%v", m, n))
	}
	maxValidSetLen := 0
	maxSetCount := 0
	for i := 0; i < len(signs); i++ {
		sign := &signs[i]
		m, n := sign.m, sign.n
		mLen := 0
		nLen := 0
		mBreak := false
		nBreak := false
		for j := i; j < len(signs); j++ {
			if signs[j].m == m && !mBreak {
				mLen++
			}
			if signs[j].n == n && !nBreak {
				nLen++
			}
			if signs[j].m != m {
				mBreak = true
			}
			if signs[j].n != n {
				nBreak = true
			}
			if mBreak && nBreak {
				break
			}
		}
		sign.mLen = mLen
		sign.nLen = nLen
	}
	for i, sign := range signs {
		setSize := 0
		if sign.mLen > sign.nLen {
			if i+sign.mLen == len(signs) {
				setSize = sign.mLen
			} else {
				setSize = sign.mLen + signs[i+sign.mLen].nLen
			}
		} else if sign.mLen < sign.nLen {
			if i+sign.nLen == len(signs) {
				setSize = sign.nLen
			} else {
				setSize = sign.nLen + signs[i+sign.nLen].mLen
			}
		} else {
			if i+sign.mLen == len(signs) {
				setSize = sign.mLen
			} else {
				nextSign := signs[i+sign.mLen]
				setSize = sign.mLen + max(nextSign.mLen, nextSign.nLen)
			}
		}
		if maxValidSetLen < setSize {
			maxValidSetLen = setSize
			maxSetCount = 1
		} else if maxValidSetLen == setSize {
			maxSetCount++
		}
	}
	fmt.Fprintf(stdout, "%d %d\n", maxValidSetLen, maxSetCount)
}

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

// boilerplate omitted...

wrong-2

--- wrong-2/cmd.go	2019-04-29 19:52:34.056966100 +0800
+++ wrong-3/cmd.go	2019-04-29 19:52:34.057947600 +0800
@@ -92,25 +92,15 @@
 			}
 			return sLen
 		}
-		if startSign.mLen > startSign.nLen {
-			m = startSign.m
-			mSet = true
-			setSize = continueWith(true)
-		} else if startSign.mLen < startSign.nLen {
-			n = startSign.n
-			nSet = true
-			setSize = continueWith(false)
-		} else {
-			m = startSign.m
-			mSet = true
-			nSet = false
-			a := continueWith(true)
-			n = startSign.n
-			nSet = true
-			mSet = false
-			b := continueWith(false)
-			setSize = max(a, b)
-		}
+		m = startSign.m
+		mSet = true
+		nSet = false
+		a := continueWith(true)
+		n = startSign.n
+		nSet = true
+		mSet = false
+		b := continueWith(false)
+		setSize = max(a, b)
 		if maxValidSetLen < setSize {
 			maxValidSetLen = setSize
 			maxSetCount = 1

wrong-3

--- wrong-3/cmd.go	2019-04-29 19:52:34.057947600 +0800
+++ small/cmd.go	2019-05-02 16:14:44.682000000 +0800
@@ -78,6 +78,7 @@
 						break
 					} else if !mSet {
 						m = s.m
+						mSet = true
 					}
 					sLen += s.mLen
 				} else {
@@ -85,6 +86,7 @@
 						break
 					} else if !nSet {
 						n = s.n
+						nSet = true
 					}
 					sLen += s.nLen
 				}

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

Solution that only works for the small input

// package, import, etc...

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

type Sign struct {
	d          int
	a, b       int
	m, n       int
	mLen, nLen int
}

func test() {
	var numSigns int
	mustReadLineOfInts(&numSigns)
	signs := make([]Sign, numSigns)
	for i := 0; i < numSigns; i++ {
		var d, a, b int
		mustReadLineOfInts(&d, &a, &b)
		m := d + a
		n := d - b
		signs[i] = Sign{d, a, b, m, n, 0, 0}
		// debug(fmt.Sprintf("m=%v, n=%v", m, n))
	}
	maxValidSetLen := 0
	maxSetCount := 0
	for i := 0; i < len(signs); i++ {
		sign := &signs[i]
		m, n := sign.m, sign.n
		mLen := 0
		nLen := 0
		mBreak := false
		nBreak := false
		for j := i; j < len(signs); j++ {
			if signs[j].m == m && !mBreak {
				mLen++
			}
			if signs[j].n == n && !nBreak {
				nLen++
			}
			if signs[j].m != m {
				mBreak = true
			}
			if signs[j].n != n {
				nBreak = true
			}
			if mBreak && nBreak {
				break
			}
		}
		sign.mLen = mLen
		sign.nLen = nLen
	}
	for i, startSign := range signs {
		var setSize, m, n int
		var mSet, nSet bool
		continueWith := func(checkM bool) int {
			sLen := 0
			for i+sLen < len(signs) {
				s := signs[i+sLen]
				if checkM {
					if mSet && s.m != m {
						break
					} else if !mSet {
						m = s.m
						mSet = true
					}
					sLen += s.mLen
				} else {
					if nSet && s.n != n {
						break
					} else if !nSet {
						n = s.n
						nSet = true
					}
					sLen += s.nLen
				}
				checkM = !checkM
			}
			return sLen
		}
		m = startSign.m
		mSet = true
		nSet = false
		a := continueWith(true)
		n = startSign.n
		nSet = true
		mSet = false
		b := continueWith(false)
		setSize = max(a, b)
		if maxValidSetLen < setSize {
			maxValidSetLen = setSize
			maxSetCount = 1
		} else if maxValidSetLen == setSize {
			maxSetCount++
		}
	}
	fmt.Fprintf(stdout, "%d %d\n", maxValidSetLen, maxSetCount)
}

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

// boilerplate omitted...

Sample test cases given in question

3
1
1 1 1
5
2 7 12
6 3 11
8 10 1
11 11 12
13 9 14
5
1 3 3
2 2 2
3 1 1
4 2 2
5 3 3

Other files

Case #1: 6 1