Round 24: Black White Necklace

pre-calc marble length, then do a two pointer on subarray

Round 24: BST Fixed Height

ways(h) = totalways(h - 1) * ways(h-1) * 2 ways(1) = 1

and then update totalWays(h)

Round 23: Permutation Matrix

calculate the cycle of each permutation index. Note that the “intro to cycle” case won’t happen!!! Can use partial sum to speed up computation

Round 23: Disk Mechanism

Note that if we fix the first disk’s width, all remaining ones are fixed too

maxR(i) = min(ub(i), x[i] - x[i-1] - minR(i-1)) minR(i) = max(lb(i), x[i] - x[i - 1] - maxR(i-1))

Official solution

Given the first radius X, we can express the each individual radius as X plus list of deltas so we can calulate the range of each constarint, and take the intersection of all of them!!!

Round 22: Black Shapes

calculate size of each component, for each cell, see if possible to connect to another cell with manhattan distance two speical case:

  1. full graph already

  2. no possible connection

Official solution

Alteratively, we can just iterate through each white cell, and check its neighbors possible from two separate components => and sum-up the answer!!!

Round 21: Max Wave Array

The arragnement would be 1, 3, 2, 5 , 4

Round 20: City Upgrades

bsearch on the max distance, to see if k is enough

Round 20: Stepping Number

We need to answer the q: how many stepping #s <= n. Then we bsearch on the minum number s.t nsn(i) - nsn(n) = k

To calculate # of steping #s <= n, ways(i) = # of stepping number <= n, with the first i - 1 digits a prefix of n, i.e, stepping numbers <= n but >= prefix * base power ways(n, i) = free(a[i] - 1, size - i) + ways(n, i + 1)

The final answer is ways(n, 0)

Official dp state

ways(i, j, k) = first i digits, last digit being j, k is 0 or 1, marks if the first i digits is following the prefix

Round 29: Equality

Note that after each operation, the total sum does not change. Thus, in the extreme case all will be floor(sum/N) or floor(sum/N) + 1. Therefore, the upper cut offline must be in (floor(sum/N) + 1, curMax).

Moreover, we notice that in this range, there exists a highest possbile upper cutoff line, so we can bsearch on the upper cut off line

Official solution

Note that A(i) is 10^5, so trying it one by one is feabile!!! so we maitain a frequency list, at each step, we operate the min(MaxFa, MinFa) times. This guarantees that K is reduced by 1

Round 29: Odd Palindromes

  1. the format must be of form ABABA…, where odd and even indicies can be considered independently

  2. obviously, in the final solution, we want to convert number to current most frequent number.

I got stuck here - suppose I am at i, and the most frequent char is not popular enough, what should I do?!!! =>

For each i, we just try the most frequenct number in the (L,R), range, if we are unable to, that means we include too much noice, thus, we need to move L to the right by 1, and update the most frequent count

Round 28: Card Shuffle

for each index -i, calculate cycle length. each card appear only once in the cycle - so linear

Note that the cycle can’t have the leading trail problem, because otherwise, the existing one will run into a collsion with the starting one if we run it infinite numbers => i.e., start1 + x * c1 =start2 + x * c2 always exist a solution

Round 28: Water Bottles

Idea 1: binary search!!! since we want to raise the water level gradually, we can bsearch on the final min water levels we want to reach. If the total volumn > L, our level is too high. so we will find the max min water level, s.t., total water consumed <= L. Note that = L may not always achieved

If total water consumed < L, we just pour 1 unit of reamining water to each remaining that has capacity. Note that

Idea 2: event based!!! Two possible events

  1. we need to stop pouring a bottle because we reach max

  2. We need to start pourting a bottle because we reach another min

So we can order by the events, and iterate them

a. upon seeing a max level event, we reduce the # of bottles receiving

b. upon seeing a min level event, we increase the # of bottles receiving

between the events, we calcuate the amount of water used = level delta * # of bottles receiving

Round 27: Huge Matrix

standard band overlap problems, with a frequencey map to help state. Note that we can solve it with path compression too, just need to watch out for the case where the update interval is less than the current next. In that case we just ignore.

Round 27: X Distance

We can consider edge only < X Consider the case where X = max edge length, then we know a max edge must be a bridge so that it can contribute to a final number. If it is not a bridge, it must be within a cycle

Official solution

Min dist = X = # of pairs with distance at most X - # of paris with distance at most X - 1!!!

To calcualte at most(x), we, just take out all edges >= x, and check what is connected.

Round 26: Bounded Distinct

small variable of a two pointer problem

Round 26: Build the Towers

  1. for first and last element, can only be 0,1,2
  2. 1, 2, 3 can NOT be continues by the rule
  3. 3 is as powerful as 0 in terms of rule pwoer

Insight I missed: if we built a number, the neighbors smaller than that will be erased to 0!!!

Intuition is that build 0130 is more expensive than 0310, if we scan from left to right.

Experiementing by brute force shows that building higher number than lower number is always cheaper than the lower than higher => some numbers will be preserved

Round 25: Rectangle Path

BFS on rectangle, and ignore the points that could potentially invalid. Invalid check can be done , by calculating prefix sums of bad spots

Round 25: min-ends-subsequence

In an optimal solution,

  1. In the optimal solution, the left border must have all precediing < the border

  2. the right boder must have all following < the border

The key insight is that give X, we find the longest min-end subsequence to include as many elements <= X as possible!!!

The optimal way is to find (L, R) s.t. L is the first element >= X and R is the last element >= x, and easy to see the length of subsequence is R - L + 1.

To optimize it, we can proceed from min to max X, because as X increases, (L, R) will just narrow down