232A: Cycles

Keep caluculating the complete graph, and populate matrix of said complete component

Official solution

29C: Mail Stamps

Build a graph, and dfs with a root with degree 1

346B: Lucky Common Subsequence

lcp[i][j][k] = longset common subseqeucne in s1[1..i] and s2[1…j], with the suffix the first k letters of visit

if(s1[i] != s1[j]){
	lcp[i][j][k] = max(lcp[i -1][j][k], lcp[i][j-1][k]) 
}else{

	if(s1[i]  == 'v'){
		lcp[i][j][1] = max(lcp[i-1][j-1][0..4])
	}else if s1[i] == 'i' {
		lcp[i][j][2] = lcp[i-1][j-1][1]
		lcp[i][j][0] = max(lcp[i-1][j-1][0,,2,3,4])
	}else if s1[i] == 'r' {
		lcp[i][j][3] = lcp[i-1][j-1][2]
		lcp[i][j][0] = max(lcp[i-1][j-1][0,1,,3,4])
	}else if s1[i] == 'u' {
		lcp[i][j][4] = lcp[i-1][j-1][3]
		lcp[i][j][0] = max(lcp[i-1][j-1][0,1,,3,4])
	}else if s1[i] == 's'{
		lcp[i][j][0] = max(lcp[i-1][j-1][0,1,2,3])
	}else {
		lcp[i][j][0] = max(lcp[i-1][j-1][0,...4])
	}
}

321B: Ciel and Duel

  1. either we destroy all defense card and attack card or we just pick a few attack cards only

  2. if we try destroying all D’s cards, we will try to match as close to the defense card as possible, and then match as close as possible the attach card. If feasible, the answer is total of remaining attacks cards after step1 - total of D’s attach cards

  3. the decide how many attack cards we destroy, we have to brute force on how many 1..i, sorted by strength, of D’s attack card.

Official solution

770D: Draw Brackets!

During the bracket matching process

  1. Keep track of which level the bracket is at

  2. Keep track of max level all together

  3. We add a space only for the, i.e., the matching [ is next to ]

223A: Bracket Sequence

maintain a balance of strings, on each closing ones, we can calculate

  1. the current length of the string, by peeking at the top of stack’s pos

  2. how many [ we have in this substring => by pre-calcuing a prefix sum

In the end we just find the best solution

343D:Water Tree

Uses segment tree

372B: Counting Rectangles is Fun

Note that q will dup # of possible cells, so we just brute force calculate if (i, j, k, l) is a properrectangle in O(n^4)

After this, we can use a 4D consecutive sums!!!

792D: Paths in a Complete Binary Tree

  1. Up: find the right most 1 bit, change this bit to 0, check the bit to its left, mark it 1

  2. Left: find the rightmost 1 bit, change the bit to the right to 1, mark cur bit to 0

  3. Right: similar to left, except we leave curbit alone