D - Harlequin

  • One state is “some has odd”, it is counter is “all have even”, and it maps to win/lose conditions

C - Align

  • It is obvious the solution will be zigzaged. Therefore, we can generate a formula for the final answer
  • we can store and sort the coefficents, and apply it to the sorted factors - way cleaner than my classification solution

B - Simplified mahjong

  • When A[i] != 0, it is obvious the anser will be floor(S/2) - by sorting and we will reach the upper bound
  • When A[i] == 0, we know the problem can be decomposed into segments
  • So we just sort the cards, and calcuate the size of 0-separated segments, and sum up the result applied by (1)

D - Coloring Dominoes

  • first col needs classification
  • I miscounted 2 * 2 + 2 * 2 case, should have 3 choices instead of 2

C - Base -2 Number

  • Classify based on the mod 4, 00, 01, 10, 11, add 4 to the original number before shifting

B - ABC

  • Replace BC with D and for a list of new strings
  • The inverse cost can be calculated by scan/bubble sort, every time we find a need to swap, the cost is increased by the number of to-be-swapped items

D - Blue and Red Balls

  • Star and band. Separating K into i empty buckets (could be empty) has choose(K + i - 1, K) ways, in the non empty case it becomes (K - 1, K - i). Note it is a direct application of formula
  • My first guess was incorrect. It was too high, and didn’t consider combiniation case

D - Coloring Edges on Tree

The official approach is cleaner than mine

  • We know that answer >= deg(v). In fact, max(deg(v)) is sufficient to give a solution
  • We can just BFS, add keep assigning the color form 1 to K while skipping the color of the edge from grand parent to parent. Such construction ensures the conditions are satisfied
  • Note that DFS is not feasible here because we lose the coloring information on siblings

E - Colorful Hats 2

The key insight is that given colors in 1…i, the color in i+1, can be uniquely determined by picking one color same as the predecessor. The mulitplication factor acts as the “pick”

Index 0 acts as the sentinel value

I got WA in formula - tried to classify 2 color and 3 color case. This implys at the each index, the pick is not unique even with the multiplier - classic anti pattern

D - Lucky PIN

The official brute force solution is cleaner than mine


for i in range(100):
	ds = [i/100, (i/10)%10, i% 10]
	find = 0 
	for i in range N:
		if match:
			find+=1

	if find == 3:
		ans+= 1

It also has a DP approach with 240M ops and 240M memory

C - HonestOrUnkind2

The official soultion is cleaner than mine. Mainly because even if I used bitmask, I still use a second array to track correctness, which is not needed, due to the bit mask

B. Counting of Trees

For reason unknown, i implemented count in a very verbose way…Just a simply dict and update is enough. Although, I missed the check where D[0] has to be 0 due to the condition in the problem

D. Disjoint Set of Common Divisors

The answer is the prime factorization of the GCD. Note that prime factorization can run in sqrt(N), and after sqrt(N), if the number is not 1, then we know that number is the only divisor left, and it is prime.

Proof: by contradiction

  • suppose that remaining number is not prime, then we should have divied it in the previous step, where all divisors no more than sqrt(N) have been discoverd
  • Because it is prime, we know it is the only possible divisor left, otherwise, it would be a product of two divisors > sqrt(n) => contradiction
  • Note by this proof, during coding we don’t have to limit the upperbound to tight sqrt(n), as long as we exhause all divisors under an upperbound it still holds

A - 01 Matrix

A construction solution that I was not able to come up with. One lesson learned is that in matrix solutions, at least one of row or column is “nicely” cut into bands (as min number as possible), and then we twist the other dimension to fit the requirements

C - Strawberry Cakes

The insight is similar to above, cut the matrix into bands and then twist it in the other dimension. Otherwise, implementation will be messy

D - Powerful Discount Tickets

  • I used the bsearch approach. One case to cover is when the remainng tickets are not enough to cover all tickets
  • Official solution uses PQ, the key insight is that floor(X/2 ** Y) = floor(floor(X/2 ** (Y-1))/ 2)

D - Ki

  • Python version gives TLE. C++ version is fine
  • Note that when we traverse trees, after we visit the node, we init the children properties on the spot, i.e., every time we reach a node, all its parent/parent edge info has been known

A - Triangle

  • The key insight that I missed is that suppose one vertex is at (0, 0), then the area of the triangle is abs(x2 * y3 - x3 * y2)/2
  • Another key insight is to set another ONE coordinate to 1 and the other 10^9 to cover the max value case, so we convert to Euclidian divison formula: 
      a = bq + r = b(q+ 1) - (b - r)

However, I still don’t understand why I need an additional %b to pass the last test case

D - Enough Array

  • Idea 1: prefix sum with bsearch
  • Idea 2: two pointers. Note that when you move the head pointer, the checked index should be i instead of i + 1