Codeforces Round #360 (Div. 1) - B. Remainders Game

Problem Statement:
http://codeforces.com/contest/687/problem/B

Summary:
Given integer n, k < 1M, and n numbers c[1], ..., c[n] < 1M, decide whether we can always guess for all unknown integer x, what x mod k is if x mod c[i] is known for all i.

Codeforces 547C - Mike and Foam

Problem Statement:
547C - Mike and Foam

Solution:
The most important observation: since \( a_i <= 5 \times 10^5 \), the maximum number of distinct prime factors \(a_i\) can have is 6, since \(2 \times 3 \times 5 \times 7 \times 11 \times 13 = 30030 < 5 \times 10^5\) while \( 2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 = 510510 > 5 \times 10^5 \). This allows us to perform a fundamental counting principle called inclusion-exclusion principle.

Codeforces Round #295 (Div. 1 C / Div. 2 E) - Pluses everywhere

Problem Statement:
521C - Pluses everywhere

Solution:
Let's start from what we know and concretely find out what we don't know.

Let d[1..n] be the digits on the number that is given to us. Focus on d[i..j] for some i, j. We know exactly how many times it will appear by simple combinatorics deduction: there are \(n-1\) spaces to place '+' signs in between d[1], d[2], ..., d[n], but d[i..j] should not have any plus signs inside, which eliminates \(j-i\) candidates to place the sign, and finally we must place a sign right before d[i] and right after d[j], hence eliminating further 2 places, which gives us \( n-1-(j-i)-2 \) places to choose from. Furthermore, since we must use two plus signs to define d[i..j], we are left with k-2 plus signs to place. Hence in total, d[i..j] appears \({{n-1-(j-i)-2} \choose  {k-2}} \) times in the summations. Let's call this value M(i,j), the "multiplier" of d[i..j]. By the way, notice that we may also have cases where \(i = 1\) or \(j = n\) in which we only need to use a sign to define d[i..j], hence the computations will differ slightly, but can be computed precisely.

Codeforces Round #290 (Div. 1 C / Div. 2 E) - Fox and Dinner

Problem Statement:
512C - Fox and Dinner

Solution:
I've always been fascinated with maximum flow problems. The author to this problem is brilliant, and his official editorial is very well written, succinct and sweet. This post is mostly for my future reference, but feel free to read through the discussion :)

We can certainly identify that this problem is a matching problem, but what exactly is the type of matching we are interested in? On the first glance it seems to require some notion of tables, in which each table must contain at least 3 elements. That sounds like a random constraint, but as it turns out, a pretty fundamental observation to this problem can leads to a very clever representation of the problem that can easily enforce the constraints described in the problem statement.

Codeforces Round #287 Problem D - The Maths Lecture

Problem Statement:
507D - The Maths Lecture

Solution:
An insightful use of dynamic programmings in number theoretic combinatorics...

The idea is for each length i, we wan to compute how many y with length i are there such that it is exactly divisible by k. Hence for each y with length i, digit 0-9 can be padded in front of y to form x. However, we do not want any y to be a suffix of another y, as it will lead to double counting of x. How should we approach the problem?

Codeforces Round 284 Div.1 Problem D - Traffic Jams in the Land

Problem Statement:
498D - Traffic Jams in the Land

Solution:
This problem abuses segment tree so bad :)

The idea is to build 60 (which is gcd of 2,3,4,5,6) segment trees, each segment tree i answers the particular query: what is the time needed to pass through roads in [L..R] given that I start at time T = i mod 60. As such, we can serve all queries in \(O(N\lg{N})\) time. The hardest part is of course to implement the trees (or plant the forest).

a bit of number theory: Notes on Number Theory

Mostly a side note for myself, but might be useful for anyone.

Bezout's Identity (or its equivalence): Given \(a, b \in \mathbb{Z}^+\). Let \(d \in  S = \{ ax+by | ax+by > 0, \text{and} x,y \in \mathbb{Z}\} \) is the smallest element in that set. Then \(\text{gcd}(a,b) = d\).
Proof:
Firstly, note that \(\text{gcd}(a,b) \leq d\). Proof: Suppose that  \(\text{gcd}(a,b) = D > d\). Since \(ax+by = d\), then \(D|ax+by\) implies that \(D|d\), which implies \(D \leq d\), contradiction. (shown)

