387C: George and Number

1. Suppose the numbers have no 0, then answer is either N or N -1, depending on the first two digits

2. If the nubmers have 0 suffix, then it must be part of the number, if the prefix < the number, so we look for the right most occurance of prefix < the 0-suffix, then we know it must be a single number. To the right of it, all prefix > 0-suffix, so we can just add the numbers one by one!!!

570D: Tree Requests

Do a DFS, keep track of the following things

1. upon visiting each node, add it to the end of the list which is for all nodes at that level - this is where I got stuck!!! The effect is that each list is a left-to-right scan of the tree, i.e., for each node, there exists [l, r] s.t., all nodes in that band are children of that root node.

2. keep track of in/out time of each node, make sure add time by 1 at each in AND out

By 1) and 2), we can see that l >= in time of the root node, and r <= out time of the root node => so just bsearch twice. Use lower_bound!!!

Once we get bound, we can do a prefix sum on each letter, to decide if there is too much odd numbers.

487B: Strip

Just go greedy to expand band from left to right

Official solution

f(i) = min(f(j)) + 1, i - g(i) < j < i - l

260C: Balls and Boxes

The last index must have one of the lowest values.

For each candidate,

1. if i = x, we are good

2. if i > x, then there is no value = min value in the range of [1, i], [x + 1, n]

3. if i < x, then there is min value in the range of [i+1, x]

so we need to keep track of

1. left most min value

2. right most min value

3. rightmost min value to the left of x

Official solution

Consider the reverse of the operation, we remove balls one by one from right to the left, at one point, we will reach a 0, and that will be one feasible choice for the init index.

To speed up implementation, we can just reduce all values by minV - 1, and then finish the last incomplete loop

432C: Prime Swaps

Calculate all primes <= 10^5, and inverted index for each number. For each number, use bubble sort idea, except that pick the larget prime < distance, and repeats. The prime number is about 10% of all numbers, i.e., we can reduce the distance to 1/10 in each swap => good for 5N requirments

691D: Swaps in Permutation

get all chars and indices in a components, sort the chars and components

825D: Suitable Replacement

Do a bsearch on the final number, find the larget one s.t. number of ?s > missing chars we need to fill

305C: Ivan and Powers of Two

First, preprocess the inputs to remove all duplicates of powers, i.e., for each power, get the count, and then add each binary index to the count of binary + current power

Then we scan from v = 1 to maxV => answer is just ?!!!

524C: The Art of Dealing with ATM

For each request, for each bill, try k1 from 1 to 20, the k2 from 0 to 20 - K1, see if K2 is a possible solution

Official solution

Create < 5000 * 20 possible values, with least # of bills to get the value. For each of the 20 query, we iterate over the first part, and look up on the second part

873C: Strange Game On Matrix

for each column, the band size is fixed, so we can just two pointer to find the highest starting band with max value. The cost is the band sum in [0, optimalStart]

360A: Levko and Array Recovery

make an upper bound for each entry. For op type 1, update the delta array, for op type 2, update the upper bound for the band.

In the end, run the array through the sequence of action again to verify all op2s are still good.

615C: Running Track

Just brute force, try both forward and backwards for the longest substring that matches the current head. Note that by the greedy approach, it doesn’t matter if we matched more in the first then the second => O(n^2)

Official solution use a DP LCP(i, j), to calculate the longest common prefix of the suffixes, i to m, j to n, and longest comon prefx i to m, j to 1

Round 61: Paint the Fence

Even-based approach, looking for the fence with layer 0.

Partial-sum approach

we mark delta[L] = 1, delta[R +1] = -1, then the number of layers at i = sum of delta[0] + delta[1]….+delta[i]

Can do a second ps on if layer[i] = 1 or 0, so we can calculate # of solutions between [L, R] efficiently

Round 61: Strictly Increasing Array

If we are looking for a non-decreasing array, we just need to find LCS. However, we can not use it directly, as we know A(j) - A(i) >= j - i, in the LCS we found!!!

So we just do a reduction, i.e., A(j) -j >= A(i) - i, this reduces to our LCS problem.

Round 62: Simple Paths

Find the first path from A to B, mark all discovered edges as bad. Then run again, while ignoring the blacklist.

Official solution

For each edge, calculate if it is a bridge or not => i.e., if without this edge, the graph is still connected

Then for each query, try to find a path without containing any bridge!!!

Round 62: Partial Maximums

Do a rolling start, keep track of top 2 numbers. For each number, track if it is already max, only 1 greater, or 2 greater than that. If only 1 greater than the current number, that greater number count++.

In the end, we just looking the number with max count, plus all number that is already max.

Official solution

Claim: We can introduce new partial maximums only if we removed an existing one!!!

Proof: Suppose suppose a new partial maximum got introduced as a result. then the one removed must be > all before i, i.e, the removed on itself j (j < i), must be a partial maximum

so for each 3 consecutive local maximua, we can just remove the middle one and do a brute force search

Note that for the last partial maixumum, removing it will introduce at most 1 new one, so we can ignore that case

arc081_c: Don’t Be a Subsequence

Start from empty string, try finding the first index where all a-z are included. If unable to find it before the end of the string, we have an answer. Otherwise, reset indices, and repeat the process

Official solution

1. Use dp to caluate the length of target subsequence len[i] = min(len(next(i, c))) + 1

