arc098_b: Xor Sum 2

By case discussion, we can see that we can treat each bit independently. For each bit, we can just caluate the last 0 to the left of it, and the add the min distance from all last 0 to the answer

arc098_c: Range Minimum Queries

Lets fix X first and discuss cases!!!

Extreme case: suppose X is the min value of whole array, to optimize the target value, we just pick the min Q values

Now suppose, we try all possible X values, then we can separate the array into bands, each of which has value >= X, and then we combine all bands with length >= K, sort the combined band, and take the top 1 and Q entries. Note if we have < Q entries, the the X value is too big.

agc025_b: RGB Coloring

We can view the combination as painting two colors independently, i.e., A * a + B * b = K. So for each a, we have a fixed b. This means, for each a, we have a fixed b, and introduces (n choose a) * (n choose b) ways.

1. Persuading bigger team is MUCH harder than the smaller teams, but working with people IS the work in a people-organization!

2. Social proof often matters as much, if not more, than facts and logics.

3. Presentation matters! It can change people’s view even if there is nothing they don’t already know

4. When getting a “NO”, ask what you need to do to get a “YES”, and ideally let the other side commit on that.

5. Basic principle: short feedback loop so that you can gain momentum for your work

6. Find who might support you, pitch your ideas to them individually, and gather them together so that you can have a self-reinforcing concensus.

Note: all links are in Chinese

Mobike

1. Use case: aggregate isolated MySQL clusters for OLAP. They run TiSpark on top of it

2. Production TiDb cluster has tens of nodes, with tens of TBs of data.

Ele.me

1. To keep the production table size in check, they regularly purge production tables and move old entries to separate archive tables

2. Need to watch out for the performance issues of DDL operations in production and archive tables

3. For migration, they use the official TiDB syncer tool to run TiDB as a Mysql read slave

4. Daily archived > 100 mil rows, > 100 G. Current TiDB volume “tens of TBs”

5. As the post was written, TiDB Binlog relies on Kafka

Ping++ - Payment SaaS

1. Use TiDB as dataware house. It replaces AliCloud’s ADS and ES

2. ADS has cost issue, and ES has difficulty handling complex queries with high dev/op costs.

3. Current cluster 5 nodes, each with 16 cores and 32G ram

A Truck Fleet Management SaaS

1. Sync data from Alicloud’s DRDS to TiDB, and runs TiSpark against TiKV, TiDB’s storage layer

2. 2T raw data incoming per day.

A Restaurant Merchant/Order/Cashier Saas

1. TiDB supports the operational datastore. Check the link to see the test queries they run.

2. Before: RDS -> Mongo via Kafka -> Hive. After: RDS -> TiDB via Kafka -> Hive. TiSpark queries both TiDB and Hive

3. Cluster setup: 8 nodes. 5 of them are for storage layer. Each TiKV/Storage node is 16 core/128 G ram with 2 1.8T SSD

4. Peak QPS 23K. Data volume “couple of Ts”

Another Restaurant Merchant/Cashier SaaS

1. Near real time complex queries. TiDB replaces Solr.

2. Current deployment 8 nodes. Storage layer on 16 cores and 64G ram

An IoT company

1. They need real time analysis capabilities.

2. Their raw data source is Mysql databases, but they don’t want to spend too much effort on Mysql -> Hive/Hbase ETL pipeline.

3. They need Spark support, so they choose TiSpark + TiDb

Motivation

Given a tree, how many paths of length k are there?

Centroid

• Claim: We can find a vertex v in tree s.t., none of the subtree has size > N/2 if v is the root of the tree
• Proof: Suppose we pick a random v as a candidate, if one of its subtree has size > N/2, we move to that subtree’s root.
• Note that finding the centroid will be similar given the DFS

Centroid decomposition

1. Starting for the whole tree, find the centroid
2. find the centroid for each subtree, and connect them to the centroid find in the previous step
3. recursively apply, until we form a new tree

Properties of Centroid Tree

1. the new tree contains all nodes of the original tree => by tree induction
2. The height of the tree is O(logN) => because at each level, the size of max subtree is reduced by at least half
3. The construction of the tree takes O(nlogn). Because at each level, we traverse each node in the tree at most once, and there are O(logN) levels
4. Consider any path A - B in the original tree, the path can be broken down to A - C - B where C is the LCA of A and B.

