931D: Peculiar apple-tree

Claim: if a level has an odd # of apples, it will contribute an apple in the end!!!

Proof: by induction on levels, when we move the apple to the level above, the cancel rule means the oddity is preserved. => at the root level, even means empty, odd means 1 => so all even cases lead to cancel at the root

937D: Sleepy Game

We need to find a path, s.t .

1. even length

2. the final node has no outgoing edges

So we assign a node into two cases: arriving at the node, with the oddity of the path traveled so far, and build a graph!!!

So we just do a DFS, and try find one such paths, and also keep track of existance of cycles, so that we can ensure that we can keep at least a draw

940D: Alena And The Heater

for each new digit we processed, we can see that

1. 11110 case, up can push down ub of r

2. 00001 case, we can inc ub of l

3. 11111 case, we can increase lb of r

4. 00000 case, we can dec up of l

5. if the last 4 digits are not 0000 or 1111, we can not infer anything

In the end, we take ub of r and lb of l, see if they intersects

946D: Timetable

Official answer uses naive dp, although i doubt it will pass the run time check

950C: Zebras

Simple greedy solution would work

950D: A Leapfrog in the Array

Note that all shift happens between even indices, while start with an odd index

Let’s conside the moment where an odd inde is first “merged” with the band to the right

1. we know for sure the length of the band to the right

2. for the odd indices to the right, they haven’t moved yet

The key insight I missed is that, at each step, the move size reduced, and conversely, increased by itself!!!

Proof: in the jump, we go from p + (n - p/2) to p, i.e. the jump length is n - p/2,

so first jump length is 2 * n - from, to 2 * (from - n), the second jump length becomes 4 * n - 2 * from, we can see that the jump length doubles at each step!!!

So that for every even index, we calculate the jump length by reverce, until the jump length is 1 => that is the first “merge” we made, half that is the answer

948D: Perfect Security

Use trie to optimize the O(n^2) solution

Drill 1: Couple of vault instances down

1. log into each downed instance, unseal the vault

2. Make sure we can still read the values from vault from command line/curl

3. Check consul and make sure the vault instance back online

Drill 2: The whole vault cluster is down and unable to restart

1. retrieve the last stable AMI, or rerun packer to generate one

2. Use tf to generate the new vault ASG, but with the same consul tags as the prvevious one

3. login into each instance in the new cluster, unseal the instance, and verify that the instance is healthy on consul

4. use tf to destroy the old vault cluster’s ASG

Drill 3: Restore vault data stored on consul

1. take a snapshot of current consul cluster

2. create a new consul cluster with new tags

3. restore the consul cluster from the snapshot, and deploy a new vault cluster on top of the new consul cluster

4. unseal the vault with original keys and verify that read is successful

HTTPS requires an SSL/TLS certificate, which in turn requires a domain name for your internal service.

Two options

1. use a .local domain, e.g., our vault is on vault.service.local. Note that this domain is a reserved TLD by the internet standard

2. use a private subdomain in a public domain, e.g., vault.internal.mycompany.com.

Based on my research, there is no conclusion on which way is preferred. The major benefit of the second appraoch is that you can sign the certifcate with the public ca, whereas in the first case, you will need your own CA to sign it

In either case, this means you need to send up DNS multi-cast, e.g., via dnsmasq and internal DNS resolver, so that domains with these specifal prefixes will be resolved by your company’s internal DNS.

If you use the first apprach, make sure add ca.cert to SSL, NSS (which curl uses), and java keytool.

Another catch is when you want to place a (most likely internal) ELB in front of your internal service. The ELB needs to be a TCP ELB, so that it won’t try terminating the SSL connection

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