2. start from 0, find the smallest char c, s.t., len[i] = len(next(i,c)) + 1, and then update i

arc083_c: Bichrome Tree

Official solution

Consider minV(v) = min total of the values of different color, then for each child node, we can mark either the child node same as the root color or not!!! i.e., we add sum to either v(c) or minV(c) to the current node value. We want to find min other value while to current node value <= v(parent), we can use a minOther(child, current value total) dp at each node. Again, because the value is positive, we can just ignore out of boudn case

arc085_b: ABS

Claim: A can not get better result than taking all but last or last in the first step!!! Proof: If A takes less than second last in the first move, and can achieve better result, then B can take the last or second last instead, which blocks A’s moves

arc086_b: Non-decreasing

If |minV| > |maxV|, add minV to all, and do a rolling add from n to 1. Otherwise, add maxV to all, and do a rolling add from 1 to n.

arc087_b: FT Robot

Standard coding problem. Note that for the each of coding, we can handle x and y separately!!!

arc088_b: Wide Flip

bsearch on K, at each K guess, do a greey conversion, start at the leftmost 1, and issue a flip, to improve the speed, use an even-based approach.

Official solution

For each different a[i] and a[i+1], we know we have to flip it, and the min length <= min(i + 1, L - i + 1).

It becomes obvious that we can find a solution given these upperbounds, i.e., the tighest upper bound is the solution, because it is no problem for us to filp longer segments. We can fix them one by one from left to right

arc070_b: No Need

Note that the orignal problem means that, a number is necessary if and only if there exists a subset without a(i), s.t. subset sum in [K - a(i), K) !!!

Also, since all a(i)s are positive, we can ignore ALL a(i) > K, as it will never appear in the subset we need anyway !!!

Idea 1

Claim: a(i) < a(j), and a(j) is not necessary, a(i), will not be necessary

Proof:

1. consider all subsets without a(i) and a(j), either it is >= K or < K - a(j), consider the second case, adding a(i) will not bring its value to >= K

2. Suppose we have a subset with a(j), s.t., subsetSum + a(j) is in [K-a(i), K), then we swap a(j) and a(i), we have subsetSum + a(k) >= K - a(j) and < K - a[j] + a(i) => contradiction!

Therefore, we need to find the smallest i, s.t., a(i) is necessary. log(n) checks, with O(K) at each check

Idea 2

No binary search, just DP on prefix and suffix sum, at each step, we do a two pointer approach, one at 0 from LHS, and K at rhs

rv = K
LPE(lv, 0, K) {

	while(rv + lv >= K && rv > 0)
		rv--;

	while(!suf[i+1][rv] && rv > 0){
		rv--;
	}

	if(rv + lv < K && rv + lv >= k - a[i])
		return true;
}

arc081_b: Coloring Dominoes

Just do a linear scan from left to right. The number of ways is deterministic at each step, 3 cases, ||, |=, ==, and =| !!!

agc019_b: Reverse and Compare

Consider the contribution from individual approach!!!

If a[i] = a[j], doing a swap will not contribute to the final count, because it will be same as swapping i + 1, j - 1.

Conversely, if a[i] != a[j], it will definitely contribute to the final count.

Proof: if swapping i and j does not contribute to the unique count, then there must exist i1, j1, s.t., i1 =< i, and j1 >= j, s.t., swaping gives the same answer. But this implies i, j is on the same side of a palindrome, i.e., a[i1] = a[j1], this contradicts with fact that a[i1] = a[j1] does not contribute to the final count

Therefore, we can count char count for each letter, and the answer is N^2 - sum of ( count ) * (count -1)/2

arc082_b: Derangement

Consider the first i = p[i], if p[i - 1] < i - 1, swap i and i - 1, otherwise, swap i and i + 1.

Offcial solution just swaps i with i+1 all the time if i = p[i], and n with 1 if p[n] = n !!!

arc083_b: Restoring Road Network

Order shortest paths by length, and we try adding them as edge one by one. Every time we see a new shortest path, we try finding the current shortest path between the two end points, if it is longer than the current path, we know that this must be a new edge. add it to the network

Official solution

Consider if there exists a third vertice w (w != u or v) s.t., a(u, v) >= a(u, w) + a(w, u), we know (u, v) is not necessary - idea similar to F-W. So we just sum over all necessary a(u,v)

agc010_c: Cleaning

Official solution

Assign an alternate function to edge instead of nodes, for each appeareance in our paths, we can add 1 to the edge. So we know that for leaves, ev = weight, internal nodes, sum of evs = 2 * weights. So we can uniquely determine the path bottom up.

The check i missed is that for an internal node, we have to make sure no edge is more than HALF of the total evs, otherwise, tehre will not be enough endpoints to assign to the incoming edges!!!

arc084_b: Small Multiple

try all 1s from 1 to K 1s, by pigeon hole principle

1. At least 1 will have mod K = 0

2. very likely to have two numbers with same mod.

Whichever one comes first will give the answer

Official solution

Construct a graph by assigning 1 to an inc operation, and 0 to * 10 operation, do a 01-bfs, until we have more than K #s,

arc076_b: Built?

Sort by deltas in x or y coordinate, and then add edge iff it will the new edge will expand existing components => similar to MST

arc076_c: Connected?

Hard problem to me

Official solution