Proof: Both A and B lie in the subtree where C is the original subtree, and they were separated into different subtrees when C is chosen, i.e., C will be node with smallest label in the original A -B path

1. So we decompose the given tree into O(nlogn) different paths, each of which is a centroid to all its children. Again, the total # is O(nlogn) is because at each level , we introduce O(n) paths, and there are O(logN) levels in total

Round 77: Two Rows

DP state = cost(col, isFirstRow, isFirstRowFilled, isSecondRowFilled, isFirstPlayer)

Round 77: Expected Lcp

Uses trie

Round 78: Banned Digits

Starndard DP - With the same prefix, how many #s we can assemble given the constraint

1. go for possible #s < next digit, and then pow of remaninings

2. go for the same digit, keep going

Round 78: Strange Matrix

Uses segment tree

1A: Waffle Choppers

Consider only one dimension, we can see that we can determistics decide which row to cut. If a row is empty - it doesn’t matter!!! Either way would do

1A: Bit Party

1. bsearch on the final answer

2. Note that R <= C, so we can just calculate the capacity for each cashier!!!

1B: Mysterious Road Signs

1. Every time we see a new segment, we can assume its left is the start of new segment, and keep scaning until we have more than two possible choices. Then we know it is the end, of the segment, and we need to start again. Of course, we need to try both directions

2. large dataset can be computed with divide and conquer - just need to guess the 3 possible cases: all in the seg, left works with left, and left works with right => T(S) = 2T(S/2) + O(S) gives O(SlogS)

arc096_b: Static Sushi

Try any of the four possible options, so for each sushi, we need to calculate

1. net gain at this point from the start clockwise, and max possible netgain seen so far

2. net gain at this point form the start cclockwise, and max possible netgain seen so far

We can scan each point, and check all possible net gain + maxpossible negain seen so far from from the opposite direction

arc097_b: Equals

We can form pairs as disjoint sets, inside each set, see how many index values appear also as value itself

arc097_c: Sorted and Sorted

Hard problem for me!!!

The inversion number is the cardinality of inversion set. It is a common measure of the sortedness of a permutation[5] or sequence.

Standard comparison sorting algorithms can be adapted to compute the inversion number in time O(n log n)

From the constraints in the statement, at any moment, the set of placed balls must be of the form ”i black balls numbered 1 through i, and j white balls numbered 1 through j”, and use an O(n^2) dp to find the min inversion # = cost

agc024_b: Backfront

Find the longest consecutive increaseing subsequence at each index, and take the longest one

agc024_c: Sequence Growing Easy

1. x1 = 0, and x(i + 1) - x(i) <= 1

2. Compute the lowerbound for the operations, and claim that the lowerbound is achievable. I got stuck at the lowerbound part!!!

3. The observation is that we need to compute # of different consecutive pairs, which is either 1, or X(i) contributed by each entry

1. Such tracing tool is good for latency/performance troubleshooting, and investigating of frequently-occuring bugs. HOWEVER, you still need tradiitonal ELK-ish logging infrastructure to do customer support, mainly because sampling rate is kept low for performance

2. Need to config message format in to follow sleuth’s format. By default it listens to stdout appender

3. The out-of-the-box zipkin jar/docker doesn’t handle service discovery and registration. You need to wrap zipkin-server in your own spring boot app to register it.

4. To disable zipkin via config, need to turn off both sleuth and zipkin

5. Zipkin doesn’t have access control, you probably need to build a reverse proxy for this.

6. Need to create zipkin db/tables before connection. It won’t auto create

7. If you don’t see some trace, make sure the very begining of the trace is recorded,i.e., if the very first receiver of the request is not recorded, the trace won’t appear

959D: Mahmoud and Ehab and another array construction task

hard problem for me!!!

961D: Pair Of Lines

take 3 points, if they are on the same line, keep scanning, and exclude all other points => they should be on the smae line

Otherwise, try one of the 3 possible lines, as the first line

960D: Full Binary Tree Queries

1. order of operations doesn’t matter

2. so we can just, keep track of shifts of two ways at each level

3. every level we move up, we need to calculate current shift - parent level shift, which, happens to be continous, means we can different apply delta as shift, and apply mod ops

962D: Merge Equals

1. Keep track of each number’s occurances

