Round 42: Prefix Matches

for each A[i], we know that B[i + A[i]] = max(A[j] , j + A[j] = i + A[i]), so we can through and upgrade it, then from n to 1, we maintain current length l, and B[i] = l, l–, or update l to the new B[i] if B[i] > l

Insight: when we update B[i], the first time it updates will have the highest value, because the staring index is at the left most position => prefix length is longest at this time

Round 42: Sorting Steps

Runtime Analysis is similar to a potential method. We defind cost(i) = number of entiers > a[i] to the left i. For each operation, cost[i] – for all cost[i] > 0, otherwise it means some bigger number is blocked. We continue this process until all cost(i) = 0. Therefore, overall # of steps = max(cost[i])

How to calculate max(cost[i]) without a complex data structure?!!!

Observations:

  1. If an entry has max(cost[i]), i must not have j > i and a[j] < a[i]. Otherwise, cost[j] > cost[i]
  2. Since all numbers < a[i] are to the left of i, cost[i] = i - real position

Round 56: Find Edge List

DAG Topological sort with cycle detection. I solved it slower than I expected.

  1. For cycle detection, maintain visited, visiting, unvisited state. Note for undirected graph, we just need 2 stages, and will find it the moment we reach a visited stage

  2. The inverse of the topological sort does not mean print before the depth. The counter exampe is A -> B <- C, the inverse of the topological sort should be A -> C -> B, but print it before going depth, we will hit, A-> B -> C

  3. Either add a fake node with edges to all nodes, or find a node with no incoming edges. Need to handle the case of every node has incoming edge -> a cycle already

Round 56: Find Path Union

Given the max #, we can know the max value of the tree, and the max level of the node, then we iterate from the max to min value => if current node is not in the set but its parent is, then we add max level - depth(node) to the sum. Final answer the total # of full tree - sum

Official solution

Remove child -> parent edge 1 by 1, starting from highest num. Answer++ if current node is in the list

So maintain 2 sorted lists, one is nodes to visit, one is ancestor’s node to visit, at each step, take the max of two lists, ans++, and put the new ancester to the parent list

Note:

  1. we can just use a q to implement sorted list, because node number is decreasing at this step, so its parent (nv/2) must be non-increasing as we progress!!!

  2. at every step, we just need to pop both q and vector on same values

  3. because each node has two children, the same q value may appear multiple times. Again, by 1), we know they will both be head of the list!!!

Round 46: Set Subtraction

Take the min number, and try all 1k possible X sort the numbers, scan from left to right, if num(a[i] ) > num(a[i] + X), bad, otherwise, reduce both a[i] and a[i] + X Note: we can use two pointer techinque here instead of sets, because the first pointer should never catch up with second one because x is positive !!!

Round 45: Remove Update

Use sweep line to calcuate the final results after all updates. and then calculate maxStart[i]= max value in 1…i, maxEnd[i] = max value in i….n

For each segment, the answer is max(maxSeg - segV, maxStart[i], maxEnd[i]), and we take the minimum.

Note that we can use the partial sum trick to simulate operations!!!

  1. calculate s[i] = a[1] +…..a[i]
  2. p[l] = v, p[r] = -v

Also, note that to minize max value, we need to consider intervals that contains all maximal values after applying all entries, which is also the max value we are looking for!!! Becaues if the interval does not cover all max As, then the remining max A entry will remain the new max value after removal. Even better, in implementation,we can just assume max value is such for ANY interval anyway, because those do not satify this will not affect our final results - maxStart and maxEnd will cover that!

Round 44: Check DFS

Idea 1

we start with the node, at every step. if p(i) and current stack top is an edge, we add it the stackkeep going. Otherwise, we pop the stack until we have it!, and then add to the stack

terminating condition is we go through all perms

Idea 2

If node v is visited before node u, then we know v can not appear after u in adjacency list. Therefore, we sort adjanent list by the order in permutation!!! In the end do a native DFS and compare orders

Round 44: Count Squares

consider each square parallel to axis, if the length is n, then we can form n squares within the square, each side with manhanttan distance n. Therefore, the answer is

1 * (x-1) (y - 1) + 2 * (x-2) (y-2) + .....+ 1 (x-n-1) (y- n - 1)

i.e., the bouding box of a square is also a square

Round 55: Build the Fence

Note that we can repeat the cut, i.e., 7 can turn into 3, 3, 1 => Therefore, higher k, less likely to achieve => bsearch on K

Round 55: Matrix Palindromes

Suppose K = M, then we can calculate the total cost to make the whole matrix palindrone.

  1. If all 4 letters are the same => cost 0
  2. If distribution is 3-1 => cost 1
  3. If distribution is 2-2 or 2-1-1 => cost 2
  4. Otherwise, cost is 3;

For each column, compare it the the case where, only rows are palindromes and columns are not. Then we pick the best M - K cost saved

Round 53: Histogram Partition

Lets look for a O(n^2) solution first!!! For each integer, we need to add 1 to cost, if there does not exist int = current int before running into anything shorter. note that we are just interested in the number <= current one, so all numbers > current one can be ignored So we can maintain a stack, so that each item is checked only once, and end result is an increasing number on stack

Round 53: Parallel Rectangles

We can brute force in two ways

  1. check out all (LL, UR) pairs, this works well if not many distinct xs
  2. for each pair of (x, y1), (x, y2), store the frequence of (y1, y2). This works well if not too few distinct xs

The key insight is to combine them togehter!!!

So we check each x-axis. If # of ys > S, use first approach, otherwise, use second approach. To choose S, consider that the second appraoch, cost is around N * S/2 * log(N), so S should be < around 50, to limit total steps around 10^6. The first appraoch will run at most N/S times, each takes N, i.e., this means S should be larger than root(N)

Round 48: 8 Divisible

To be able to divisible by 8, we can break the number = a number < 200 but division by 8 + a number divisible by 200 => this just suggests that the last 3 digits divisible by 8 <=> whole number divisible by 8!!!

Then we can generate string, and keep the lexically smallest, excluding ones with leading 0s => 10^3 choices * 10^3 length each

Round 48: Dominant Free Sets

O(n^2) gives obvious DP relationship. Use Fenwick tree to speed up!!!