1. Given two numbers, it is impossible to construct if all 4 occurance appear in the order of 1,2 ,1, 2 clockwise, i.e., we form a line that cuts the plane into halves. Note if only one number is on the boundary, we can force all lines to go along the sides

2. So we connect all non-boundary numbers first, and then all boundary numbers

3. We can use a stack and go clockwise to make sure no intersecting boundary numbers

arc077_b: 11

Classfication: with both same numbers with 0 same numbers with 1 number, and nothing in between with something in between, and one number either to the left or right

Note the official solution calculates the complements

agc017_b: Moderate Differences

Rearrange all the operations to do increase first, and then decrease second, do a brute force search on all possible turning points

arc078_b: Fennec VS. Snuke

Find the path between two starting cells, and find the edge where the two colors. Calculate subtree size rooted at either end of the cell - the one > N/2 wins

agc018_b: Sports Festival

Assume all sports are selected, and we calculate how many people are on each sports. Then we start taking out sports one by one, and update all affected users in the process in O(n)

arc079_b:Decrease (Contestant ver.)

Official solution

Consider the inverse of the problem on an array [0,1,……n-1] !!! Apply them one by one. Speed up by only simulating the last K%N ops, because applying inverse to all = increase all by N

arc079_c: Decrease (Judge ver.)

Official solution

1. One key insight is that the difference between entries will never be more than N, i.e., one operation will move a number from max to min !!!

2. bsearch to find Y, s.t., we have a solution for the high watermark value Y, given that we will run operation X times

3. Apparantly some people just do bruteforce simulate, by try decreasing all values to below N???

arc080_a: 4-adjacent

1. each odd number must be followed by a product of 4

2. each product of 2, must be followed by a product of 2 or 4

So we use all 4s to try to satifiy the first condition, and then see if product of only 2 is odd, if so, it is impossible only if we have no 4 remaining

arc080_b: Grid Coloring

Use the zig zag line construction for each square. Use a event-based two-pointer model when coding

arc071_c: TrBBnsformBBtion

Upon inspection, we can see that AA <-> B, and BB <-> A, so we can just covert all B to A, and see the diff in length % 3 = 0

agc013_b: Hamiltonish Path

Use the “growth” approach!!!

We just start with an edge and changing the endpoint if one endpoint has a neighbor that is not in the path yet. Keep doing this, and we will exhaust all unchecked vetirces in N - 1 steps, or we reach an dead end.

arc074_b: 3N Numbers

maintain a minheap and a max heap, and move separator i from N to 2N - 1

agc015_b: Evilator

same direction one, opposite twice

agc015_c: Nuske vs Phantom Thnook

For a forest, we know # of components = total # of nodes - total # of edges. Cutting the region will preserve the forest properties. Therefore, we just need to calculate how many nodes, and edges in that subregion, e.g., by 2-D prefix sum!!!

arc075_b: Widespread

bsearch on the number of expositions, calculate # of As we need for each monster and see if the total sum is good

agc016_b: Colorful Hats

Official solution goes by classfication!!!

1. max = min, then all unique or all the same

2. max = min + 1, we know that A = max(a(i)). So number of unique cats = cats with A - 1. A >= unique + 1 and A <= unique + freecat/2

agc016_c: +/- Rectangle

As long as H * W % h * w != 0. It is always possible. Set corner to 10^9, every other to the min v, s.t. v * (h * w - 1) > 10^9

Official construction

1. if the row number % h = 0, then write positve number. Otherwise, write negative number.

2. The ratio will be fixed at h/1, so one construction is to have 1000(h-1) - 1 as postive, and -1000 as negative!!!

arc065_b: Connectivity

Do a flood fill on road to decide which city goes to which component, and then flood fill again on rail roads, but add the edge only if the two nodes are in the same components

Official solution handles a and b separately, and test of (a,b) are the same!!!

agc008_b: Contiguous Repainting

The final form must have a continons block of black or white of length >= K.

So we just try all i, and candidates are positives in [0, i), [i+k, n], max(sum[i, i+k), 0))

agc008_c: Tetromino Tiling

Note that only I, O, J, L matters. if I is odd, and give that extra to a J, L combo. Note official solution needs to try the number of I + J + L patterns!!!

agc010_b: Boxes

We can caluate exactly how many ops we performed O. if a2 - a1 = O, we know that no ops NOT in a1. Conversely, suppose we have O1 opes on a1, then the a2 - a1 = -O1 * (n-1) + O - O1,i.e., we can infer how many ops are on a1 .

Note:

1. the formula suggests that k - d(i) = n * x => we need to check the dividability here.

2. that sum of d(i)s is 0 => sum of (k - d(i))/n = k

agc011_b: Colorful Creatures

sort the value, for each i, check if there is an iterm s.t., a(j) > 2 * ps(i)

agc005_b: Minimum Sum

maintain next[i], prev[i], the index of next and previous unseen index, at i

We iterate value from n to 1, use the reverse index to update next and prev

Official solution uses a set to to get the adjacent numbers to the set.

agc005_c: Tree Restoring

Given the input, we know the diameter of the tree.

Assume D is even, we also know the min value must exactly D/2, and there is only one such point. so we just build the two legs of length D/2, each, and then, given each remaining d(i), directly attaches to a node with max distance d(i) - 1

Official answer uses a mutli-set

agc006_b: Median Pyramid Easy

Possible as long as the value is not 1 or N - 1!!!