2. from min # to max #, get occurances, sort by the index, and populate the 2 * X, entry with the right value

3. scan through the elements agent and populate the remaining elemnets

Each operation reduces the size of the array by 1, so it is O(nlogn)

963B: Destruction of a Tree

If |V| is even, then it is impossible to win, because |E| = |V| - 1 is odd, and we take out only even # of edges at each step.

Proof: By induction, on the size of the tree

1. By induction, we can delete all subtrees with EVEN # of child nodes, and the oddity of the # of nodes with current tree is preserved

2. Current root must have an even degree, because in the non-true root key case, the remaining subtrees each has ODD # of noeds, so the total nodes must be even

3. Now we delete the root, and can induct on the full tree with ODD # of nodes case

Round 74: Two Squares

Bruteforce search on the TL corner of the first square. And then update all possible choices with squares with TL corner with the chonse square. In the end, pick the remaining one between the one with TL outside the sqaure, and within sqaure

Round 74: Minimum by Xor

Need to print all subsets, but how to prove it?!!!

Round 75: Race Cars

Essentially bsearch on each way, and see which one can be better

Round 75: Electric Cars

Sort by arrival time, and start simulation

1. maintain a list of interrupted cars, current time, current charge, remining to charge

2. for each incoming car, try finish the current car first

3. if not, add the current car to the interrupted list, update current car

4. if yes, keep removing head of the list, and try finishing them, add the remaining back for the last one

5. in the end, clean the current, and all cars in the list

Round 76: Candy Boxes

just keep track of budget on each box, and assign them in sequence

Round 76: Pyramids

1. For each column, we need only the lowest point, and then we add point from left to right, and take out all shadowed points. Note the new point itself can be shadowed. This works because if the right most can’t shadow the new point, the points to the left can’t either!!!

2. To calculate the intersection between pyramids, we can use math or bsearch. Note that if we deduct intersections at the end of each step, we can just compute the end points from left to the right, one by one!!!

954C: Matrix Walk

1. scan through all diffs, they must be either 1, or a delta => which we find y

2. now we can go through the steps again, and deduct x, i.e., just need to ensure that cols match

954D: Fight Against Traffic

Compute all dists from s, and all dist from t

For each pair (i,j), see if (s,i) + (j, t) + 1 or (s,j) +(t, i) + 1 is smaller

955C: Sad powers

Generate all possible answers for P >= 3, and discard all perfect squares!!!

At each query, can get the band range in two bsearchs, and perfect squares can be calculated via math

934D: A Determined Cleanup

Polynomial long division

957D: Riverside Curio

Hard problem for me!!!

1. Note that total marks at each day t(i) = m(i) + d(i) + 1

2. lower bound: t(i) >= max(t(i-1), m(i) + 1)

3. Each day leaves at most 1 mark => t(i) >= t(j) - (j - i)

Claim: we will try finding a solution that satifies all 3 conditions, then we have a valid sequence of actions, and this solution is optimal

Proof: Going backwards, we reduce the current number by one - try lower the upper bound as much as we can, even to the point of too low, and lowerbound it with the current m(i) + 1 to satify condition 2.

After that we just run forward again to pad the lower bound we reduced too much in the first pass. This simulation process also ensured that the solution is valid

Terms

1. Grants: the mode/scenario/method a client acquires the access token, as per offical OAuthSpec

2. Resource owner: the entity that can grant access to the resource

3. Resource server: the server hosting the resource

4. Client: the entity that wants to access the resource. Client will need authorization from resource owner.

5. Authorization Server: the entity trusted by the resource server. AS will issue access token to client, once resource owner authenticates and authorizes client’s request. Often called identify provider

6. Scope: the permission/access client wants to resources

Notes

1. OAuth is an AUTHORIZATION protocol but NOT an authentication one. How authentication is undefined, but normally uses Open ID Connect, which builds on top of the OAUTH.

2. OAuth flow is actually very similar to Open ID (NO CONNECT)’s. The key difference being that the former returns the access token, while the latter just a signed claim that client got the the authorization from the user. Hence, Oauth workflow is often called pseudo-oauth-authentication

