761D: Dasha and Very Difficult Problem

My Idea: bsearch

We can bsearch on the max value in C, since we know it will be <= 1e9

For each maximum C value, we can try from n-th biggest to 1-th,

	1. current c entry value, cv < previous c value
	2. b = a - cv, and b is in [l, r], i.e., we set cv = min(prev cv -1, a + l)
	3. If cv < a - r, we know our guess is too slow

Official: greedy

we know that for each c, it must be within the range of [ac-r, ac-l], also, it must be within the range of [aPrevC-r -1, aPrevC-l -1], just iterate through n to 1.

The solution exists if no bound overlaps. Once we have c, we can easily get b.

762C: Two strings

For each prefix of a, calculate longest b prefix that it can form a subsequence

For each suffix of a, calculate longest b suffix that it can form a subsequence

calculate max(prefixL[i] + prefixL[i+1]), buy checking all i in [0, n-1)(!!!)

Note

1. the offical calculates in the other direction, i.e., given a prefix of b, what is the minimum prefix of a we need? And it will do a two pointer scan from the B side, until the total length of A required less than A.size()

2. The problem with my approach is that I have to worry about cases 1. b is a substring of a, and 2. only a prefix or a suffix is needed, but not both

754D: Fedor and coupons

sort the start and end points, and keep track of how many levels we have at each event. Update the start and end segment when level becomes k and k - 1, respectively.

Note we should process the leave events first before start events at the same point

In the end, scan through segments for the first k that has start <= seg start and end >= seg end