Note that if we have two adjecent cells, the value will preserve all along the way, until the top. So we can use this to construct the bottom easily

agc007_b: Construct Sequences

A crazy construction!!! a(i) = 30000 * i b(i) = 30000 * (n - i) + inverse(i)

agc001_b: Mysterious Light

Base case x = y, ans = 3 * y

if x > y, ans = x + y + x + ans (y- x, x). similarly x LT y.

Note to improve the performance, we need to do something like the euclidian algorithm, when a LT b

f(a, b) = 2 * constant * floor(b/a) + f(a, b % a)

i.e., skipping the many expanding steps!!!

An even simpler solution is 3 (N - gcd(N, X))

agc001_c : Shorten Diameter

The key insight is the the properties of diameter!!!

1. If d is even, then there exist a point s.t. all distances from v LTE d/2

2. if d is odd, then there exists an edge, s.t., all distances from either end of edge LTE (d-1)/2

We just try all V/E’s and find the maximal graph that satifies this condition

arc058_b: Iroha and a Grid

Note that H, W LTE 100K.

ways(1,1) -> (H, W) = ways(1,1) -> (i, B + 1) * ways(i, B + 1) -> (H, W), for all i in [1…A)

First part is choose(i + B, i), second part is choose(H-i + W-B, H-i). Note that official solution uses (H-A + 1, j) instead

agc002_b: Box and Ball

We need to maintain

1. cnt for each box

2. at current step, possible for for it to have red ball

3. red ball poitions we have visited

for each move, we mark the next one as possible if cnt[i] > 0 && possible[i]. When cnt[i] = 0, possible[i] becomes false

agc002_c: Knot Puzzle

Consider the last knot we untie, as long as l(i) + l(i+1) > L, we can find a solution. My original guess was too restricted!!! The construction is trivial given this insight.

agc003_b: Simplified mahjong

Claim: for each continous block of cards, we can make floor(S/2) cards!!! Proof: we list all S cards, and sort them, and we can see that the pair will keep going!!!

So we just scan through each continouous, non-0, subarray, and calculate sum from each side.

agc003_c: BBuBBBlesort!

Claim: answer is # of poistions at odd positions that should go even!!! Proof: we can use type 2 rearrangement to move odd should go even and even should go odd to each other, e.g., move both to the head of two spots, and then perform type 1. In the end perform type2 again

arc060_b: Digit Sum

Such number theory problem does not give too much insights, so let’s consider if we can brute force/simulation!!!

if b LTE sqrt(s), we can just do brute force conversion.

if b > sqrt(s), we know it can have only two digits, i.e.,

1. d1 * b^2 + d2 * b = n

2. d1 + d2 = s

We know that n % b = 0, i.e, we just try all b LT sqrt(n)

arc060_c: Tak and Hotels

Use two pointer/bsearch to calc, next(i) = rightmost hotel the pointer can reach, and then we can calc next(i)(2^p), the rightmost hotel to reach in 2^i days,

for each query, we can just try decreasing p from 32, the moment we have next(ai) (2^p) LTE bi, we add 2^p to the final answer, and update ai to next(ai)(2^p)

agc004_b: Colorful Slimes

Suppose we did K shifts in total, then we know that the cost to acquire a(i) >= min {a(i-1)…..a(i-k)}, overall cost >= sum over cost(i) + K * x

Claim: this lowerbound is reachable all the time!!!

Proof: if a(i) is the min value for only entry, we acquire it upfront. Otherwise, suppose it is also the init entry for a(j), and a(k), j LT k, then we can acquire, and then shift, and acquire again

Then we just need to iterate on K, can improve by DP on cost(i), as it is non-decreasing and K improves

arc061_c: Snuke’s Subway Trip

The hard part is how to construct the graph!!!

We construct the node (station, last visit comompnay), because the new node can only be generated by an edge, so the new node # LTE number of edges.

For each edge (u,v) operated by company c, we connect (u, c) to (v, c), with cost 0, we also connect each node to (v, -1) with cost 1, representing leaving and entering the gate, with cost 1.

Final answer is shortest distance from (1, -1), to (N, -1) divided by 2.

Round 60: Digit Permutation

Note that for topologic sort, after each dfs call, even if you start with a node without incoming edge, the component may not be traversed fully yet!!! A counter example is a -> b <- c. C is not touched after we did a -> b

This is not a problem will not occur if 1. the graph is a tree (only 1 node with incoming endge 0)

2. undirected, flood fill problems

3. a depends on b, i.e., b should be printed first

However, in this problme I chose a < b => a -> b, i.e., a should be printed first. This means I should reverse the orddr until the whole traverse is over!!!

To assign 0, we can just start with 1, and skip it when we reach the 0 node in the final list. Because the 0 node has no incoming edge, it will not cause conflict.

Round 60: Card Groups

This is an example of meet in the middle, a search technique I see for the first time!!!

2^40 is not too huge, but still huge enough to not apply direct brute force search. Meet in the middle will reduce complexity to around 2^20 => slightly over 1M!

Meet in the middle

Consider the each half, the combination of answer should give B0 + B1 = R0 + R1 => B0 - R0 = R1 - B1

So we iterate over all 2^20 sets of potential B0, and calculate B0 - R0, put them in a set, keeping track of min diff.

And we iterate over all 2^20 sets of potential B1, while we iterate, we look up to see if there is any potential matching ones, and then update the final answer.