3. Which OAuth grant to use depends greatly on the context.

   a. Client Credential: authorizing machine to access, no need of permission from user, i.e., machine to machine authorization = client is the resource owner. Example: a cron job that uses an API to import to DB, and the application can use the oauth access token to call the API on behalf of ITSELF

   b. Otherwise, Authoerzation Code: need permission from user, and client is a web app and runs on a server. This is considered safest, because AT is to the web server hosting the client, without going through user’s web browser

   c. Otherwise, Resource Owner Password Credential: Client is trusted with user credentials. Note that this flow is a legacy, and should be used ONLY WHEN ACG is not available

   d. Otherwise, ACG if client is a native app

   e. Otherwie, client is an SAP: implicit grant.

4. Authorization is mostly role-based instead of ACL-based. Note that there exists a standard DB model for RBAC.

Authorization and Role Management in Microservices

The discussions I found give VERY diverted opinions on how to implement authorization in a microservice environment. I will just list my findings and conclusions here

• Most authorization rules I found in a microservice environments are role-based instead of ACL-based. May consider a specific user role/identity service to handle the user-role mapping. However, must be careful because this user-role mapping service can quickly become the kitchen skin of contexts from different domains
• Often, a service has a very domain specifc authorization rules and roles. In this case, such logic and roles, should remain within the service, but the trade off means we need to replicate main user database, or at least access a centralized user-role service
• Most likely you will have some global default roles, e.g., admin, billing admin. These roles should stay with the general global auth service, i.e., when we generate the JWT, we should attach the applicable global roles to the JWT. Moreover, these admin roles should be the only roles that can bootstrap service-specific roles and assign them to the users.
• JWT should have only global role info, because:
  • JWT is normally part of header, which is limited to 8KB.
  • We don’t want to leak other service’s context.
• This setup suggests that role popluation happens twice, once at the auth service, once at the actual request processing service, and the actual role/permission check is decentralized instead of centralized.
• Favor coarse-grained roles, modelled on how organization works

JWT

• Three parts: header, payload and signature.This means microservices need to know the public key to verify the signature.
• Normally sent with the authorization header as the bearer token,i.e., use the bearer schema
• API gateway will forward the request with JWT to the service, which will in turn will decide if it will grant the resource or not.
• We may choose to let user use a reference token, and API gateway will translate the reference token to the jwt token. Note the reference token can come from an OAuth server. This also suggests that JWT stays within the private network, and only reference token is on user’s browser session

Note that Spring Cloud Security is exclusively for OAuth2 scenarios. Treat it as a complete different thing from Spring Security! Also, Spring Security has a very specific, pre-defined authentication flow, from where you can find names of many auto-wired/injected classes

Common Choices

• Spring cloud security
• keycloak by JBoss
• OpenID-Connect-Java-Spring-Server
• Apereo CAS

Workflow

• Client logs in to acquire access token
• Client sends access token to the API gateway
• Gateway uses auth server to validate token and convert to JWT
• Gateway sends jwt token along with requests to backend microservices
• Every microservice has JWT client to decrypt user context inside the jwt

On the authentication service side, generate JWT and add it as “Autherization: Bearer” token. May consider writing it in an authentication filter that extends RequestHeaderAuthenticationFilter

On the resource service side, to parse the incoming JWT, we have two implementation options

Option 1

1. add an AUTHORIZATION filter that extends BasicAuthenticationFilter.
2. This filter will parse the token text into a UsernamePasswordAuthenticationToken
3. this authentication token will be placed in the context via SecurityContextHolder.getContext().setAuthentication(authentication)
4. We also need to extend WebSecurityConfigurerAdapter. Inside protected void configure(HttpSecurity http) throws Exception, we configure authoriazation for each path. Note that we need to explicitly set CORS config here to enable traffic from all source. This class also sets what AuthenticationManager to init/pass-in/config.

Option 2 (less common)

1. Add an AUTHENTICATION filter that extends RequestHeaderAuthenticationFilter. This filter will have a reference to the AuthenticationManager, which ,by the design of Spring Security, passes requests through a list of AuthenticationProviders
2. This also means we need to extend AuthenticationProvider to parse token and authenticate
3. Don’t forget to inject our filter and provider into the context

arc093_b: Grid Components

We just a grid with 41 rows, and 100 columns

row 0 - 20, fill with #

row 21 - 41, fill with .

for each additional ., iterate to add to (2i, 2j)

for each additional #, iterate to add to (21 + 2i, 21 + 2j)