Next, we can write \(a = qd + r\) where \(0 \leq r < d\) (Can be proven formally), then
\( r = a - qd \)
\( r = a - q(ax+by)\)
\( r = a(1 - qx) + b(-qy)\)
\( r = ax' + by' \)
This implies that if \(r \not= 0\), then \(r \in S\) and hence \(r \geq d\), which contradicts the fact that \( r < d\). Therefore \(r\) must be 0, which means that \(a\) is divisible by \(d\).

With analogous reasoning, we can conclude that \(b\) must also be divisible by \(d\). Hence \(\text{gcd}(a,b) \geq d\). Therefore we have \(d \geq \text{gcd}(a,b) \geq d\), and the proof follows.

Euclid's Lemma:  If \(p | ab\), then \(p | a\) or \(p | b\).
Proof:
If \(p|a\), then the the proposition trivially holds. Hence assume that \(p \nmid a\), then by Bezout's Identity, we have
\(ax + py = 1\) (since \(\text{gcd}(a,p) = 1\) by definition)
\((ab)x + (pb)y = b\)
Notice that \(\text{LHS}\) is divisible by \(p\). This means that \(\text{RHS}\) must also be divisible by \(p\). Hence the proof is complete.

Corollary 1: contrapositive of Euclid's Lemma: If \(p \nmid a\) and \(p \nmid b\), then \(p \nmid ab\).
Corollary 2: Fundamental Theorem of Arithmetic: All positive integers can be uniquely represented by multiplication of prime numbers. (Haha not so corollary actually, but yeah)

Lemma 1: Suppose \(P,A\) are some relatively prime integers. Then if \(AN \equiv AM \mod{P}\) then \(N \equiv M \mod{P}\).

Proof: We have \(AN - AM \equiv 0 \mod{P}\), hence \(P | A(N-M)\). Then \(P | N-M\), which means that \(N-M \equiv 0 \mod{P}\), or equivalently \(N \equiv M\mod{P}\), and the proof follows.

Lemma 2: The ordered set \(S =\{ 0, A, 2A, 3A, \ldots ,(P-1)A \mod{P} \}\) is a permutation of \(T = \{0,1,2,3,\ldots, P-1 \}\).

Proof: (by contradiction) suppose that \(S\) is not a permutation of \(T\), then there must exist \(a_i, a_j \in S\) with \(i \not= j\) such that \(a_i = a_j\). This means that there exist \(N \not= M\) such that \(AN \equiv AM \mod{P}\), which contradicts Lemma 1. Hence \(S\) must be a permutation in the first place.

Existence and Uniqueness of Inversion:  We denote \(a^{-1}\) be the inverse of \(a\) such that \(a \cdot a^{-1} \equiv 1 \mod{N}\). Then for \(a,N\) relatively prime, there always exist a unique inverse of \(a\).
Proof:
Following Bezout's Identity, there exist some \((x,y) \in \mathbb{Z}^2\) such that \(ax+Ny=1\). Taking \(\mod{N}\) on each side, we have \(ax \equiv 1 \mod{N}\). Therefore \(x = a^{-1}\) is an inverse of \(a\). Now, the uniqueness of \(a^{-1}\) follows from Lemma 1.

Wilson's Theorem: \(N\) is prime if and only if \((N-1)! = -1 \mod{N}\)