Round 10: Shifted Diagonal Sum

Just calc all potential diagonals. Suppose we shift to the right by X, and down by Y

Extended question: after the X, Y shift, which two orginal diagonals become the new main diagonal? Note that the formula is different when X > Y and X < Y

Round 10: Subarray Medians

Done in O(N^2)!!!

To calculate all medians for subarrays starting at i, and online algorithm takes O(nlogn), with two heaps. So we will try an offline approach, i.e., calculate the complete picture, and then deduce parts from it.

The explanation is very confusing…

Round 9: Flip Game

Obviously, we need to change all in column 1 to 1. Two options, rows flips to 0, and then col flip, and then col flip

After that, we just do col flip as long as we get more 1s => i.e., in the original column, # of 0s < # of 1s

Note that

1. The order of ops doesn’t matter!

2. Each row/col will receive AT MOST one ops

3. Suppose we flip a set of R rows and C cols, the final result is EXACTLY same as flip the complement of these 2 sets, because flipping 0 times = flipping 2 times.

4. This means that, for every possible choice we have at flipping the first columns, we have a corresponding and equivalent chose at at NOT flipping the first coliumns, i.e., the optimal solution at not flipping the first column cases covers all other cases!!!

Round 9: Array Removal

Reverse the order of ops, and use a union find to keep track of the start of subarrays. and update the max sum as we move

Note that we can also update it with linked list approach -> but more cumbersome

Problems to watch out for

1. Run it on ECS or not?

2. During the restart, what if the consul process is not longer co-located with data volume, or even worse, loaded a stale data volume

3. What network mode to use? What IP to broadcast?

4. Raft protocol size is fixed to 3 or 5 in practice, this means our cluster running Consul should be 3 or 5.

Original Post

CloudFormation Template

Consul server starts

docker run -d --restart=always -p 8300:8300 -p 8301:8301 -p 8301:8301/udp"
                                            "-p 8302:8302 -p 8302:8302/udp -p 8400:8400 -p 8500:8500 -p 53:53/udp",
                                            "-v /opt/consul:/data"
                                            "-h $(curl -s http://169.254.169.254/latest/meta-data/instance-id)",
                                            "--name consul-server progrium/consul -server -bootstrap",
                                            "-dc" INJECT_HERE
                                            "-advertise $(curl -s http://169.254.169.254/latest/meta-data/local-ipv4)",
                                            "-ui-dir /ui"

Consul agent starts

"docker run -d --restart=always -p 8301:8301 -p 8301:8301/udp",
                                            "-p 8400:8400 -p 8500:8500 -p 53:53/udp",
                                            "-v /opt/consul:/data -v /var/run/docker.sock:/var/run/docker.sock",
                                            "-v /etc/consul:/etc/consul",
                                            "-h $(curl -s http://169.254.169.254/latest/meta-data/instance-id)",
                                            "--name consul-agent progrium/consul -join" INJECT_HERE
                                            "-advertise $(curl -s http://169.254.169.254/latest/meta-data/local-ipv4) -dc" INJECT_HERE
                                            "-config-file /etc/consul/consul.json"

Note

1. -v, –volume=[host-src:]container-dest[:]: Bind mount a volume.

2. -h, set the host name

3. -advertise,

4. /etc/consul/consul.json. leave_on_terminate: true

5. Although /etc/ecs/ecs.config is defined, Consul does not run as a ECS task or service.

6. 169.254.169.254 is a reserved endpoint to query current instance’s metadata

7. It also has a glidelab/registrator component

8. –net

9. progrium/consul is not the official consul docker image, which is hashicorp/docker-consul

1. vault goes to /usr/bin

2. vault config in /etc/vault.d/vault.hcl. Note by default tls_disable is false,i.e., https is turned on by default

backend "consul" {
  address = "127.0.0.1:8500"
  path    = "vault/"
}

listener "tcp" {
  address     = "0.0.0.0:8200"
  tls_disable = 1
}

Note that the consul address is local, because it is talking to the local consul agent, as per recommendation of Hashicorp

1. Systemd config in /etc/systemd/system/vault.service

[Unit]
Description=Vault
Requires=network-online.target
After=network-online.target

[Service]
Restart=on-failure
ExecStart=/usr/bin/vault server -config /etc/vault.d/vault.hcl
ExecReload=/bin/kill -HUP $MAINPID
KillSignal=SIGTERM

[Install]
WantedBy=multi-user.target

1. Note that this template has no autoscaling group/launch configuration setup.

2. It also has config and setup for consul client. The configuration layout is exactly same as the consul quickstart

3. Although vault requires unseal on each restart, there is no script in the template to handle that. That means unsealing, and making sure # of alive instances > 1 is completely manual

Round 15: K Consequal

Maintain a stack with letter and current count, update the stack on each new letter

Round 15: Base K Xor

Idea 1 ——- We consider each digit independently, i.e. sum becomes an operation under mod k, i.e.,we can apply the partial sum trick. Note that we can delay the mod operation as much as we can, until the final step, since it doesn’t affect value, not presentation of digits.

at i > 1 th digit from right to left, the answer is sum(num/base) * base - base + digits to the right. All these happens in base 10, but mod k. However, note that for ith digit, it changes every k^i times, i.e., every complete change is a multiple of k already => so we just need to worry about the last digit!!!

So the answer is d * (x % k^i + 1), +1 is for the x0000..0 case

