149C: Division into Teams

Sort the players by score, then biggest one goes to team A, and next one goes to team B.

Claim: This arrangement satisifes the conditions

Proof: Obviously condition 1 and 2 hold, and obviously s(B) < s(A)

If A > B , i.e. total number is odd, s(A) < s(B) + MaxP,
If A = B , i.e., total number is even, s(A) - MaxP < s(B), i.e., s(A) - s(B) <= MaxP

Can also proved in a geometrics way

107A: Dorm Water Supply

Since each house has at most 1 in and out edges, for each node, we can keep track of prev and next node, and start with nodes where prev[node] = node, and find the most narrow pipe

255C: Almost Arithmetical Progression

Case q = 0 ———- just just the element with highest count

Case q != 0

For each element, try it as p

Linear scan, for each p, maintain 2 length[i], current subsequence length, state[i], min index of p needed to increase the subsequence length

If a[i] = p, update lastPI

If a[i] != p

	1. get the id for current value
	
	2. check the needPI[id], if it is >= lastPI, do nothing, note that needPI is init to -1

	3. otherwise, length[id]++, and needPI[id] = i + 1

Then scan from the tail, find the position of the last p and second last p, for all number between them, length[id]++

and then find the highest length

148D: Bag of mice

Pr(p, w, b) = Pr(white) + (1 - Pr(white)) (1 - Pr(d, w, b-1))

Pr(d, w, b) = Pr(white) + (1 - Pr(white)) (Pr(white jumps) * (1 - Pr(p, w - 1, b-1)) + Pr(black jumps) * (1 - Pr(p, w, b-1))

Pr(p, 0, i) = 0

Pr(p, i, 0) = 1

Pr(d, 0, i) = 1

Pr(d, i, 0) = 1

616D: Longest k-Good Segment

When we try adding the current element to the segment


	1. If a[i] is in the set already, move the right pointer, update the right most index for that value, and the current best length

	2. Otherwise, move the left pointer, until the left pointer is greater than the right most index of that value. Also, remove that value from the set, and add a[i] to the set