715B: Complete The Graph

Consider only edges with weight > 0, if possible to have path < L, bad

Then make each erased edge weight 1, see if it is possible to have a path < L

find edges in the path, increase one erased edge to delta -1 , and other free edges outside path by the same amount

360B: Levko and Array

bsearch on the target c(a), then dp(i) = min steps to keep i constant, and yet satifies c(a) constraint!!!

145B:Lucky Number 2

we can see that the different betwen cnt(47) and cnt(74) is at most 1

if cnt(47) = cnt(74), we can easily constructa 474747, and append attach remainng 4 and 7s

if cnt(47) = cnt(74) + 1, and the base form is 47474, we will attach the remaining 4 and 7s to first 4 and 7

118C:Fancy Number

First, brute force to decide the target digit, sorted by (cost, improvement = (index * improvement or not))

653C:Bear and Up-Down

linear scan to find the first violating pair, we know we will have to switch one of then

each swap we can fix at most 4 bad indices, so we keep track of the first 4 bad inices. brute froce and see if all for are fixed afterwards. This also means answer -1 if we have > 4 bad indices

691C:Exponential notation

string implementation,find the decimal point index , and first non-0 digit index, we can calculate Eb

need to handle the case without the decimal point

665D:Simple Subset

Consider a(i)s > 1, we know that the max subset size is 2 => one even # and one odd number

After that, we consider all a(i) = 1, and find 2 numbers, s.t., a + 1 is prime, b+1 is prime and a + b is prime

we can pre-compute the prime # with sieve

843B:Interactive LowerBound

randomed sample 1000 entries, pick the highest number <= target, and try finding the next.

The probabily that the 1000 entries don’t hit the band = (1 - bandLength/n)^number of pokes => minimal!!!

935D: Fafa and Ancient Alphabet

DP idea is simple, but I got stuck at calculating modular inverse, because I didn’t know Fermat’s Little Theorem!!!

LL inverse (LL num) { return quickPower(num, 1000000007 - 2); }

939D: Love Rescue

Number letters - number of connected components

400D:Dima and Bacteria

1. ignore all cost > 0 edges, this means all vs with same type should be within the same component => correctness check!!!

2. add all edges with cost only to the first B of a type, and then run floyd-warshall

845D:Driving test

keep track of signs in effect and add events one by one, if potentially violates the sign, ignore

253C:Text Editor

We can delay shift left/right as much as we can

799D: Field expansion

two choices: h to a or h to b

Vault Cluster Setup

1. Our vault uses consul as the storage backend and is deploy on baremetal instead of inside a container, as per recommendation.

2. I build our vault AMI based on the example from hashicorp.

3. Because vault is an internal service, I decide to use the default internal domain name vault.service.consul as its domain name. Note that in hashicorp’s example, dnsmasq, the dns forwarder, is set to forward .consul domains to consul’s DNS interface already.

4. Use your own CA to generate vault’s server certificate and private key with your internal domain name, and update ca_public_key_path, tls_public_key_path, tls_private_key_path in vault-consul.json

5. The vault cluster terraform is very similar to the example cluster setup, minus the consul and vpc setup. Make sure you set ami_id, consul_cluster_tag_key, and consul_cluster_tag_value to your own value

6. Once terraform is run, log into any instance and init/unseal as normal. On the vault instance, you should be able to resolve vault.service.consul to the private AWS IP already

Vault Consumer ECS Cluster Setup

1. Because we need to set up consul agent and dnsmasq to resolve the internal domain name, we still need to build our custom AMI based on hashicorp’s example. Note that this packer template does not have pip and aws installed, I have to modify the install script to ensure that pip and aws are available on the sudo path, i.e., add symbolic link from /usr/local/bin to /usr/bin

2. The ecs cluster terraform setup is similar to the module. However, I have to modify the user_data in the launch configuration to include

#set up ECS agent

export ECS_CLUSTER=$MY_ECS_CLUSTER

cat <<'EOF' >> /etc/ecs/ecs.config
ECS_CLUSTER=$MY_ECS_CLUSTER
ECS_LOGFILE=/var/log/ecs/ecs-agent.log
EOF