Idea 2

As the title suggests, it is essentially XOR in a different base. When k = 2, (4 * x) ^ (4 * x + 1) ^ (4 * x + 2) ^ (4 * x + 3) = 0

So we can expand on this idea, and just calculate the XOR from a to nearest k^2 * k , and from nearest k^2 * k to b

Round 14: Surrounded Rectangle

Official solution ——– Idea is similar but simpler. For each point, we look for the first 0 to the right of it, and to the down of it. So that we know the rectangle must be bound for that. Given this candidate, we can do a validation check via 2D prefix sums. Note we need to calcualte on prefix sum of 1, as 0-case can be inferred already.

Alternative solution

Flood-fill on 1s, and keep track of the max, min x and ys. In the end, check if the size of the component matches equal to the product.

Round 14: Subarrays Xor Sum

1. For each bit, we calculate the prefix sum - odd or not on the count of it.

2. The partial sum of xor is similar to regular addtional, except the difference in the interval is XOR too !!!

3. For each [j - B, j - A +1] interval, we need to keep track of how many XOR sums are 0 or 1, to handle to case of xorSum(j) is 0 or 1

Round 13: Balanced Min Pairing

Do a greedy pairing - sort A, B, and match a[1…N/2] with b[N/2 + 1… N] , and run validations

Round 13: Num Cube Sets

We know a,b must be of form n1 * n2^2 * n^3, therefore, we group each number by n1 * n2^2, n1^n2 can not be n^3. and in the end we brute force on all possible group counts. Note that elements from within the smae subset should have the same normalization

Round 12: Independent Rectangles

Build a graph and then calc components

Official solution

Sort by (w, h), we also keep track of min height we have seen so far. It is independent, if it is the min height we can seen so far. Alterantively, sort by (-w, h), and keep track of the max height we have seen so far

Round 12: Bitwise And Queries

So for y, if x has a bit 0, can be 1, if x has a bit 1, the corresponding bit has to be 1. We assume x < b.

At each bit of y, we try to keep a prefix of b

1. x = 1, b = 1, do nothing

2. x = 1, b = 0, invalid

3. x = 0, b = 0, do nothing

4. x = 0, b = 1, add 2^remaiing free bits to answer

The final answer is answer + 1 to include x itself.

The range in [a, b] is calucated by the delta approach

Round 11: Connect the Graph

during DFS, we can find the edge that would introduce cycles, and then we save them to add all other components to the first node

Round 11: A Single One

Naive approach is to use a BFS. # of nodes are good, but there are too many edges.

To optimize it, we can not include potential edges explicitly. Instead, we find that the nodes it tries to expand to form a CONTINOUS band with the same oddity!!!

Therefore, we keep track of two node lists, one for odd, one for even, when we BFS to expand on the next node, we use set::lower_bound to infer the neighbors instead of using explicity edges

1. The AMI is an ubuntu image

2. creates a systemd named consul. bin at /usr/bin, config at /etc/consul/config, data at /etc/consul/data

3. Sample config. This goes to /etc/consul/server.json

