arc099_a: Minimization

Official solution: Always ceil(N-1/K-1)

Proof:

1. each op increases # of 1s by K-1 at most, so we know it is the upperbound. We claim such bound is always achievable

2. Construct segments as c(K-1) ….(c +1)(K-1). We can see that neighboring segments share a comment element, and i =1 must exist within one segs. Also, ceil(N-1/k-1) such segs is enough to cover the whole array.

3. Therefore, we just start with the seg A[i] = 1 in, and expand to both sides

arc099_b: Snuke Numbers

I had problem proving my insights during the contest!!!

1. Because each N we find is the new mean, the N/S(N) ratios are actually increasing as K increases

2. Therefore, to iterate, we can just calculate F(N) = M, M is the the smallest # > N that yields min M/S(M), and then assign N = F(N)

Claim: the suffix of M’s must end with 9s - may be multiple though.

Proof:

a. Because M > N, from left to right there must exists a digit where M(i) > N(i). We can move some of the delta, to make first right to left non-9 to 9.

b. Thus, M/S(M) got reduced, we can repeat, until we can procceed

Therefore, the format of M is {prefix of N}{a single digit >= N[i]}{9s}. Given that each step we have at most 15 digits, we can just brute force search and find the min M/S(M) in the search space

2PC

• 2PC assumes that data in stable storage is never lost. No node cashes forever
• Classic 2PC blocks when a machine fails - it locks the object down for further changes, until at the commit
• One we pass the prepare stage, we know the exeuction result will be all commited

TCC

• Try: reserve resources
• Confirm: execute without checking, idempotent. Note that txns other than the one from main service can be executed asyncly
• Cancel: cancel the execution, release resources done by the try. Idempotent. Note that txns other than the one from main service can be executed asyncly

Saga

P2p distributed saga

• The Order Service creates an Order in a PENDING state and publishes an OrderCreated event to Cutomser Service
• The Customer Service receives the event attempts to reserve credit for that Order. It publishes either a Credit Reserved event or a CreditLimitExceeded event to Order Service
• The Order Service receives the event and changes the state of the order to either approved or cancelled

Centralized coordinator saga

1. The Order Service creates an Order in a pending state and creates a CreateOrderSaga
2. The CreateOrderSaga sends a ReserveCredit command to the Customer Service
3. The Customer Service attempts to reserve credit for that Order and sends back a reply
4. The CreateOrderSaga receives the reply and sends either an ApproveOrder or RejectOrder command to the Order Service
5. The Order Service changes the state of the order to either approved or cancelled
6. Note that even in centralized case, steps are performed IN ORDER instead of parallel

Saga’s isolation problem

Lost update - commited txn change got overwritten

1. T1 creates order
2. T2 cancels order
3. T1 approves the order - without proper check, T2’s change can be ignored! That is, need domain logic to handle when when we are approving the order that is already cancelled

Similarly, during compesntation, the previous result of do is no longer there because of another txn.

Dirty Read - Read uncommited changes

1. T1 reserves credits
2. T2 reserves credits, before parent txn of T1 commits

Non-repeatable read - read twice within the same txn. Got different results

Scenario:

1. T1 creates order
2. T2 updates order
3. T1 tries to finalize order , but find the state changes already!

• To defend against isolation problems above
• need to have communtative updates between try and compensate, or re-read value
• mark the OOO try as rollback only - can not execute
• txn should have a globally unique id
• In traditional DB, read committed isolation level can prevent it
• In distributed, we can again use a semantics lock, although need to also introduce timeout + random slacked retry to prevent possible deadlock
• Domain logic should get money first before giving money to reduce the loss if compenstation failed due to concurrency

TCC vs saga

1. try vs direct
2. in sequence vs parallel
3. compenstation order
4. For user POV, TCC offers better consistency, because try stage will reduce the likelihood of user seeing partial results. However, partial results cases can always constructed due to the nature of eventual consistency

1. Minimum: 30 mins every two weeks. Try best to stick with plan, and mentally prepared for that.
   • If you can’t handle it, it is a sign the team is too big. 7 +/- 3 people seems to be the sweet spot.
2. Don’t ask “How are things?” - you should know this through normal standups. Instead, focus on
   • Company direction
   • Career development/path of growth - and follow up before the next review cycle
   • Conflict resolution
   • Constructive feedback
3. Spent first 10 mins to discuss company-team wise issues, to pass the context down to the team
4. After that, Give feedback on performance and their individual goals. Your people are hungry to know how they’re doing
5. Leave the end chunk to questions and discussions. Very likely you don’t have answers to questions on the spot - take notes and follow up later
6. May consider walking meeting to help relaxation.
7. Stare into people’s eye and ask “Are you bored?”.
   • Dig deep until they are able to look into your eyes too. Goal is to discover problem before they even realize it
   • “I don’t know what to do next” is a common sign of boredom
   • It’s the job of every manager to help with the flow of information up and down the organization. When people express frustration with leadership, it’s usually due to a failure in that flow.
   • stay silent for 10 seconds to see if the other side can pursue you or open up. In fact, you should try to stay silence as much as you can
   • The simple act of listening to someone bitch is often all you need to do. Let the fury pass. View it as the oppurtinity to let the other part organize their thoughts - People want to be heard
     • But do NOT join the bitching
     • Start the triage only after the steam is off

On diffcult talk

• Positive visioning. Before the conversation, think about your ideal outcome. It’s very possible that the conversation will go much better than you initially thought.
• Create talking points at least one night before - you want to avoid monologue. Review the points with another neutral person
• SLOW DOWN. Disengage after one becomes defensive
• Look at the person’s face!
• Tell the person why you are disappointed and how you feel, but reaffirm the person they are better than this and gives actionalbe items
• When commenting, compare with the same person’s previous product, to cushion the shocks

References

• From Hired

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