#start consul agent
set -e
exec > >(tee /var/log/user-data.log|logger -t user-data -s 2>/dev/console) 2>&1
/opt/consul/bin/run-consul --client --cluster-tag-key CONSUL_TAG_KEY --cluster-tag-value CONSUL_TAG_VALUE

Vault-consuming ECS Container Setup

1. Each service should have its own ECS Task role, ideally one for different enviroment. This ecs task role is mainly for vault’s IAM auth, because it is very hard to solve the secret bootstrap problem with token-based auth.

2. Because we use dns forwarding at the ami level, our service container needs to be deployed in the host mode

3. When we build the docker image

   • Because we use a private domain for vault, we need to add our own ca.cert to the java trust store, i.e.,

ADD ca.crt.pem .
RUN mkdir -p $JAVA_HOME/lib/security && \
 yes "yes" | $JAVA_HOME/bin/keytool -import -trustcacerts -alias $CA_ALIAS -file ca.crt.pem \
 -keystore $JAVA_HOME/lib/security/cacerts --storepass $TRUST_PW

* Add our new cert to the java class path, i.e., 

-Djavax.net.ssl.trustStore=$JAVA_HOME/lib/security/cacerts 
 -Djavax.net.ssl.trustStorePassword=$TRUST_PW 

Round 68: Right Triangles

A variant of Fenwick tree

Round 68: Triangular Updates

For the banded updates, one technique is to convert the original array to an delta array. The main benefit is that update can be translated to exactly 2 updates instead of variable sizes => the original items will be recovered by calculating the prefix sum of the delta array.

This problem has similar idea, except that to retrieve the items, prefix sum is diagonal

Round 69: Build Correct Brackets

n^2 DP

Official solution