agc022_b: GCD Sequence

Overall, a hard problem for me!!!

Note that the constraint is equivalent of saying gcd(a(i), S) != 1

Note that we have to pick about 2/3 of all numbers, so we can define S to be multiple of small primes => S = 6K

So we pick 6K + 2 , 6K + 3, 6K + 4, and 6K, and make sure we pick 2, 3 to force all gcds = 1

Note that N <= 5 case is different from N >= 6 case.

arc095_c: Symmetric Grid

Overall a hard problem for me!!!

1. notice that the order of ops doesn’t matter, so we try all row ops and then col ops

2. When W is odd, we know (W + 1)/ 2 is a palindrome

3. Keep track of unused pairs of cols, and see if any of the reversed strings are the same, and populate assignment

4. However, H! possible row combos are too slow, so we consider only all possible parings of rows 11!! = 11 * 9 * 7 … * 1

• Win you the trust and respect of your teammates, before attempting any major rewrite
  1. Project level refactoring should not go in parallel with day-to-day requirments dev. Use a mock refactoring to discover potential depenedency problem, and refactoring them in day-to-day devs. Finally, halt dev for 2-3 days and focus on project refactoring.
  2. Refactoring rarely-changed code gives little benefit and most likely doesn’t outweigh the cost. Espcially a lot of such legacy codes are hard to maintain and extend.
  • Refactor as little as possible (change ONLY what you need), and unit test is basis for refactoring
  • starting very coarse-grained end-to-end test, and gradually add more, finer-grained tests. End-to-end, integration, then unit tests, in that order.
  • don’t start making changes until you have a suite of tests that can spot behavior changes. There are times when things that appear to be bugs are actually weird features that the business needs to function.
  • Focus more on the user scenario than code logic 7. To solve branch conflicts, use feature flag to hide development in progress 8. Open to extension, close to changes, because changing existing code is easy to introduce new bug 9. Refactor code to be extended, let existing unit tests cover that (only change code), and then enhance with TDD (only add code) 10. Refactoring across services is hard. Options:
  • Don’t do it - perfectly valid
  • One big version change
  • Long term ownership can’t be ambigious. Build a temp team to build the third service - Conway’s law

arc091_b: Remainder Reminder

Just interate through i * f + K, for all i in [K + 1, N]

arc091_c: LISDL

A >=1, B>= 1, A + B <= N + 1.

Claim: A * B > N Proof: I got stuck here!!!

arc092_a: 2D Plane 2N Points

I used maximal bipartite matching. given N = 100, can be solved with Ford-Fulkerson as network flow problem. Note that this algo has a simplified form for implementation!!!

Note that this approach costs O(V * E), because for each node, we essetinally tranverse all edges in a DFS way, during the shift update with the help of visitor

Official solution

Similar to all pseudo bipartite matching problems, we can just sort one side, try matching head at each time, and take the most restricted matching at the time, so that we leave more possibilites to the remaining ones. Note that translating it to bipartite matching loses too much contextul information, and thus a harder implementation.

Note the core reason the greedy approach works is that suppose the optimal solution didn’t match the current head or matched a different one, we can swap the mapping while maintaining the count

arc092_b: Two Sequences

Consider each bit indepdenently

Round 70: Min Distances

the classic shortest path relationship is that minD(a, b) = min (a, c) + min(c, b) over all cs

Note that when we can’t find c that satifies such relationships, either our graph is invalid, or a,b is direct!!!

so we just populate matrix and re-run f-w

Round 71: Binary Differences

Claim: the set must be continous

Proof: suppose we find the max diff, we can keep taking off left and right end and reduce the diff by 0, 1, or 2, as we like

so we can just find the max and min possible k value. Note that for the ease of calc, we can map f(0) = 1 and f(1) = -1

Round 71: Russian Dolls

easy to calculate # will gain by reducing to the next level, and keep track of the max # we have seen so far, we stop, when the new # >= seen

Round 72: Beautiful Matrix

only 4 possible cases

1. swaping top row

2. swapping bottom row

3. swapping left col

4. swapping right col

Round 72: Spring Cleaning

So the graph is a cycle or sunny graph. Easy to see we can clean all but 1 node. So just DFS and print it in reverse order except the last one

Round 73: Binary Isomorphism

Hard problem for me!!!

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