Proof:
Forward Direction:
Firstly, we need to proof the following claim:
Claim 1: For a prime \(P\) and \(x \in \{1,2,\ldots,P-1\}\) \(x^2 \equiv 1 \mod{P}\) if and only if \(x = 1\) or \(x = P-1\).
Proof:
If \(x \not= 1,P-1\), then we have \(x^2 -1 = (x-1)(x+1) \equiv 0 \mod{P}\). This implies that \(P | (x-1)\) or \(P|(x+1)\) (By Euclid's Lemma), which leads to \(x = 1, P-1\), contradiction.

Now by Existence and Uniqueness of Inversion, for each \(i \in S = \{2,3,\ldots, N-2\}\) there exist a unique \(j \in S\) such that \(ij \equiv 1 \mod{N}\). Hence \(2 \cdot 3 \cdot 4 \cdot \ldots \cdot N-2 \equiv 1 \mod{N}\). Lastly, \(1 \cdot (N-1) \equiv -1 \mod{N}\), therefore combining both products completes the forward proof.

Backward Proof:
Suppose for contradiction that \(N\) is composite which satisfies \((N-1)! \equiv -1 \mod{N}\). Since \(N\) is composite, there is \(1\leq q < N\) such that \(q | N\). since \((N-1)! = aN-1\) for some \(a \in \mathbb{Z}\), we have \( (N-1)! = aN-1 \equiv -1 \mod{q}\). However, \( (N-1)! \) is also \( 0 \mod{q}\), hence a contradiction, and therefore \(N\) must be a prime. (shown)

a bit of number theory: Greatest Common Divisor

We'll discuss one of the most ancient algorithm in the history of Number Theory. 

Problem Statement:
Given two positive integers \( M\) and \(N\), find the greatest integer \(D\) such that \(D\) divides both \(M\) and \(N\).

In case you have forgotten, here are a few examples:

• for \(M=10\), \(N=55\), the greatest common divisor \(D\) is \( 5\)
• for \(M=72\), \(N=64\), the greatest common divisor \(D\) is \( 8\)

For small \( (M,N) \), \(D\) can usually be easily found by trial and error (and sometimes by terror), but for large values of \( (M,N) \), while trying all integers less than M and N might work, it can be really slow and certainly we can do better than this.

An efficient algorithm to solve this problem hinges on the following observation:
Theorem 1:
For positive integers \(a,b,d\), if \(d\mid a\) and \(d \mid b\), then \(d\mid ax+by\) for any \(x,y \in \mathbb{Z}\).

Proof:
Directly substituting \(a = kd\) and \(b = ld\) shows that the claim indeed holds. \(\blacksquare\)

With this, we can devise an efficient algorithm due to Euclid:

Euclid(M,N)
Input: M,N are integers, \(M\geq N\)
Output: integer D, the greatest common divisor of M and N
Pseudo-code:
if \(N\)==0:
   return \(M\)
return Euclid(\(N\), \(M \pmod{N}\))

Convince yourself that this algorithm works.
Euclid(M,N) eventually terminates with \( D = xM + yN\) for some \(x,y\in \mathbb{Z}\).
We will prove that it indeed returns the greatest common divisor of M and N.

Theorem 2:
Given integers \(d,x,y,a,b\), if \(d = ax + by\) and \(d\) divides both \(a\) and \(b\), then \(d\) is the greatest common divisor of \(a\) and \(b\).

Proof:
Suppose that \(d\) is not the greatest common divisor of \(a\) and \(b\). Hence there is \(D\) where \(D > d\) such that \(D\) divides both \(a\) and \(b\). By Theorem 1, \(D \mid ax + by = d\), which implies that \(D \leq d\), a contradiction. Hence \(d\) must be the greatest common divisor of \(a\) and \(b\). \(\blacksquare\)

Finally, what is the running time of Euclid(M,N)? It is guaranteed that Euclid(M,N) will terminate after \(O(\log{N})\) recursive calls since each call reduces the size of either M or N by half, with each call performs a modular arithmetic which can be done in constant time. The claim below explains the upper bound to the recursive call.

Claim:
If \(M \geq N\), then \(M \pmod{N} < \frac{M}{2}\) 

Proof:
\(N\) can be either bigger or less than \(\frac{M}{2}\), so we have 2 cases to consider:
Case 1: \(N \leq \frac{M}{2}\)
Then we know for a fact that \(M \pmod{N} < N \leq \frac{M}{2}\).
Case 2: \(N > \frac{M}{2}\)
Here we have \( M \pmod{N} \equiv M-N \pmod{N}\) and since \(M-N < M - \frac{M}{2} = \frac{M}{2} < N\) we have \(M \pmod{N} = M-N < \frac{M}{2}\). \(\blacksquare\)

Here is an implementation in C:

/* Recursive greatest common divisor */
int gcd(int M, int N){
   if (N>M) return gcd(N, M);
   if (N==0) return M;
   return gcd(N, M%N);
}