Round 51: Tree Coloring

Root level: (k chooses 1 + # neighbor) Other non-leaves level: (k - 2 chooses # neighbors) leaf level : 1

The answer is the product of all. Note need to calcualte N choose k in linear time

Round 49: Max Substring

count # of appearance for each char. For each char in a-z, we increase the length of guesses 1 by 1, until we hit prev same char or reachs index -1, or the position at that char is different

Round 49: Amusement Park

DP on the expected value, Ex(t, a). Note the boundary coniditon => Ex(0, x) = 0

Ex(t, a) = 1 + Pr(t, a) * (Ex(t, a + 1)) + (1 -Pr(t, a)) * Ex(t -1, a +1)

Round 47: Gcd Rebuild

Init base U, V factors to 1 For each V, just calculate the LCM of the i-row. For each U, just calculate the LCM of the i-column.

Note that we act greedily here, if other numbers are possibles, they must be a multiple of LCM anyway. So we just try LCM to reduce the likelyhood of OOB

And then run through the UV matrix again to verify

Round 47: Expected Merge

DP on Ex(l), use a vector to store the length, since each will be visited only once. The overall cost will be same as merge sort

Consider calc(l)

for i in  0 to l
ans[i] += l

calc(l/2)

if(l is even){

for (j, 0, l/2)
	ans[j] += Ex(j, l/2)

for(j, 0, l/2)
	ans[l/2 + j] += Ex(j, l/2)
}else if(l is odd){

calc(l/2 + 1)

for (j, 0, l/2)
	ans[j] += 1/2(Ex(j, l/2) + Ex(j, l/2 + 1)

//middle one is special
ans[l/2]  = 1/2(Ex(l/2 - 1, l/2) + Ex(0, l/2 + 1))

for(j, 0, l/2){
	ans[l/2  + 1 + j] += 1/2(Ex(j, l/2) + Ex(j + 1, l/2 + 1)) 
}

Round 54: Pair Swap

Maintain a heap of next k entries, we will swap with current head and break if

  1. heap top < current head

  2. heap top is maximal in the heap, but within the range

The moment we find it we can stop

Note: official solution uses a dequeue!!!

  1. maintain a dequeue s.t. elements forms an increasing sequence, i.e., i < j and a[i] < a[j], with the last entry being a[i + k]
  2. every time we seen a new entry, we add a[i+k] to the tail of the queue, after we pop the tail to remove bad ones
  3. becaues we moved i to the left, and i < j and a[i] < a[j], the head of the queue may be i itself (valid in the last iteration but not this one anymore) => so we need to pop it

Round 54: Spanning Trees

We can construct tree in two parts: 1. share nothing, 2. share everything => i.e., if we have solution for (N,K), we also have a solution for (N+1, K+1) => we just add an external node

share nothing works when N >= 4, when N = 1 , 2, or 3, we can just brute force

Round 52: Virus on a Tree

calcuate subtree size, sort by size, for each cut one, traverse to mark as cut already

Note in implementaion, we can pass a canSave flag, and save only the root of possible tree to cut, and add the root/size to a list

Round 52: Game on a Circle

check 1, 12, 23,…, 89 until we find the first black. if no black so far, then we know b = 9, 9 and 19 would be black

upon finding a black c[i],

when i is not the first entry we tried
we check c[i - 1]. 
	if c[i - 1] is white, we check c[i+ 1] 
		if  c[i + 1] is black, we know value of a, we also know that a[i + 10] can not be black, so does a[i + 20....]
		if c[i + 1] is white, then we know the value of b, and you know c[i - 9]....c[i - 1] can not be black, because a >= i - 9 or  < i - 10 - 10  
	if c[i-1] is black, if know c[i - 11] is white, we can try all other 9 * c[i - 11 + n * 10].
		
when i is the the first entry we tried
	keep going until we reach the second black si, then we can try si + 10....skip mod = i...skip mod = si

Official solution

  1. imagine the game as a 10 * 10 grid!!!
  2. ask 0, 11, 22,….99, until we have two blacks
  3. if we have 2 blacks, we know those two columns might be back, so we just try the other 9 columns
  4. If we have only 1 black, we know that column might be black, so we just try all remaining columns

Round 51: Manhattan Distances

Manhattan distance is similar to the idea of linear two, a + b >= c, and then we can fix (0, 0) and (0, c), and make the third point (x, y) s.t.

  1. x + y = a

  2. b - x + y = c

Note that if a soution exists, the a+ b+ c is even, because consider x1 < x2 < x3, the total value is 2 * (x3 - x1) + 2 * (y3 - y1) (Note, xi and yi may not belong to the same point!)