leetcode

An online judge to practise interview problems. Most of them are nontrivial.

In one of the problems I need to use dp to remember vector >
so I end up having some awkward thing like vector

Using typedef saves a few key strokes, but what is a good way to write such things?

github notes

If you want read/write access to repo, use ssh link.

To clone a project:

cd ~/.ssh && ssh-keygen
cat id_rsa.pub | xclip 
git clone

git init

git remote add some_name_in_remote.git
git add files
git push


git branch

codechef September short

Carvans	CARVANS	1093	39
Coal Scam	COALSCAM	138	24.35
Prime Permutations	PPERM	155	19.58
Pizza Tossing	PTOSS	12	14.81
Recipe Reconstruction	RRECIPE	769	35.21

Carvans: keep track of the slowest car before you.

Coal Scam: Two phase of Kruskal's, the key is to prove that ties can be broken arbitrarily. For implementation, since M is only 20000, even the O(n) union-find implementation will work. For quick union-find, either union by size or union by rank is fast. I had another terrible mistake for not noticing nodes are given as 0 to N-1, while I thought it was 1 to N. This caused id[0] not to get reinitialized between testcases.

Prime Permutation: To count, notice that after you placed 1 to N-1, inserting N to anywhere does not affect whether the first N-1 numbers are in a valid position or not, since their rank does not change. So you only need to place N at 1 or a prime position. My mistake is only calculate cnt[] to 5000000-1, and got a WA.

Recipe Reconstruction: since it has to be palindrome, you can match char by char from both ends. The tricky part is that 10000000+9 = 23 * 434783 which is NOT a prime. So you need Chinese Remainder's Theorem (CRT) to calculate the mod.

Side note: to verify my solution after seeing editorial for PPerm, I wrote a bash for loop to write 1 to 5000000 to a file. This takes about 6m30s. Running the c++ code read in the file and do all the calculations and write to another file takes less than 2s.

Vertex Cover in bipartite graph

Vertex cover reduces to matching and flow when the input is a bipartite graph.

First the unweighted case, that is, we want the minimum cardinality vertex cover.

Konig's theorem says size(VC) = size(M) where VC is a minimum vertex cover and M is a maximum matching.

Quick proof: The direction M >= VC is easy since at least one of the two endpoints in M has to appear in VC. The other direction, M <= VC is proved by providing an algorithm that constructs VC from M.

Suppose we have a matching M now. We have a simple observation, if v in L is matched to w in R, then at most one of v and w can have an unmatched neighbor, otherwise we can augment. A stronger version is that an alternating path start with an unmatched vertex must end at a matched vertex.

The algorithm: start from every unmatched vertex on the left L, do dfs/bfs to reach other vertices in L and R. Let L1 and R1 be set of matched vertices. From L to R we use E-M, from R to L we use M. Let the hit vertices in L be L0 and those in R be R0, the answer is L1-L0 + R0. Intuitively we need all v in R0 to cover all unmatched vertices in L, as well as v in L0. Given the observation we had before, no vertex in L0 can have an edge with an unmatched vertex in R. So edges involving all unmatched vertices in R is covered by L1-L0. Edges involving R1-R0 are covered by L1-L0 because none of them is reachable from L0 when we do dfs. Edges involving R0 are covered by R0 of course. That way we have covered all edges with endpoints in R, namely unmatched vertices, R0 and R1-R0.

The weighted version involves a reduction to min-cut. The graph is constructed by adding s and t, s has edge w(e) = w(v) for each v in L, and each v in R has an edge to t with w(e) = w(v). Each edge from v1 in L to v2 in R has inf capacity. Now a mincut is a min VC.

First observe that a trivial cut is to have s by itself and the weight is finite. So a mincut cannot have an inf edge. Suppose we have a VC = L1 + R1, then our cut is s + L - L1 + R1. The cost of VC is w(L1) + w(R1) and the cost of cut is also w(L1) + w(R1). Conversely, if we have a cut with finite capacity, let the cut assign L1 to s, where L1 is a subset of L, then all vertices in R, call it R1, with an inf edge with L1 must also belong to s. Hence we have L-L1 + R1 being a vertex cover with the same weight.

The algorithm is thus solving the mincut problem with max-flow-min-cut algorithm, then those reachable from s in R and those not reachable from s in L form VC.

Software engineering principles

Things I learned from google, or some google engineer.

Look for sound design and code readability (this is more than small things like indentation, but the overall structure)

Do not compromise quality.

SRM 556 another setback

First I am not very careful indeed.

p250 is easy, just recognize that you need to explore all possible states
dp[n][val], n is at most 50 and val is at most 1023
each (k, v) can lead to at most n new states.
For some reason I thought you only need dp[n], and the challenge follows.

p500 is not hard either. This is one of the few p500 problems that I got the idea pretty quickly. The reason I was not able to finish is:
1. I wrote too much python recently and keep using string str = "" + a[i] + tmp;
C++ does not understand what I am doing.
2. I didn't spend enough time to figure out the base case and my dp implementation is rather messy.

Given over 60min on p500 and I still could not get close enough to a working implementation. Quite disappointed with myself.

One more note, if you get SIGKILL in tc arena, you are using too much memory. string dp[55][55][55][55]; is too much, for example.

TODO this weekend

read FFT in Dasgupta.

Write facility location.

SRM on Friday.

two problems about RSA

1. Given e, d and N, can you find p and q?
2. if alice send the same message M to three different people, that is, if you have M^e1, M^e2 and M^e3, and N1, N2, N3, can you recover M?

problem 1 involves deep number theory.

problem 2 can be solved using chinese remainder's theorem, assuming N1, N2 and N3 are relatively prime.