Why migration

1. Spring Cloud Config does not provide good secret management solutions, compared to vault + consul

2. Using Eureka implicitly infers that all our services will be using spring cloud. This assumption is too strong

3. The self-preservation node makes our DR drills trickier.

4. Modifying the main DNS entries with EIP is annoying for our DR drills. If we use hosted zones instead, the from time to time the service will report unable to resolve the main eureka DNS entries.

5. EIP is public ip, but most likely you want your Eurkea instances to be on private subnet

6. Need to explicitly override EurekaIp if you want to run your services in ECS, otherwise, it will register as the docker container ID

Migration Plan

1. For each service to migrate, start a new branch with dependency and config changes. This branch keeps rebasing from dev

2. Migrate Cloud Config as the first service, so that other services can reuse it.

3. Update all services build jobs, and create a new ECS cluster that mirrors the existing ones

4. On production, change the DNS record to point to the new ECS cluster’s LB

5. During the process, keeps rebasing from the master

6. Run DR drills before completely replaces Eureka

Setting up consul

1. For the deployment, we use an autoscaling group (ASG) of fixed size, i.e., min size = max size = 3 or 5, and set -bootstrap-expectto the cluster size. Desired size for ECS and ASG are equal to the min size

2. Use -retry-join "provider=aws tag_key=$TAG_KEY-ecs tag_value=$TAG_VALUE" to mark the consul EC2 instances. Other flags don’t seem to work in my experiments.

However, this retry-join by tag actually gave me a lot of trouble in DR drills, namely the handle the case where majority of instances are replaced by autoscaling group. In the end I took it out and manually join the cluster. Consul is smart enough to rejoin previously know cluster

1. Need -client 0.0.0.0 so that the consul inside docker can receive traffic from outside the docker,i.e., consul will listen to all network interfaces

2. The image we use is based on the offical consul image, but we have to modify docker-entrypoint.sh to include EC2 API call. So that we can fix the node id to the EC2 instance ID, and address to the EC2 private IP. I also tried invoking the curl call from terraform or supply the command from docker command, but my efforts are not successful

A working example, inside the docker-entrypoint.sh

set -- "$@" agent -server -ui \
        -data-dir="$CONSUL_DATA_DIR" \
        -config-dir="$CONSUL_CONFIG_DIR" \
        $CONSUL_BIND \
	-bootstrap-expect=$BOOTSTRAP_EXPECT \
	-node $(curl -s http://169.254.169.254/latest/meta-data/instance-id) \
	-retry-join "provider=aws tag_key=$TAG_KEY tag_value=$TAG_VALUE" -client 0.0.0.0 \
	-advertise $(curl -s http://169.254.169.254/latest/meta-data/local-ipv4)

Setting up consul client

1. EACH instance in your service cluster needs consul agent and registrator running. This can be done by using ECS api call in user data AND adding that to systemd, or just force ECS task capacity same as cluster size.

2. By default, i.e., without -dev or -server, agent runs in client mode. It can reuse our custom consul server docker image above.

3. Registrator and consul client should not be in the same task, because during start, registrator should wait for the consul client to get ready. Otherwise, the registrator ECS task would fail.

4. The registrator automatically discovers the service name by its BASE docker image name. This means all our deployments should use a single ECR with different tags

5. However, most likely you don’t need the registrator, because most consul client package will include the registration

6. Consul client agent container should run in the host mode, so does all its client programs, i.e., we should manage ports to avoid conflicts here. Note if the network is host mode we don’t need to set -client

7. Unlike server agent, client agent can and should rejoin by tag, since its stateless

Gotchas

1. For spring cloud consul, MAKE SURE you set spring.cloud.consul.discovery.queryPassing = true. Otherwise, spring’s consul library will grab unhealthy instance as well. This caught us off guard during our DR drills.

2. To deregister a service instance, use the agent API instead of catalog API on the same host the service instance is running. The service ID is the “ServiceID” field returned by the GET request

3. ECS has no auto restart API. So as part of deployment, we need to register a new service definition and then update the service, as shown by many other people. However, pay attention to the minium health threasold you set. If it is too high (> 0 if you have only 1 instance), the auto restart upon service update will not kick in, because otherwise, the # of health services will drop below your min thresold

612D: The Union of k-Segments

Do a standard event based approach. Note need to handle the tail.

877D: Olya and Energy Drinks

How to improve the naive BFS runtime?!!!

To root cause is there are too many wasted edges => therefore, we try not to store or traverse them.

For each row and col, we keep set of unvisited cells, at each step of BFS, we just keep using lower_bound() and upper_bound() to find and later remove the next cell to visit

442A: Borya and Hanabi

1. Try all 2^10 guesses, maintain a colorCount for each card, and cardCount for each color, current know cards.

2. for each hint, populate corresponding color/card. every time we fix a point, reduce the unknown count for each color-card, by 1. Note we need to skip the already populated case.

3. Do a recurisve reduction, stops if current know cards = n, or this reduction finds none that can reduce, if only card is known, check if the card has only 1 type of unkown color, if so, mark it as known. if only color is known - similar. If both are unkown, we can try only if only 1 color has 1 unknown cards.

14D:Two Paths

Official solution

The two paths don’t intersect, so we can try each edge that cuts the tree into two, and calc the product the longest path in each subtree

891B: Gluttony

find the inverted index of all values, and shift them to the left by one, i.e., new inverted index for 1 is the old inverted index for 2.

Proof: such shift works because, consider the subset doesn’t include the old 1 index,i.e., the new n index, the subset sum of the new one is already greater than the old one

Otherwise, the subset sum is the total sum, which is a constant, mius the subset doesn’t include the old 1, which is already different

778B: Bitwise Formula

iterate them bit by bit, use dp to solve the value

514D: R2D2 and Droid Army

since its continous, just use a two pointer to calc shift, use a heap on each col to maintain the max value. not we will allow start = end + 1, to mark invalid ones

627B: Factory Repairs

looks like fenwicks tree problem

263D: Cycle in Graph

Consier the case where we can not expand the path in DFS ANY LONGER, then all its neighbors must be on the path generated by DFS already!!! so the first vertex on the path marks the start of the cycle, and the cycle has K+1 vertices, i.e., len k + 1

I got stuck here because

571B: Minimization

This follows the patterns of decoupling (1D -> 2D) into independent parts and then recoupling (2D -> 1D)

First, notice that we can decouple the whole array in a list of silo, the indicies from the same silo have the same value mod k. The best value for each silo is to sort inside it, i.e., the different between max and min.

Moreover, to achieve the optimal value, we should avoid overlaps between the max and min values. Therefore, the problem reduced to, given a sorted array, how do we partition them into S segments (no rotation either, otherwise we will introduce overlaps)!!!

Claim: we have k - (n mod k) groups of size n/k!!!

Proof: because we organize the groups by mod value, so we have k groups in total. Because each index is evenly distributed, group sizes are either n/k or n/k + 1. We can see that we have n mod k groups that has size n/k + 1, and thus the remaining ones are the smaller groups

Now, how do we do the partitioning? Note the placement order matters even with the same group count, because the gap between silos are ignored, so we need to place our small and large groups carefully. Therefore, we do a O(k^2) bottom up DP on the optimal placement, and keep update the dp[l+1][s] or dp[l][s+1] value

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