{
  "server": true,
  "ui": true,
  "data_dir": "/opt/consul/data",
  "client_addr": "0.0.0.0",
  "bootstrap_expect": __BOOTSTRAP_EXPECT__,

  "retry_join_ec2": {
    "tag_key": "__CONSUL_TAG_KEY__",
    "tag_value": "__CONSUL_TAG_VALUE__"
  }

1. Sample service

[Unit]
Description=Consul
Requires=network-online.target
After=network-online.target

[Service]
Restart=on-failure
ExecStart=/usr/bin/consul agent -config-dir /etc/consul
ExecReload=/bin/kill -HUP $MAINPID
KillSignal=SIGTERM

[Install]
WantedBy=multi-user.target

1. The launch configuration uses EC2 health check instead of health endpoint,i.e., potentially there might be case where instance is up, but process is down

2. For consul client machines, client shares the same consul.service file, but gives a different configuration. This goes to /etc/consul/client.json in the config dir.

{
  "server": false,
  "ui": true,
  "data_dir": "/opt/consul/data",
  "client_addr": "0.0.0.0",

  "retry_join_ec2": {
    "tag_key": "__CONSUL_TAG_KEY__",
    "tag_value": "__CONSUL_TAG_VALUE__"
  }
}

1. IAM role for consul client and server

   1. s3:GetObject - to get scripts and binaries

   2. ec2:DescribeInstances - need to get tag information

Round 59: Triangular Matrix

We can do a greedy approach. since for each row, we are interested only in the min char, so we record what candidate indices we have, and only take the indices withe min char as the new candidates, and add the min char to the solution

Round 59: Editor

each line must start with a word, therefore, after max 10^5 lines, we will run into a cycle, and we need to quickly answer this question: if this line start at index i, what the index at which the next line starts, and how many first entries we will see on this line?

This can be calculated by a bsearch. Of course, we need handle the case where total length < W.

Note that official solution uses a two-pointer method by calculating the mod of total length!!! This works because

1. we reduced to the case where total length >= W, there form the next pointer will never catch up from behind. This is the important gurantee of two-pointer’s performance.

2. we know EXACTLY many complete cycle exists, so we just reduce the W and delta between start and end pointer, but the length of this many complete cycles

so we need to know, cycle length, plus how many first entries appeared in this cycle, by keeping track of how many first we have seen before we start this line

curstart = 1
ln = 1
while curstart not seen && ln <= H
	seen[curStart] = ln
	next[curStart] = calculateNext(curStart)
	if(nextStart <= curStart){
		numFirst++;
	} 

	numFirst += (W - firstSeg)/TotalLen;
	total[curStart] = numFirst;
	curStart = next[curStart]
	ln++;

if(ln > H){
	return numFirst

}else{
	cycleLen = ln - seen[curStart] 
	numCycle = (H - see[curStart] - 1)/curlcyLen;
	cycleFirst = numFirst - total[curStart - 1]	
	numFirst +=  numCycle * cycleFirst;
	H -= (numCycle - 1) * cycleLen; 
	//repeat the while loop above without bsearch to finish the remaining H
	//alternatively, we can use some formulas
}

Round 18: Squarish Rectangle

brute force search on W, since W <= sqrt(S)

Round 18: Concatenated String

For each char, we maintain a set of its indices, and then we scan b one by one while maintaining the index at i. If we can not find solution via set.lower_bound(), we reset the current A index to 0

However, this implicitly dependes on the size of S, may still be too slow!!! To key insight is that since we keep moving pointer to the right, we can speed up by keeping track of current index, and ignore all index < current index

We will just pre-compute next(i, c) = at index i, what the next index of char c. To calcualte it, we need to keep track of last seen char index, and upgrade everything between the last seen one, but before the current one

Round 17: To Front - To Back

Find the longest consecutive subsequence, anything not on it must be moved. To calculate it, we can just keep track of the seen index of the number, and the length of consecutive subsequence of it.

Round 17: Largest And Subset

Keep a set of candidates, starting from the highest bit. Scan through the candidate to find one with that bit as 1. if there is less than k candidates, we do nothing. Otherwise, we narrow down the scope

Round 16: Marble Weights

Just weight the 2,3,4,…n subrarray. In the end weigh 1 with n

Official solution

3 weights to find w1, w2, and w3, and then we can weigh w1 with w4…w5…w6

Round 16: Fake Coins

1. The key is to find an arrangement s.t. 10 and 30 are in two different partitions

2. What is the probability that 10 and 30 will be in the same parititon => 50% !!!

3. So we just randomly assign coins to two parts, on avg, we expect 2 tried to find them in different paritions

4. After that, it will be standard ternary search

895B - XK Segments

1. suppose we have a range (L, R), then the exact number is R/x - (L-1)/x. I had problem coming up with formula during the contest!!! Should be easy to come up with if we view it from the delta band persepctive

2. Therefore, given x, k, we know the range of R, and we can bsearch on the left and right part of the array, and we take distance as number of js in the form of (j, i)

My (wrong) approach during the contest

1. calcualte # of coordinates s.t. no more than k number divisible by x in the segment

2. calculate the segment length, but with k - 1

3. calcualte the difference

The idea did not work => we didn’t consider the case (i, j) where i > j, and a(i) = a(j). This may happen if we have a band of equvalents, and k happens to be 0 or 1!!!

Implmentaton-wise, normally two-pointer needs two checks, 1 for index, one for predicate. because it is a while on and solution, we need to explicitly check for out of bound/invalid case.

895C - Square Subsets

I got the bitmask idea - need a bit mast to mark the state of products => which primes have odd numbers. However, the answer will be 2^19^n which is still too high.

Instead of iterating on index i, we can just iterating on the value of numbers, since it is < 70!!! We will check how many ways to get a product with odd number of primes in the subsequence of 1…70

i.e., ways(n + 1, oldbm) += ways(n, oldbm) * sum of(choose(num(n), even times)) ways(n + 1, oldbm XOR bitmask of n) += ways(n, oldbm) * choose(num(n), odd times)

893D - Credit Card

How do we calculate the exact amount we need to fill at each step?

If we have to fill a card, we need to fill it s.t. at least one suffix sum of which has to become d. Because otherwise, we will overflow at some point, so we just try the best possbile.

To calcualte to potential maximal to the right, we need to

1. precompute the sum of all deltas,

2. scan from right to left, to keep track of max delta so far

3. also keep track of fills we have done so far, at each point we need to fill, the max we can fill is d - maxDelta - deltaSofar. If deltaSofar + ps[i] < 0, we know it is invalid

Round 19: Cities Robbery

four cases:

1. go straight to left

2. go straight to right

3. left and then right

4. right and then left.

We can use either set.upper_bound() or a two-pointer approach

Round 19: Smallest Array Permutation

1. If one # appears > ceil(N/2) times => we have no solution

2. If one # appears = ceil(N/2) times => we have to use this number ONLY IF IT IS ODD!!!

3. Otherwise, we use the minimum number. Can use a heap to keep track of current maximum. Note that the official solution does not use a heap!!!

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

Round 58: Palindromic Friendship

we consider both the odd and even case if (i, i+1) is in the list, then we expand deltas to try the max. if (i, i+2) is in the list, then we expand deltas to try the max. each existing relationship will be checked only once. and non-exisitng one is terminal, so the run time will be linear

Round 58: Tournament Swaps

1. easy to generate the FBT, with the winner at each node
2. then we scan trough bottom up (or while we are generating), update max[a[i] +1] = current level, i.e., swap i with i+1, and we want to find the highest level

Official soultion

So we need to know the second strongest player. We will just preprocess it to calculate for a give size M, who is the second strong player in for all substrees of size 2^M

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.

Round 39: Reconstruct Sum

Consider each column independently. we just analyze the 4 cases, i.e., a combination of

1. when there is a carry from last col
2. there is a carry to the next col

Implementation-wise, we reverse the digits, and scan from 1 to n. Note we can just brute force to to calucate ways, with 10 added to carried digits

Round 39: Seven-segment Display

To be smallest, the # of digits must be smallest Therefore, we can calcuate greeidly, given K, what is the min # of digits we can have.

0, 1, 2,3,4,5,6,7,8,9 needs 6,2, 5,5,4, 5, 6, 4, 7, 6 segments respectively

But note that even though we know max # of digits, we need to find a way to max # of 0s, and then 1s,and then 2s. I got stuck findng an efficient way of solving it!!!

Note that 9 can never appear in the solution => we can use 6 instead. Therefore, 8s must form a suffix

Now we consider bruteforce search all potential non-8 prefixes, because of minimum length requires, the total # of segments in the non-8 part can be more than 7, otherwise, we will just add a new 8, i.e., at most 3 segments

so we brute force search 1 to 999, and caluate # of 8s need to fill all k segments, and keep track of the best number. Note that 9 can not appear in the solution

Round 38: Bounded Difference

1. find the total # of violations, if # > 4, impossible to fix
2. swap a[i - 1] with a[0], a[1]…., and calculate # of violations afterwards
3. swap a[i] with with a[0],a[1]…., and calcualte # of viodlations afterwards

We break only if total # of violations is reduced to 0 in any cases.Note that we must swap one of a[i] or a[i-1], so we don’t need to check other cases.

Round 38: Tree Antichain (Easy)

A tree can always turned into a bipartite graph by coloring nodes alternatively in a DFS fashion. So we have two half permutations we can build on already!!!

Obviously, if tree is a star, we can not find solution. If it is not a start, we can find a path with length >= 3. Then the first and last vertices of opposite colors will not share a vertex for sure

Implementaion

1. we can use a nested loop to detect the connection points => LTE 25 mil
2. we can use swap(item, vector.back()) in c++ to change the connection point

Round 43: Bad Triplet

if all deg LTE2, then we must find a cycle with length % 3 = 0

if exists V deg >= 3, then either we find a cycle with length 3, or the V and neighbor itself is good enough!!!i.e., all passes through the central V.

Round 41: Tennis Tournament

if player wins M matches, then the first 2^M -1, must be worse then him, and 2^M + 1.. 2^(M+1), must have at least one that is better than him

Round 41: BFS-DFS

We need to satisfy both BFS and DFS. So to satify DFS, a trivial answer will be D1 -> D2-> D3 -> D4… To satify BFS, a trivail answer will be B1 -> B2, B1 -> B3…. Turns out these 2 can be satified AT THE SAME TIME!!! if we just add edges together!

The invalid case will be the that B1 -> B2 is different from D1 -> D2

Round 40: Switch the Lights

We need to toggle the first one, and keep a switched bool for each i

for each i, if i dark, continue. Otherwise, switch the current swtich flag, and add one at bool[R(i)], and then add apply the exsting switch flag. Alternatively, we can use a counter

Round 40: Restricted Permutations

ways(1, 1) = 1 calculate totalWays(N-1, i) ways(N, i) = totalWays(N-1, i - 1) if a[N - 1] = 1 Otherwise, ways(N, i) = ways(N-1, i) + ways(N-1, i + 1)…ways(N-1, N -1) = (N-1)! - totalWays(N-1, i - 1) Instead of inverse, we can just calculate partialSum(i, j)!!!

886C - Petya and Catacombs

1. Note that if a number appears twice, then we know a new room must added. Similarly, if t appears k times, then at least k-1 new rooms are introduced
2. If a number appears only once, we just assign to whatever room it is in. Note that we don’t have to find it!!!
3. So the answer is sum of max(0, # of t - 1) for all t that appears.

886D - Restoration of string

1. Assume the set is valid already, how do we get the final string, and is it possible to detect the invalid case during the construction?
2. We model the each independent substring as a graph, e.g., if the string is abc, then we model as a-> b -> c
3. Note that if a letter branches it is invalid too!, i.e., consider the set {ab, ac}
4. so we just build a simple cycle-list, and start from a->z try hooking up all the cycles

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!)

1. Its use case is a remote application.properties file with HA. Therefore, auto refresh is possible but not natively supported, and config client will not retry if the config server returned from eureka is dead => just like how local java app reacts when the application.properties is changed on disk, or the location of the .properties file is not valid

2. It has no client/server cache => every request does a brute force git full => yet another reason when auto refresh is not a good idea => very easy to overwhelm git backend

3. Therefore, every time we deployed config change, we will have to do a rolling restart of our service

4. It is not designed to handle secretes, e.g., API key, db password, because the decrption of such information happens on the SERVER side. This means the http (not S) response client sees will have secret in plain text. Use Vault or AWS parameter store to manage secrets

5. Cloud Config can push to client via RabbitMQ or Kafka, although adding such coupling just for notification is debatable

For AWS parameter store, each account can have max 10k keys. This may not be enough for the usage of general config server.

Conclusion: spring cloud config is a lightweight tool to manage feature flags and non-sensitve configs, but not for secrets an real-time updates

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!!!