Round 35: Least Even Digits

A very hard problem for me!!!

if x has no even digit, infinite

Upper bound: find the last even digit, increase by 1, and make a suffix of 1s. This gives B + 1 Proof: by decreameing 111s, it will reduce # of even digits. However, B+ 1 has strictly less even digits than X

Lower bound: No obvious insight possible. Consider a brute force-ish solution to find A-1, the highest number that has < even digits than X

  1. we know A - 1 must share a prefix with X
  2. we know the digit immediately after the prefix must be less (but we don’t which the exact number)
  3. after that, the suffix should be a list of 9s, so as not to introduce even digits

Round 33: Div 3

standard greedy solution. Note that we can prove by induction that cost(x) >= cost(y) if x > y. Watch out for the case where n = 2!!!

Round 32: Subarray Partition

scan through to calc right[i] scan through again, maintain currentSegEnd, update it at each right[i], if currentSegEnd = right[i], we know it is the end of the new segment

Round 32: Square Root Frac (Easy)

No obvious insight. Consider a brute-force solution.

We know the number is < 10^5, we just brute force the sqaure of it, and see if the result is an integer. A double based solution with ep = 1e-9 would work. However, an integer based solution will easily cause overflow, and we need to dynamically calculate the pads when the incoming # has < 9 digits!!!

Round 31: Recursive String

need to precompute count(N), so that we can compute char(N, K)

Round 31: Second Minimum

The key insight is that the second smallest will face the smallest in one of the binary floating process! use 1-2, 3-4,…binary search to find the min index, and for each comparsion, we append the winner the loser

and then we find the min number, in the loser indices, the smallest number. Note we have only (logN) candidates, i.e., we can do a bubble sort-ish comparsion

Round 30: Constant Sum

for each number, we just need to keep track of all added so far - total/(N-1) + total add to i/(N-1)

Round 30: Prefix Free Subset

My idea:

if a is the longest prefix of b, we build an edge a-> b. Therefore, we can build a forest. after that, we bsearch on the length of the max suffix, and iterate on the forest, what the max # of no-parent childs it can have, s.t. the length of work < our target.

Note that longest(K) <= longest(K+1), and answer(K +1) is also good for answer(k), such monotonic relationships suggests sorting, and in-turn, greedily iterative methods!!!

So we start by adding shortest strings one by one to the potential. The moment the new string run into a prefix conflict, we replace its prefix with the new string. Repeat until we reach size K

How to prove this actually works??? - Induction on size k, WLOG, assume all stirngs are of different length. We claim that our algorithm give the best and only solution.Note here we intentionally make our inductive hypothese strong to help the proof

Round 37: Fantastic 4

Claim: we just need to increament two numbers Proof: suppose we have an operation of form abbbbc, then it is equivalent of doing bbb, while the value of d is bigger. Therefore, for any optimal sequence of actions, we can apply such transform, until we have only two types of increments left

So we can brute force on all possible two increments choices. For each one

  1. increment a, until b is 0, if b is 0 before c, and b, we know b can’t be the best choice
  2. increament b, then, increment a twice, repeat, until we have c or d < 2
  3. increment b once, and then increament once

Round 37: Reconstruct Graph

Order by the depth, then we know

  1. the depth should be continuous
  2. no given edge connects depth >= 2
  3. each node has at least one edge connecting to a depth -1 node
  4. Only 1 node with depth 0!!!

so for each node, ways = 2^ (nodes of same level - existing same level edge) * (2^ nodes of last level -1 if no connection, or 2^nodes of last level not conect)

Round 36: Socks Pairs

  1. pick one sock for each color
  2. start from min to max, check colors of odd #s
  3. check the remaing color of even #s

Round 36: Tree Nodes Sets

Keep track of number of insertions and deletions, and traverse down the graph. Note because all ops for the ancestors are perfomed before i, at each step there is no valid delete left

Alteratively, we can keep track of a stack for each x!!! and x is only if the last one is add

Round 57: Foxes on a Wheel

Distince between each node is either 1 or 2. So we just try greedily fit as many 1 pairs as possible. The remaining will be 2 distance.

However, when we assign first choice, we have either go left or right, we need to try both, since we can’t prove which side is better!!!

Round 57: Distinct Palindromes

How to calcualte the # of pandlndromic subsequence with duplicate:

#(l, r) = 0  if l > r
= 1 if l = r
= #(l+1, r) + #(l, r-1) - #(l+1, r-1) if s(l) != s(r), i.e., (L,R) can't be border
= (#(l+1, r) + #(l, r-1) - #(l+1, r-1)) + 1 + #(l+1, r-1)  if s(l) = s(r), i.e., (L,R) can be boarder

In the distinct case, first 3 cases are still valid!!! because s(l) != s(r), we know distinct pa starts at l must be different from distinct pa ends at r

in s(l) = s(r) case, when will adding a new boarding not introduce a new pa? Answer: patterns like, a…a..M..a..a, i.e., Ma is introduced twice at at different (L,R)s. We will have to consider a clear representitive of each class, (L,R) is too coarse grained.

So #(L, R, c) = 2 + sum of (#(L-1, R-1, a-z)) => empty + cc + all inner subsequence padded with a when S(L) = S(R) = c

Note to construct distinct, we can either same last char + different border, or different last char + same border

Round 35: Equal Sums

solution is trivial if a[i,j] we know sum of row(i) and sum of col(j) < maxV, i.e., we delay that only if one of them does not satfisfy. Note there are max 2N -1 constarints, at each iteration, we will satify at least 1 constraint. Therefore, the loop continues for 2 * N -1 times

I had problem proving why this always works!!!

Claim: either all costR(i) = 0 and costC(j) = 0, or exists (i, j) s.t. costR(i) > 0 && costC(j) > 0 If not, then there exists costR(i) > 0 and no costC(j) > 0. However, note that sum of costR(i) = sum of costC(j) in the initial state, and at each step we increase both by the same value. This means both will reach 0 at the same time

Implmenetaion

Calculate sumR(i) and sumC(j), use a two-pointer method to increase both the min of cost

Round 34: Max Or Subarray

two pointer scan to keep track of right most i, where we see 1s. Every time we see a new number, we update the list, and calculate the result number, and index intervals

Round 34: Minimize Max Diff

WLOG, assume it is strictly increasing. then we know, removing element will not decrease the maximal, unless the maximum themsevles are taken out.

For the ease of processing, we can convert the original array to 0, d1, d2, …,dn and find the longest interval between the two max d(i). If intervenl + K < N, we can not reduce the d1

Therefore, we do a span size = n-k scan, using a two pointer approach, and keep track of the maximal diff. Or we can use a dequeue to implement this.