keep track of cost[i][j], and ways[i][j], i.e., cost/ways to make the first i chars correct out j outstanding (s, for each incoming char, we just see if we can flip or not, and update the answer as we go

Final answer is cost[N][0]

Round 69: Cover the Tree

Official solution

1. need to find a node s.t. no subtree is dominant !!!

2. Obiously, we should try each path to be leave to leave. This means we will have at least ceil(nl/2) pairs = # of pathes, so we can just pick two two leaves for the biggest two subtrees, form a path, and add the remaining leaves back to the pq

3. If there is one remaining at the end, we just connect it to the root

922D: Robot Vacuum Cleaner

Order by the ratio of h/s

proof: Consider the noise function of f(a + b) = f(a) + f(b) + ns(a) * nh(b) Conversely, f(b + a) = f(b) + f(a) + ns(b) * nh(a)

Therefore, f(a+b) > f(b+a) <=> a’s ratio (s/h) is higher

Implementation-wise, watch out for the case where nh = 0 and handling doubles!!!

934C: A Twisty Movement

Considering the point separating 1 and 2, if the band we select does not cover the point => Consider the case of not choosing anything

Therefore, we just dp on the cutting point, and reassemble the two parts 1112222111222

932D: Tree

binary lifting

938C: Constructing Tests

Easy to see the maximamum 1 pattern => x = n^2 - floor(n/m)^2

So we can brute force on all factors and see if possible to form a pair of factors

938D: Buy a Ticket

1. For back and forth, double the edge count

2. To calculate multiple shortest paths, just add all nodes to the initial heap. The final answer is the answer we are looking for!!!

377B:Preparing for the Contest

bsearch on days, and then use a pq on feasible students, but by cost. The key insight is that we can reuse the pq on the next sgement, because the previous capabily ones are still solid!!!

501D:Misha and Permutations Summation

Uses factorial number systems

652D:Nested Segments

A common pattern of solving 2-d problem with the help of a 1-d D.S. Uses fenwick tree!!!

301B: Yaroslav and Time

binary search answer + Bellman-Ford

Suffix Flip

for each number, precalcuate the binary flip of that number

for each number, we have no more that 17 bits to flip, so we can populate a DP table

Overall 10^5 * 17

Official solution

Note that at every move, the last digit keeps changing between 0 and 1, alternatively, until we reach the all 0 cases.

Therefore, all numbers end with 0 => losing case. The other is the winning case.

Falling Balls

Segment tree related

509C: Sums of Digits

need to know minGood[i], suppose we know minGood[i-1], need to find the miniumum number > minGood[i], and sum of digits = b[i], gine b(i), we know the min size of digits.

Then we know the length of string has at most two choices, size of string, size of string + 1, or sum of digits/9

In each case, we just brute force on each digit, and see if it is possible to fit that digit into, i.e., the remaining digit sum range can contain the remaining b[i]

O(n^3) run time, because we have to represent the number as a string

374C:Inna and Dima

Use 4 step BFS to find the edges between D nodes => 4 * 3 * 3 < 40 mil edges max

We can find an edge, we can can use a union find to see if the vs are within the same component, if so, then cycle.

In the end, calculate longest path in each tree

Official solution is confusing to read

264C:Choosing Balls

For each ball, calc the prevvious color index, then we have two choices, either use all values between the two balls,or just use the previous ball + current v * a(i)

353D:Queue

Observations

1. Relatively orders of girls do not change

2. t(i) >=

   final pos - init pos

   , call it D(i).

3. t(i) >= t(i-1) + 1, because at t(i-1), D(i - 1) + 1 = D(i) is occupied by a boy !!!

4. Because each one moves as fast possible, so each t(i) is the max of the two. Note such pattern seems not uncommon, i.e., giving list of reachable lower bounds, the minimal answer is the max of those reachable lower bounds

5. Alternatively, we can use the blocking -> non-blocking + hold trick!!! That is, we don’t swap the F until we are sure that we will not be blocked by previous girl. This means startT(i) = startT(i-1) + 1, if i and i-1 are next to each other. or startT(i) = startT(i-1) - (numM between i and i-1) + 1 !!!

Final answer is max of startT(i) + D(i)

592D:Super M

Find the longest path in the tree, and the answer is len - longest path, just need to tweak the algo a bit the skip subtrees with no nodes to visit

141C: queue

Sort the pair by a(i), and assign n….0 to them. Then for each, just assign them to the existing vector at a[i]. Of course, if a[i] > current size, it is impossible

The insertion can be done by res.insert(res.begin() + a[i], man)!!!

142B:Help General

cases: n or m = 1, n or m = 2, n >=3 and m >= 3. Note that it is a known conclusion that in such case a knight path exists!!! Therefore, we just take every OTHER node of the path to avoid conflict

918C: The Monster

For each i, we start scannning from right to left, and keep track of how many free ?’s we have, and how many (, we have

if size of stack is empty, but we have ( incoming, reduce ?, if nothing to reduce, we know we are bad already if size of stack + free ? % 2 = 0, we add sum[i - j] to sum [i]

The final result is the sum[0] to sum[j]

918D: MADMAX

standard DAG dp, with state[A’v][B’s][last char][A moves now]

Note the first step is special, don’t include them in the DP state

770C:Online Courses In BSU

Standard DP on DAG problem. Also note the standard 3 state cycle check problem

613B:Skills

1. check if possible to fill all skills to max level

2. The final form is that some mininum are raises, and some are increased to max numbers, we know that

a. if incrase all mins by 1, the increased cm < cf

b. if increase a skill to A, then increase cf < increaseing the min cm

1. Therefore, we can calculate the cost to make the min K aligned together

2. After that, we try filling max number one by one, and given the pre-computatin, we know exactly the max min value we can reach, so each fill step can be calcualted in O(logN)

652C: Foe Pairs

keep track of current index at 0, maintain a heap that sorted by end and the start

Keep popling the heap

1. if the curStart >= curIndex, add curEnd - startIndex, and then update curIndex to curStart + 1

2. in the add add n - startIndex

919D: Substring

1. if it has cycle, can be infinitely large

2. otherwise, it becomes longest path on the tree problem, once for each letter

788B: Weird journey

Hard problem for me - uses facts about Euler graph

117C: Cycle

Do a dfs, while maintain an index on the current DFS path, every time we reach an “visiting” node, we can check if that node’s index = current Index - 2

arc089_b: Checker

1. Note that if (x, y) is B, then it is equivalent of asking if (x + K, y), or (x, y + K) is W!!!

2. So for each cell we call categories it into one of the 2k * 2k cells, i.e., the 4 - grids form a cyclic pattern.

3. Then we try all (k^2) possibilies of lower left corner, with the help of 2-D ps to calculate v’s inside the rectangles in O(1) in each try

arc090_b: People on a Line

1. form two direct graph, one forward, and reverse

2. while not all are visited, forward visit form each vs, and then for each node in the graph, reverse visit

3. the moment we have current + edge != next, we know we have an inconsistency

Official solution

But directed graph with pos and neg weights, resepctively. Run DFS for each connected components, update dist (+ or -) as we go

arc090_c: Avoiding Collision

Consider the complement of the problem. Calculate how many ways A and B can collide?

Calculate wayS(v) = # of shortest paths from S to v, waysT(v) = # of shortest paths from T to v

So total possible choices to waysS(T) * waysS(T)

number of ways to meet in a node = for each node, if distS(v) = distT(v), then decrease by waysS(v) * waysT(v)

number of ways to meet in an edge = for each edge (u, v), if distS(u) + distT(v) + len(u, v) = distS(T), and distS(U) < D/2 and distT(v) < D/2 then decrease by waysS(v) * waysT(v)

Round 65: Crossing Tree

Answer = 2 * |E| - |longest path|

So we find the longest path first, and put all its edges on a black list

then we start from the first to the second last on node on the longest path, and print out the traversal minus the blacklist edges

Round 65: Count Arrays

I had many problems during idea and implementation!!!

Consider the final array we get, we will just consider number of good arrays ending with i with a[i] = 0.

Find the left most i, that we can construct a good array even if all betwee i and j are filled with 1,e.g, with a two pointer method, and then calculate the partial sum in [j, i).

Round 66: Counting Quacks

sort n numbers, and start calculating for the min LCM <= T, the first answer = number of index, the second answer the T/LCM(1…i)

Round 66: Flipping Matrix

We can see that if there is a row or col full of 0s, we can not flip it.

Claim: as long as no row or col full of 0s, we can find a way to flip Proof: that means, each row in each col forms a permutation of 1..n, i.e.,we just need to rearrange the perm.

So we can just, for each col, find which rows has it. and we keep track by the set size, and we sort by the set size

For each swap, we will

1. swap first non-visited set.begin() row number with the current col

2. update the doublely linked map of original col <-> after col

3. update visited row to col

Official solution

Modelled it as bipartite graph, and find a perfect matching,e.g., by Hopcroft-Karp

645D:Robot Rapping Results Report

Variant of longest path from root of a DAG

494B: Obsessive String

Hard problem for me!!!

First, use KMP to find all possible mapping points

689D: Friends and Subsequences

Segment tree related

769D:k-Interesting Pairs Of Integers

10^8 brute force

222D:Olympiad

1. Since there is no upper bound, we can always take first

2. To calculate lower bound, we just sort both runs, and run a two pointer with one moving from from L to R, one from R to L

3. if curSum >= x, move both closer, increase the count, else, move the lower bound up. Final answer is the count

622D:Optimal Number Permutation

Easy construction exists for a total zero sum!!!

601B:Lipshitz Sequence

Hard problm for me

916A: Jamie and Alarm Snooze

This is type of question where existance proof leads to solution

Claim: the answer will exist within 24 hours Proof: because each click <= 60 seconds, so we will hit every single minue of the day, i.e., we will hit 07:mm and 17:mm

916B: Jamie and Binary Sequence

This is a relaxation problems

Constraint: we # 1 bits <= N

Note that for each bit we shift to the right, we increase total count by 1, i.e., we can gradually push bits to the right until we hit N

So we can try:

1. Can push all bits?

2. if not, just push 1 to the right by 1, and increase counter by 1

916C: Jamie and Interesting Graph

Build the graph N - 1- 2-…..N - 1, calculate two primes s.t., p2 - p1 > n - 2. Assign p1 to N-1, and 1,…., p2 - n - 2 to (N-2) - (N-1)

For each remaining edege, just add complete graph i -> (i - 1 + deala) % N + 1, with weight p2, until we reach the total count

914C: Travelling Salesman and Special Numbers

The more 1 bits we have, the higher k will be. Therefore, we can dp to find a range of # of 1 bits, s.t., # of steps = k

Then we can answer the following questions, given n, how many #s <= n has < nb 1 bits

so we scan from left to right, keep track of how many 1 bits we have encountered so far, for each one bit we have, we have (remaining pos to the right choose remaining 1bits) to the answer. In the end we need to check if n itself has <= nb 1 bits

914D: Bash and a Tough Math Puzzle

Uses a variant of segment tree

232A: Cycles

Keep caluculating the complete graph, and populate matrix of said complete component

Official solution

29C: Mail Stamps

Build a graph, and dfs with a root with degree 1

346B: Lucky Common Subsequence

lcp[i][j][k] = longset common subseqeucne in s1[1..i] and s2[1…j], with the suffix the first k letters of visit

if(s1[i] != s1[j]){
	lcp[i][j][k] = max(lcp[i -1][j][k], lcp[i][j-1][k]) 
}else{

	if(s1[i]  == 'v'){
		lcp[i][j][1] = max(lcp[i-1][j-1][0..4])
	}else if s1[i] == 'i' {
		lcp[i][j][2] = lcp[i-1][j-1][1]
		lcp[i][j][0] = max(lcp[i-1][j-1][0,,2,3,4])
	}else if s1[i] == 'r' {
		lcp[i][j][3] = lcp[i-1][j-1][2]
		lcp[i][j][0] = max(lcp[i-1][j-1][0,1,,3,4])
	}else if s1[i] == 'u' {
		lcp[i][j][4] = lcp[i-1][j-1][3]
		lcp[i][j][0] = max(lcp[i-1][j-1][0,1,,3,4])
	}else if s1[i] == 's'{
		lcp[i][j][0] = max(lcp[i-1][j-1][0,1,2,3])
	}else {
		lcp[i][j][0] = max(lcp[i-1][j-1][0,...4])
	}
}

321B: Ciel and Duel

1. either we destroy all defense card and attack card or we just pick a few attack cards only

2. if we try destroying all D’s cards, we will try to match as close to the defense card as possible, and then match as close as possible the attach card. If feasible, the answer is total of remaining attacks cards after step1 - total of D’s attach cards

3. the decide how many attack cards we destroy, we have to brute force on how many 1..i, sorted by strength, of D’s attack card.

Official solution

770D: Draw Brackets!

During the bracket matching process

1. Keep track of which level the bracket is at

2. Keep track of max level all together

3. We add a space only for the, i.e., the matching [ is next to ]

223A: Bracket Sequence

maintain a balance of strings, on each closing ones, we can calculate

1. the current length of the string, by peeking at the top of stack’s pos

2. how many [ we have in this substring => by pre-calcuing a prefix sum

In the end we just find the best solution

343D:Water Tree

Uses segment tree

372B: Counting Rectangles is Fun

Note that q will dup # of possible cells, so we just brute force calculate if (i, j, k, l) is a properrectangle in O(n^4)

After this, we can use a 4D consecutive sums!!!

792D: Paths in a Complete Binary Tree

1. Up: find the right most 1 bit, change this bit to 0, check the bit to its left, mark it 1

2. Left: find the rightmost 1 bit, change the bit to the right to 1, mark cur bit to 0

3. Right: similar to left, except we leave curbit alone

915C - Permute Digits

This follows the patterns of relaxation under constraint!!!

The key insight is that it doesn’t matter how you do brute force search, you have to try the minimal suffix, and see if it can be smaller,i.e., the first digit < b’s digit may not be d[i] - 1.

One counter example is 31, 30, the answer should be 13.

915D - Almost Acyclic Graph

The removed edge must be on a cycle, so we just find a cycle, and try edges on them one by one, to see if the removed graph is acyclic.

Note that to detect cycle in directed graph, we need a “visiting” state on top of the visited state.

I got the idea during the contest, but i was hesitant to calculate n^3 solution, because I didn’t notice that # of edges is no more than 10^5, which makes the overall performance right into the bound!!!

906A - Shockers

Maintain a set of impossibles

1. for each ., add letter to impossible

2. for each !, add all letters not in the word to impossible, and check if all but one letter in the word is invalid

3. for ?, check and update if we are in guessed mode

Official solution

From the last entry we know the answer, and then for each letter, we calculate the latest entry that deny’s its existance. The final answer is the latest of all other 25 letters

912C - Perun, Ult!

This problem has a lot of corner cases!!!

Three types of events

1. health is set to less than the kill threshold

2. health is set to higher than the kill threshold

3. health has been regened more than the threshold

Note that max value must exist in the second right before the second and third event. So for each event, we add a type 2 and or 3 events, and then we do linear scan

agc020_a: Move and Win

A naive DP-ish approach will not work, because you can move back and forth => creates cycles, thus should not use DP approach and think about an insight based approach

agc020_b: Ice Rink Game

I used a band-based approach to reverse and calc min-max values.

But note that at each step, f(x) = x - x mod a[i], i.e., f(x) is monotonic, and the whole sequence of actions can be though as a composition of monotonic functions. Thus, we can just bsearch min/max to see if the final answer >= 2 for lower bound, and <= 2 for upperbound!!!

The uppoerbound for k is 2 + K * max(A(i))

agc020_c: Median Sum

Consider any subsequence and its complements, we know that one must be =< total/2, one must be >= total 2, i.e., for any subsequence <= total/2, we can mirror its complemnet to the other side => total/2 IS the cut off value for median!!!

Therefore, we can DP to find the min value >= total/2. We can compress the DP state by keeping only a list of values, and scan from max value to min value

Official implementaion uses a bitset which I don’t quite understand!!!

Round 63: Find Remainder

1. K > max(b(i))

2. a(i) - b(i) >= 0

3. (a(i) - b(i)) % K = 0

4. Consider the GCD of all deltas > 0, and filter buy the constraint that K > max(b(i)).

5. Note that K should be smallest, i.e., GCD % K = 0 !!!

6. So we just bruteforce from 2 to sqrt(GCD), update K by either divisor or GCD/ divisor, as long as they > max(b(i))

Round 63: Graph Game

The key insight is that # of even deg vs has the same oddity as total # of vs!!!

Therefore, suppose N is even, A will always pick the scenario with even # of even degs, B will always pick the scenario with odd # of even degs, i.e., B can not lose => A always loses.

Conversely it is true for the odd case

Round 64: Create Tree

Just check them one by one, because unique path among all = unique path from single node to all!!!

Round 64: Limited Moves

Claim: A will win all cases if N is not a power of 2!!! Proof: we keep removing the least signficant bit 1 in current N, we know that the next move will introduce 1s to the right of the bits B removed, i.e., we can keep goinging, this means as long as B can move, A can move, i.e., A can not lose

How to verify that consul is in a normal state

1. the nodes request shows expected number of nodes

2. insert a value on the first node, check its value on the second node

Drill 1: single node failure

1. Stop an EC2 instance, verify autoscaling group kicks and spawns a new instance.

2. Verify that the new instance joins the existing cluster and reaches a stable state

3. Go inside the container, verify that the new consul instance is at the correct version (to test the rolling upgrade case)

4. Restart the stopped instance at 1), force remove it after it joins the new stable cluster. Otherwise, force remove it.

Drill 2: loss of quorum - multiple instances down

1. Reboot all servers

2. The ECS should kick in and all servers restart and rejoin the same cluster successfully

Drill 3: loss of quorum - complete outage

1. Stop all but one server. ASG will kick in and spawn new instances, but the cluster is at a corrupted state, so any rejoin will fail.

2. Stop all newly spawned instanced expect the original alive one

??4. Change the -bootstrap-expect, note for the init bootstrap you need -boottrap-expect flag for sure -need to take out ASG desired capacity

1. go to the -data-dir of each server, inside ratf/ dir add a raft/peers.json file. Find the server id in node-id file of data directory. This file should include ONLY the alive node

2. reboot the only alive server now. Make sure the log shows that peers.json is read correctly

3. Go into the new instances, and manually join the node to the cluster

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