Problem Statement:
Codeforces Round #356 (Div. 2) D. Bear and Tower of Cubes
Summary:
Given m < 10^15, find the largest (k, X) such that a[1]+a[2]+...+a[k] = X <= m, each a[i] is a perfect cube, and for a given X, a[i] is the largest cube such that a[1] + ... + a[i] <= X.
Showing posts with label Algorithm. Show all posts
Showing posts with label Algorithm. Show all posts
Sunday, June 12, 2016
Saturday, November 8, 2014
Codeforces #276 (Div. 1) Problem C: Strange Sorting
Problem Statement:
484C - Strange Sorting
Solution:
This is an awesome problem. Good stuff.
The first thing to notice is that that the length of string n and the number of queries is bounded by \(nm \leq 10^6\). What happens if \(n = 10^6\)? In this case for \(K\) large enough, the running time of pure simulation of the operations will take too much time.
The great idea that is suggested by the problem setter (Codeforces handle: Bugman. You are awesome) is to think of each sorting operations as permutations on the string, which it indeed is. The good thing about permutation is that we can represent it in an NxN elementary matrix (which only has one "1" in each rows and each columns, and "0" everywhere else). Let's call this permutation matrix as P. Then each shuffling operations can be seen as matrix multiplications of S and \(P^n\). So if we can find a matrix P to represent the d-sorting on S at different substring of S, we can proceed with doing a fast matrix multiplication of \(P^n\) which takes \(O(N\lg{n})\), which also marks the bound for the running time of each query (Btw, the matrix multiplication itself in general is \(O(N^3)\), but since the matrices multiplied are elementary, we only need \(O(N)\) time, and it is quite fun to figure out how to do it :D).
484C - Strange Sorting
Solution:
This is an awesome problem. Good stuff.
The first thing to notice is that that the length of string n and the number of queries is bounded by \(nm \leq 10^6\). What happens if \(n = 10^6\)? In this case for \(K\) large enough, the running time of pure simulation of the operations will take too much time.
The great idea that is suggested by the problem setter (Codeforces handle: Bugman. You are awesome) is to think of each sorting operations as permutations on the string, which it indeed is. The good thing about permutation is that we can represent it in an NxN elementary matrix (which only has one "1" in each rows and each columns, and "0" everywhere else). Let's call this permutation matrix as P. Then each shuffling operations can be seen as matrix multiplications of S and \(P^n\). So if we can find a matrix P to represent the d-sorting on S at different substring of S, we can proceed with doing a fast matrix multiplication of \(P^n\) which takes \(O(N\lg{n})\), which also marks the bound for the running time of each query (Btw, the matrix multiplication itself in general is \(O(N^3)\), but since the matrices multiplied are elementary, we only need \(O(N)\) time, and it is quite fun to figure out how to do it :D).
Friday, October 24, 2014
TopCoder SRM 637
Division 1
Problem 250:
SRM 637 Div1 (250) - GreaterGame
Solution:
To find the expectation, first sort the cards on each hand. Then for each of the known Sothe's card, we can determine whether we want to top the card with the lowest possible card on our hand, or just lose with the lowest possible card. Each of the card that we topped will contribute to the expectation by 1, and those we lose contribute 0. Then we will end up with the cards that Sothe did not reveal, and the cards that we do not used yet. For each card on our hand, we find the probability of our card winning given the knowledge of Sothe's remaining cards. Each of the probability contributes to our expectation. Hence we just sum up all the probabilities with the number of the cards that we won earlier on.
Problem 250:
SRM 637 Div1 (250) - GreaterGame
Solution:
To find the expectation, first sort the cards on each hand. Then for each of the known Sothe's card, we can determine whether we want to top the card with the lowest possible card on our hand, or just lose with the lowest possible card. Each of the card that we topped will contribute to the expectation by 1, and those we lose contribute 0. Then we will end up with the cards that Sothe did not reveal, and the cards that we do not used yet. For each card on our hand, we find the probability of our card winning given the knowledge of Sothe's remaining cards. Each of the probability contributes to our expectation. Hence we just sum up all the probabilities with the number of the cards that we won earlier on.
Tuesday, October 21, 2014
Ray Casting Trial
Today I spent almost the whole (haha) debugging my implementation of ray casting on Javascript. Ray casting is a technique used by game developers in the past to create a 3D feeling games on a 2D graphics, which in my opinion is very clever. It uses a 2D array to represent the whole 3D world. After implementing the technique, I am pretty amazed by the end result! Here is the link to the code I just wrote: Ray Casting on HTML5 Canvas
Sunday, September 28, 2014
a bit of matrix: LUP Decomposition
Scratch note:
Given system of linear equation \(Ax = b\), solve for \(x\).
One of the method to solve this classic linear algebra is described here called "LUP decomposition". LUP is itself an abbreviation for Lower, Upper, and Permutation Matrixes. The idea is that in a Gauss Elimination process, we are actually trying to transform a matrix into its row equivalent upper or lower triangular matrix. The method here owes to the insight from Gauss Elimination.
Recursively:
1. We swap the first row in \(A\) with another row such that the first element in \(A\) is not zero. Call this permutation \(Q\), and hence the resulting matrix \(QA\).
2. Rewrite QA as
\( \left(
\begin{array}{cc}
1 & 0 \\
v/a_{k1} & I_{n-1}
\end{array}
\right)
\left(
\begin{array}{cc}
a_{k1} & w^T \\
0 & A - vw^T/a_{k1}
\end{array}
\right)
\)
3. Let \(P =
\left(
\begin{array}{cc}
1 & 0 \\
0 & P'
\end{array}
\right)
Q
\)
Where \(P'(A-vw^T/a_{k1})=L'U'\)
Hence we have
\(PA =
\left(
\begin{array}{cc}
1 & 0 \\
0 & P'
\end{array}
\right)
\left(
\begin{array}{cc}
1 & 0 \\
v/a_{k1} & I_{n-1}
\end{array}
\right)
\left(
\begin{array}{cc}
a_{k1} & w^T \\
0 & A - vw^T/a_{k1}
\end{array}
\right)
\)
which simplifies to
\(PA =
\left(
\begin{array}{cc}
1 & 0 \\
v/a_{k1} & L'
\end{array}
\right)
\left(
\begin{array}{cc}
a_{k1} & w^T \\
0 & U'
\end{array}
\right)
\)
Or \(PA = LU\)
Given system of linear equation \(Ax = b\), solve for \(x\).
One of the method to solve this classic linear algebra is described here called "LUP decomposition". LUP is itself an abbreviation for Lower, Upper, and Permutation Matrixes. The idea is that in a Gauss Elimination process, we are actually trying to transform a matrix into its row equivalent upper or lower triangular matrix. The method here owes to the insight from Gauss Elimination.
Recursively:
1. We swap the first row in \(A\) with another row such that the first element in \(A\) is not zero. Call this permutation \(Q\), and hence the resulting matrix \(QA\).
2. Rewrite QA as
\( \left(
\begin{array}{cc}
1 & 0 \\
v/a_{k1} & I_{n-1}
\end{array}
\right)
\left(
\begin{array}{cc}
a_{k1} & w^T \\
0 & A - vw^T/a_{k1}
\end{array}
\right)
\)
3. Let \(P =
\left(
\begin{array}{cc}
1 & 0 \\
0 & P'
\end{array}
\right)
Q
\)
Where \(P'(A-vw^T/a_{k1})=L'U'\)
Hence we have
\(PA =
\left(
\begin{array}{cc}
1 & 0 \\
0 & P'
\end{array}
\right)
\left(
\begin{array}{cc}
1 & 0 \\
v/a_{k1} & I_{n-1}
\end{array}
\right)
\left(
\begin{array}{cc}
a_{k1} & w^T \\
0 & A - vw^T/a_{k1}
\end{array}
\right)
\)
which simplifies to
\(PA =
\left(
\begin{array}{cc}
1 & 0 \\
v/a_{k1} & L'
\end{array}
\right)
\left(
\begin{array}{cc}
a_{k1} & w^T \\
0 & U'
\end{array}
\right)
\)
Or \(PA = LU\)
Monday, September 22, 2014
a bit of greedy: UVa 10670 - Work Reduction
Problem Statement:
UVa 10670 - Work Reduction
Summary:
We want to transform an integer N into integer M. Then we are given 2 operations:
1. \( N \mapsto N-1\), with cost \(A\)
2. \( N \mapsto \frac{N}{2} \) (round down), with cost \(B\)
What is the lowest cost?
Solution:
Naturally there is a greedy scheme to follow:
1. If we can divide by 2, take \(min \{ A \lceil \frac{N}{2} \rceil, B \} \)
2. If cannot, use operation 1 for the remaining steps
Proof?
I was exploring on the maths for a bit, for the case \(N = 2^k\) and \(2^{k-2} < M < 2^{k-1}\), I get this results...
Suppose we do a few operation 1 (\(x\) times) and then do operation 2. We will end up with \(2^k \mapsto 2^k-x \mapsto \lfloor \frac{2^k-x}{2} \rfloor\). Meanwhile, if we follow greedy scheme, we have \(2^k \mapsto 2^{k-1}\) instead. I will call the former "deviation" from greedy scheme. Then I observe that greedy scheme actually stays ahead of the deviation. If I take \( \lfloor \frac{2^k-x}{2} \rfloor \) as the "rendezvous" point, we have 2 costs:
By deviation: \(C' = xA + min \{ A \lceil \frac{2^k-x}{2} \rceil, B \} \)
By greedy scheme: \(C = min \{ 2^{k-1}A, B \} + x'A\) where \(2^{k-1}-x' = \lfloor \frac{2^k-x}{2} \rfloor \)
Now, if \(x\) even, we have \(x' = \frac{x}{2}\), while when \(x\) is odd, we have \(x' = \frac{x+1}{2}\). Hence we can say \(x' \geq \frac{x}{2}\), and also \(x \geq x' \) for all \(x \geq 1\).
We have to check the following cases:
Case 1: if \( A \lceil \frac{2^k-x}{2} \rceil > B \) and \(2^{k-1}A > B\)
Then \( C' = xA + B \geq x'A + B = C \). Hence greedy scheme is at least equal, and at best cost less than the deviation.
Case 2: if \( A \lceil \frac{2^k-x}{2} \rceil < B \) and \(2^{k-1}A > B\)
\(C' = xA + \lceil \frac{2^k-x}{2} \rceil A = xA + (2^k - x - 2^{k-1}+x')A\)
\(C' = x'A + A2^{k-1} > x'A + B = C\) again!
Case 3: if \( A \lceil \frac{2^k-x}{2} \rceil > B \) and \(2^{k-1}A < B\)
This is impossible by the love of God
Case 4: if\( A \lceil \frac{2^k-x}{2} \rceil < B \) and \(2^{k-1}A < B\)
then C = C' by simple algebra.
Yay then I can say that the greedy scheme actually stays ahead once there is a deviation from the scheme as we can always reach the state at at worst equal cost to the one resulting from the deviation :D
But for the case in general.. no idea yet
Now.. that's why people always ponder upon the paradox of why such a simple greedy algorithm can actually be so complicated.. A facade of all facades
UVa 10670 - Work Reduction
Summary:
We want to transform an integer N into integer M. Then we are given 2 operations:
1. \( N \mapsto N-1\), with cost \(A\)
2. \( N \mapsto \frac{N}{2} \) (round down), with cost \(B\)
What is the lowest cost?
Solution:
Naturally there is a greedy scheme to follow:
1. If we can divide by 2, take \(min \{ A \lceil \frac{N}{2} \rceil, B \} \)
2. If cannot, use operation 1 for the remaining steps
Proof?
I was exploring on the maths for a bit, for the case \(N = 2^k\) and \(2^{k-2} < M < 2^{k-1}\), I get this results...
Suppose we do a few operation 1 (\(x\) times) and then do operation 2. We will end up with \(2^k \mapsto 2^k-x \mapsto \lfloor \frac{2^k-x}{2} \rfloor\). Meanwhile, if we follow greedy scheme, we have \(2^k \mapsto 2^{k-1}\) instead. I will call the former "deviation" from greedy scheme. Then I observe that greedy scheme actually stays ahead of the deviation. If I take \( \lfloor \frac{2^k-x}{2} \rfloor \) as the "rendezvous" point, we have 2 costs:
By deviation: \(C' = xA + min \{ A \lceil \frac{2^k-x}{2} \rceil, B \} \)
By greedy scheme: \(C = min \{ 2^{k-1}A, B \} + x'A\) where \(2^{k-1}-x' = \lfloor \frac{2^k-x}{2} \rfloor \)
Now, if \(x\) even, we have \(x' = \frac{x}{2}\), while when \(x\) is odd, we have \(x' = \frac{x+1}{2}\). Hence we can say \(x' \geq \frac{x}{2}\), and also \(x \geq x' \) for all \(x \geq 1\).
We have to check the following cases:
Case 1: if \( A \lceil \frac{2^k-x}{2} \rceil > B \) and \(2^{k-1}A > B\)
Then \( C' = xA + B \geq x'A + B = C \). Hence greedy scheme is at least equal, and at best cost less than the deviation.
Case 2: if \( A \lceil \frac{2^k-x}{2} \rceil < B \) and \(2^{k-1}A > B\)
\(C' = xA + \lceil \frac{2^k-x}{2} \rceil A = xA + (2^k - x - 2^{k-1}+x')A\)
\(C' = x'A + A2^{k-1} > x'A + B = C\) again!
Case 3: if \( A \lceil \frac{2^k-x}{2} \rceil > B \) and \(2^{k-1}A < B\)
This is impossible by the love of God
Case 4: if\( A \lceil \frac{2^k-x}{2} \rceil < B \) and \(2^{k-1}A < B\)
then C = C' by simple algebra.
Yay then I can say that the greedy scheme actually stays ahead once there is a deviation from the scheme as we can always reach the state at at worst equal cost to the one resulting from the deviation :D
But for the case in general.. no idea yet
Now.. that's why people always ponder upon the paradox of why such a simple greedy algorithm can actually be so complicated.. A facade of all facades
Sunday, September 21, 2014
a bit of graph: A little note on Maximum Flow
This is a scrap note for Maximum Flow - Minimum Cut Algorithm for KIV purposes...
Terminology:
1. Capacity of an edge: \(c(u,v)\)
2. Flow : \(f\)
3. Residual Graph : \(G_f\)
4. Residual capacity : \(c_f(u,v) = c(u,v) - f(u,v)\)
5. Backedge : \(c_f(v,u) = f(u,v)\)
6. Flow Conservation: \(\sum_{u \in V} f(v,u) = \sum_{u\in V} f(u,v)\)
7. Max Flow - Min Cut Theorem: Finding maximum flow is equivalent to finding the minimum cut of the flow network.
Ford-Fulkerson Algorithm
Let \(P\) be a simple \(s-t\) path on the residual graph called the augmenting path. Let bottleneck(P) be the lowest valued edge in path \(P\) on the residual graph.
augment(f, P):
set b = bottleneck(P)
for (u,v) in P:
if u,v \(\in E\): \(f(u,v) = f(u,v) + b\)
else \(f(u,v) = f(u,v) - b\)
return b
Ford-Fulkerson(G,E):
Initialize \(G_f\), f = 0
while exist augmenting path \(P\):
f = f + augment(f, P)
return f
Bound: \(O(C|E|)\)
Using Edmonds-Karp Algorithm (BFS Implementation of Ford-Fulkerson), running time is pseudo-polynomial
Push-Relabel Algorithm:
Terminology:
1. height-function \(h(v)\)
2. preflow
3. excess flow (on overflowing vertex) \(e(v)\)
4. preflow property: on every vertex, in flow must be at least equals to out flow: \(\sum f(v,u) - \sum f(u,v) \geq 0\)
5. If \((u,v) \in E_f\), then \(h(u) \leq h(v) + 1\)
Push:
6. Can only push downhill: in particular, can only push on edge (u,v) if \(e(u) > 0\) (i.e. u is overflowing vertex) and \(h(u) = h(v)+1\)
push(u,v):
e = \(min \{ c_f(u,v), e(u) \} \)
if u,v \(\in E\): f(u,v) = f(u,v) + e
else f(v,u) = f(v,u) - e
e(u) = e(u) - e
e(v) = e(v) + e
7. Push is saturating iff (u,v) disappear from \(G_f\), otherwise unsaturating.
8. If saturating push, then \(u\) is no longer overflowing vertex.
Relabel:
9. Can only be performed on overflowing vertex, and only if push cannot be performed: for all \(u,v \in E_f\), \(h(u) < h(v) + 1\)
10. Since \(u\) is overflowing, it is always true that there is at least an edge \((u,v) \in E_f\).
relabel(u):
d = \(min_{(u,v) \in E_f} \{ h(v) \} \)
h(u) = d + 1
Push-Relabel(G,E):
Initialize \(f, h, e, G_f\) such that:
for all v, h(v) = 0, except source: h(s) = \(|V|\)
for all v, e(v) = 0.
for all (s,v) \in E:
f(s,v) = c(s,v)
e(v) = c(s,v)
e(s) = e(s) - c(s,v)
while can push or relabel:
push or relabel accordingly!
return the max flow f
Correctness: hinges on a lot of lemmas, a few important ones:
1. There is no s-t path in \(G_f\). Proof: by contradiction using height function property and a fact about a simple path.
2. Invariant: preflow property is always conserved. Hence if the algorithm terminates, that means we cannot push or relabel, hence there is no overflowing vertex anymore, which means the preflow is indeed the flow, and since no s-t path in \(G_f\), by Max Flow - Min Cut theorem the flow is max flow.
Run-time: \(O(V^2E)\), the proof is very elaborate.
Terminology:
1. Capacity of an edge: \(c(u,v)\)
2. Flow : \(f\)
3. Residual Graph : \(G_f\)
4. Residual capacity : \(c_f(u,v) = c(u,v) - f(u,v)\)
5. Backedge : \(c_f(v,u) = f(u,v)\)
6. Flow Conservation: \(\sum_{u \in V} f(v,u) = \sum_{u\in V} f(u,v)\)
7. Max Flow - Min Cut Theorem: Finding maximum flow is equivalent to finding the minimum cut of the flow network.
Ford-Fulkerson Algorithm
Let \(P\) be a simple \(s-t\) path on the residual graph called the augmenting path. Let bottleneck(P) be the lowest valued edge in path \(P\) on the residual graph.
augment(f, P):
set b = bottleneck(P)
for (u,v) in P:
if u,v \(\in E\): \(f(u,v) = f(u,v) + b\)
else \(f(u,v) = f(u,v) - b\)
return b
Ford-Fulkerson(G,E):
Initialize \(G_f\), f = 0
while exist augmenting path \(P\):
f = f + augment(f, P)
return f
Bound: \(O(C|E|)\)
Using Edmonds-Karp Algorithm (BFS Implementation of Ford-Fulkerson), running time is pseudo-polynomial
Push-Relabel Algorithm:
Terminology:
1. height-function \(h(v)\)
2. preflow
3. excess flow (on overflowing vertex) \(e(v)\)
4. preflow property: on every vertex, in flow must be at least equals to out flow: \(\sum f(v,u) - \sum f(u,v) \geq 0\)
5. If \((u,v) \in E_f\), then \(h(u) \leq h(v) + 1\)
Push:
6. Can only push downhill: in particular, can only push on edge (u,v) if \(e(u) > 0\) (i.e. u is overflowing vertex) and \(h(u) = h(v)+1\)
push(u,v):
e = \(min \{ c_f(u,v), e(u) \} \)
if u,v \(\in E\): f(u,v) = f(u,v) + e
else f(v,u) = f(v,u) - e
e(u) = e(u) - e
e(v) = e(v) + e
7. Push is saturating iff (u,v) disappear from \(G_f\), otherwise unsaturating.
8. If saturating push, then \(u\) is no longer overflowing vertex.
Relabel:
9. Can only be performed on overflowing vertex, and only if push cannot be performed: for all \(u,v \in E_f\), \(h(u) < h(v) + 1\)
10. Since \(u\) is overflowing, it is always true that there is at least an edge \((u,v) \in E_f\).
relabel(u):
d = \(min_{(u,v) \in E_f} \{ h(v) \} \)
h(u) = d + 1
Push-Relabel(G,E):
Initialize \(f, h, e, G_f\) such that:
for all v, h(v) = 0, except source: h(s) = \(|V|\)
for all v, e(v) = 0.
for all (s,v) \in E:
f(s,v) = c(s,v)
e(v) = c(s,v)
e(s) = e(s) - c(s,v)
while can push or relabel:
push or relabel accordingly!
return the max flow f
Correctness: hinges on a lot of lemmas, a few important ones:
1. There is no s-t path in \(G_f\). Proof: by contradiction using height function property and a fact about a simple path.
2. Invariant: preflow property is always conserved. Hence if the algorithm terminates, that means we cannot push or relabel, hence there is no overflowing vertex anymore, which means the preflow is indeed the flow, and since no s-t path in \(G_f\), by Max Flow - Min Cut theorem the flow is max flow.
Run-time: \(O(V^2E)\), the proof is very elaborate.
Monday, August 18, 2014
a bit of dp: UVa 10502 - Counting Rectangles
Problem Statement:
UVa 10502 - Counting Rectangles
Summary:
Given a square array A (made up of 0s and 1s) of dimension less than or equal to 100 x 100, find the number of rectangles formed by the 1s in the square.
Simple brute force approach with time complexity \(O(N^6)\) will lead to TLE since in worst case there are \( {100 \choose 2}^2 \) possibilities to check for, with \(O(N^2)\) checking time each. Hence we need to resort to a more clever strategy, and one that rings a bell is that of 2D array sum DP approach.
Let array S[100][100] be the array in which S[i][j] = \(\sum_{m=1}^i\sum_{n=1}^j\text{A[m][n]}\) (Or simply put, S[i][j] stores the sum of all elements of A which is inside the rectangle bounded by (1,1) and (i,j)). Having this array, we can easily find the sum of all elements in any rectangle in A in O(1) time. With this information, we can efficiently determine whether a rectangle is formed by 1s (since the sum of all elements of A in the rectangle will be equal to the area of the rectangle if the rectangle is fully filled with 1s). Therefore, the running time is reduced to \(O(N^4)\) which is still not bad for the problem. I suspect there is a more efficient algorithm to tackle this problem.
UVa 10502 - Counting Rectangles
Summary:
Given a square array A (made up of 0s and 1s) of dimension less than or equal to 100 x 100, find the number of rectangles formed by the 1s in the square.
Simple brute force approach with time complexity \(O(N^6)\) will lead to TLE since in worst case there are \( {100 \choose 2}^2 \) possibilities to check for, with \(O(N^2)\) checking time each. Hence we need to resort to a more clever strategy, and one that rings a bell is that of 2D array sum DP approach.
Let array S[100][100] be the array in which S[i][j] = \(\sum_{m=1}^i\sum_{n=1}^j\text{A[m][n]}\) (Or simply put, S[i][j] stores the sum of all elements of A which is inside the rectangle bounded by (1,1) and (i,j)). Having this array, we can easily find the sum of all elements in any rectangle in A in O(1) time. With this information, we can efficiently determine whether a rectangle is formed by 1s (since the sum of all elements of A in the rectangle will be equal to the area of the rectangle if the rectangle is fully filled with 1s). Therefore, the running time is reduced to \(O(N^4)\) which is still not bad for the problem. I suspect there is a more efficient algorithm to tackle this problem.
Wednesday, July 23, 2014
a bit of dp : Longest Increasing Subsequence
Given a sequence of number, find a subsequence (may not be consecutive) in the sequence such that the elements are strictly increasing.
Eg:
S = 2, -1, 3, -3, 1, 8, 9
Longest Subsequence: 2, 3, 8, 9
(2, -1, 3, -3, 1, 8, 9)
There are a lot of ways to do this. For small search space, we can do a complete search, but the complexity grows exponentially with incremental increase in search space.
Dynamic Programming can solve this problem in \(O(N^2)\) complexity, in which both top-down and bottom-up approach can work. Suppose that we are given \(|s_1|, |s_2|, \ldots, |s_k|\) where \(|s_k|\) is the length of the longest subsequence of the sequence \(a_1, a_2, \ldots, a_k\) which includes \(a_k\) as the last element of \(s_k\). Then to find \(s_{k+1}\), we go through all the list \(s_1, s_2, \ldots, s_k\), and we append \(a_{k+1}\) to \(s_i\) if and only if \(a_i < a_{k+1}\). Then \(s_{k+1}\) is the one with the maximum length.
Another approach is by using Binary Search (wow!). As we go through \(i = 1,2,3,\ldots, k\), we maintain an array of maximum lengths of subsequences we have seen so far, and we check if we build a longer subsequence using \(a_i\). If so, we add \(a_i\) to the array and continue. Otherwise, \(a_i\) is either equal to an element (say \(a_j\) in our array or smaller. Either case, we update the the array by replacing \(a_j\) with \(a_i\) since we can build a subsequence of equal length, but with a smaller last element. Using binary search, we can check for the above cases (whether \(a_i\) is bigger than all elements in our array or if there is such \(a_j\)) in \(O(\log{N})\) time. Overall, we can solve the problem in \(O(M\log{N})\) time.
As an example, UVa 481 - What Goes Up can be solved using binary search:
Eg:
S = 2, -1, 3, -3, 1, 8, 9
Longest Subsequence: 2, 3, 8, 9
(2, -1, 3, -3, 1, 8, 9)
There are a lot of ways to do this. For small search space, we can do a complete search, but the complexity grows exponentially with incremental increase in search space.
Dynamic Programming can solve this problem in \(O(N^2)\) complexity, in which both top-down and bottom-up approach can work. Suppose that we are given \(|s_1|, |s_2|, \ldots, |s_k|\) where \(|s_k|\) is the length of the longest subsequence of the sequence \(a_1, a_2, \ldots, a_k\) which includes \(a_k\) as the last element of \(s_k\). Then to find \(s_{k+1}\), we go through all the list \(s_1, s_2, \ldots, s_k\), and we append \(a_{k+1}\) to \(s_i\) if and only if \(a_i < a_{k+1}\). Then \(s_{k+1}\) is the one with the maximum length.
Another approach is by using Binary Search (wow!). As we go through \(i = 1,2,3,\ldots, k\), we maintain an array of maximum lengths of subsequences we have seen so far, and we check if we build a longer subsequence using \(a_i\). If so, we add \(a_i\) to the array and continue. Otherwise, \(a_i\) is either equal to an element (say \(a_j\) in our array or smaller. Either case, we update the the array by replacing \(a_j\) with \(a_i\) since we can build a subsequence of equal length, but with a smaller last element. Using binary search, we can check for the above cases (whether \(a_i\) is bigger than all elements in our array or if there is such \(a_j\)) in \(O(\log{N})\) time. Overall, we can solve the problem in \(O(M\log{N})\) time.
As an example, UVa 481 - What Goes Up can be solved using binary search:
#include <iostream> #include <cstdio> #include <vector> #include <algorithm> using namespace std; vector<int> par; vector<int> dp; vector<int> num; void printout(int idx){ if(idx == -1) return; printout(par[idx]); printf("%d\n", num[idx]); } int main(){ int N,cur=0; while(scanf("%d", &N) != EOF){ num.push_back(N); if(dp.empty()){ dp.push_back(cur); par.push_back(-1); ++cur; continue; } int lo = 0, hi = dp.size()-1, mid; while(lo <= hi){ mid = (hi+lo)/2; if(num[dp[mid]] < N){ lo = mid + 1; } else { hi = mid - 1; } } int it = lo; if(it == dp.size()){ par.push_back(dp[it-1]); dp.push_back(cur); } else { if(it > 0) par.push_back(dp[it-1]); else par.push_back(-1); dp[it] = cur; } ++cur; } cout << dp.size() << endl; printf("-\n"); printout(dp[dp.size()-1]); return 0; }
Tuesday, July 22, 2014
a bit of uva : UVa 11572 - Unique Snowflakes
Problem Statement:
UVa 11572 - Unique Snowflakes
Summary:
Find the maximum \(|i-j|\) such that for a sequence \(a_1,a_2,\ldots,a_n\), the subsequence \(a_i, a_{i+1}, \ldots, a_j\) has distinct elements.
I like this problem, because it allows you to think a bit and reward you with happiness and joy (haha wth I'm writing that for). Strategy: Suppose we already have a subsequence \(T = a_i, a_{i+1}, \ldots, a_j\). Upon deciding whether \(a_{j+1}\) can be added to this subsequence, we need a quick way to check whether the previous occurrence of \(v = a_{j+1}\) is before index i. Otherwise it's already in the subsequence, and therefore if there is a longer subsequence other than T, it must start after the occurrence of v in T (Proof by contradiction). By the end of this procedure, we will obtain the longest subsequence possible such that each element are all distinct.
There are various ways to get a fast look up for previous occurrences of an element: If \(a_i\) are small, a simple array for direct addressing table (DAT) suffices. Otherwise, a good hash table with expected O(1) or a map with O(log N) look-up time will do.
UVa 11572 - Unique Snowflakes
Summary:
Find the maximum \(|i-j|\) such that for a sequence \(a_1,a_2,\ldots,a_n\), the subsequence \(a_i, a_{i+1}, \ldots, a_j\) has distinct elements.
I like this problem, because it allows you to think a bit and reward you with happiness and joy (haha wth I'm writing that for). Strategy: Suppose we already have a subsequence \(T = a_i, a_{i+1}, \ldots, a_j\). Upon deciding whether \(a_{j+1}\) can be added to this subsequence, we need a quick way to check whether the previous occurrence of \(v = a_{j+1}\) is before index i. Otherwise it's already in the subsequence, and therefore if there is a longer subsequence other than T, it must start after the occurrence of v in T (Proof by contradiction). By the end of this procedure, we will obtain the longest subsequence possible such that each element are all distinct.
There are various ways to get a fast look up for previous occurrences of an element: If \(a_i\) are small, a simple array for direct addressing table (DAT) suffices. Otherwise, a good hash table with expected O(1) or a map with O(log N) look-up time will do.
Monday, July 21, 2014
a bit of algorithm: Binary Search Your Way!
I have come across a few interesting usage of binary search. As we all know, binary search is usually implemented to fast searching of a key/value in a sorted data structure. However, as not many of us are not aware of (or maybe not that many, but at least me) that there are many subtle or not so obvious uses of binary search for problem solving! Here I'll go through a few of them.
1. Root Finding
While many more efficient algorithms exist out there to find roots of a function, binary search can be regarded as the easiest to implement. The method itself is called "Bisection", which makes use of the following properties:
1. Intermediate Value Theorem: Given a continuous function \(f(x)\), we say that if there exist \(a,b\) such that \(f(a) \leq 0 \leq f(b)\), then we can find \(x \in [a,b]\) such that \(f(x) = 0\).
2. If \(f(a) * f(b) < 0\), then by part 1, \(x\) must be in between \(a\) and \(b\)
So to find a root, we need to:
1. Find 2 values a and b such that f(a) < 0 and f(b) > 0
2. Let \(c = \frac{a+b}{2}\). We check the following:
2.1 if f(a) * f(c) < 0, then \(x\) must be in between \(a\) and \(c\). So we set b = c and repeat 1.
2.2 else if f(a) * f(c) > 0, then x must be in between \(a\) and \(b\) instead. We set a = c and repeat 1.
Notice that the loop can go on forever since the algorithm converges quite slowly towards the exact root \(x\). In practice we repeat the process around N = 40 to 50 times to minimize the error to less than \(\frac{1}{2^{N}}\), small enough for many purposes and applications.
2. Guessing (Efficiently)
Sometimes if we know the search space of a problem beforehand, we can use binary search to "guess" the correct answer. However the problem must have the property such that if we know that our guess is not correct, we can determine quickly which side we should take to continue our search. One such problem can be illustrated in this UVa problem:
UVa 12032 - The Monkey and The Oiled Bamboo
The problem can be summarised to a few sentences: Given an array of values \({a_1,a_2,\ldots,a_N}\), find the smallest value \(K\) such that if we compare \(a_i\) with K sequentially from \(i = 1,2,3,\ldots,N\), \(K\) must always be at least \(a_i\), and if \(a_i\) is equal to \(K\), we decrease \(K\) by one and continue.
It may not be obvious that we can apply binary search to the problem, it sounds a lot like a DP problem to me. However, if we observe closely, we'll see that if \(K\) does not satisfy the requirements, \(K\) must be bigger, and vice versa. Hence we can guess for \(K\) using binary search over the search space of at most around \(10^7\), which can be handled pretty quickly by binary search.
There are many more applications of binary search that can be very interesting and subtle. It's always satisfying to notice such things :)
1. Root Finding
While many more efficient algorithms exist out there to find roots of a function, binary search can be regarded as the easiest to implement. The method itself is called "Bisection", which makes use of the following properties:
1. Intermediate Value Theorem: Given a continuous function \(f(x)\), we say that if there exist \(a,b\) such that \(f(a) \leq 0 \leq f(b)\), then we can find \(x \in [a,b]\) such that \(f(x) = 0\).
2. If \(f(a) * f(b) < 0\), then by part 1, \(x\) must be in between \(a\) and \(b\)
So to find a root, we need to:
1. Find 2 values a and b such that f(a) < 0 and f(b) > 0
2. Let \(c = \frac{a+b}{2}\). We check the following:
2.1 if f(a) * f(c) < 0, then \(x\) must be in between \(a\) and \(c\). So we set b = c and repeat 1.
2.2 else if f(a) * f(c) > 0, then x must be in between \(a\) and \(b\) instead. We set a = c and repeat 1.
Notice that the loop can go on forever since the algorithm converges quite slowly towards the exact root \(x\). In practice we repeat the process around N = 40 to 50 times to minimize the error to less than \(\frac{1}{2^{N}}\), small enough for many purposes and applications.
2. Guessing (Efficiently)
Sometimes if we know the search space of a problem beforehand, we can use binary search to "guess" the correct answer. However the problem must have the property such that if we know that our guess is not correct, we can determine quickly which side we should take to continue our search. One such problem can be illustrated in this UVa problem:
UVa 12032 - The Monkey and The Oiled Bamboo
The problem can be summarised to a few sentences: Given an array of values \({a_1,a_2,\ldots,a_N}\), find the smallest value \(K\) such that if we compare \(a_i\) with K sequentially from \(i = 1,2,3,\ldots,N\), \(K\) must always be at least \(a_i\), and if \(a_i\) is equal to \(K\), we decrease \(K\) by one and continue.
It may not be obvious that we can apply binary search to the problem, it sounds a lot like a DP problem to me. However, if we observe closely, we'll see that if \(K\) does not satisfy the requirements, \(K\) must be bigger, and vice versa. Hence we can guess for \(K\) using binary search over the search space of at most around \(10^7\), which can be handled pretty quickly by binary search.
There are many more applications of binary search that can be very interesting and subtle. It's always satisfying to notice such things :)
Friday, July 18, 2014
a bit of uva: Exclusion - Inclusion Principle (UVa 1047 - Zones)
I am just glad that finally I can solve this problem :)
Problem Statement:
UVa 1047 - Zones
The idea behind the problem is a principle in Set Theory called Exclusion-Inclusion Principle. When we have several sets intersecting one another, we have the following relationship:
\(A \cup B \cup C = (A + B + C) - ((A \cap B) + (B \cap C) + (A \cap C)) + (A \cap B \cap C) \)
The genius is that we can simply iterate through all combination of towers using bit manipulation. The code is much shorter than my first (wrong) attempt by using recursive set construction.
Code:
Problem Statement:
UVa 1047 - Zones
The idea behind the problem is a principle in Set Theory called Exclusion-Inclusion Principle. When we have several sets intersecting one another, we have the following relationship:
\(A \cup B \cup C = (A + B + C) - ((A \cap B) + (B \cap C) + (A \cap C)) + (A \cap B \cap C) \)
The genius is that we can simply iterate through all combination of towers using bit manipulation. The code is much shorter than my first (wrong) attempt by using recursive set construction.
Code:
#include <iostream> #include <cstdio> #include <utility> using namespace std; pair<int,int> common[15]; int tower[25]; int R,choice; int main(){ int P,T,M, tc=1; while(scanf("%d %d",&P,&T), P!=0 && T!=0){ choice = 0; R = -1; for(int i=0;i<P;++i){ scanf("%d",&tower[i]); } scanf("%d",&M); for(int m=0;m<M;++m){ int nM,key=0,val; scanf("%d",&nM); for(int i=0;i<nM;++i){ int j; scanf("%d", &j); key |= (1<<(j-1)); } scanf("%d",&val); common[m] = make_pair(key,val); } int lim = 1<<P; for(int i=0;i<lim;++i){ int k=0; for(int j=0; j<P;++j){ if(i & (1<<j)) ++k; } if(k != T) continue; int ret = 0; for(int j=0;j<P;++j){ if(i & (1<<j)){ ret += tower[j]; } } for(int j=0;j<M;++j){ int intersect = (common[j].first & i); int ctr=0; for(int c=0;c<P;++c){ if(intersect & (1<<c)) ++ctr; } if(ctr <= 1) continue; //count how many intersect, and substract accordingly ret -= (ctr-1)*common[j].second; } if(ret > R){ R = ret; choice = i; } else if( ret == R){ for(int j=0;j<P;++j){ int a = (i & (1<<j)); int b = (choice & (1<<j)); if(a != b){ if( a>0 ){ R = ret; choice = i; } break; } } } } printf("Case Number %d\n", tc++); printf("Number of Customers: %d\n", R); printf("Locations recommended:"); for(int i=0;i<P;++i){ if(choice & (1<<i)){ printf(" %d", i+1); } } printf("\n\n"); } return 0; }
Sunday, June 29, 2014
a bit of graph: Dijkstra's Shortest Path Algorithm
Problem Statement:
Given a undirected graph with non-negative weighted edges, a starting point s, and a destination t, find the path with minimum weight.
Dijkstra's Algorithm:
A greedy algorithm can be devised to solve this problem. Suppose we already have a minimum path using several nodes. Then the intuitive thing to do is to add a node to the last node in our path such that its weight is the lowest. This is basically the intuition behind Dijkstra's algorithm, which resembles Prim's algorithm for Minimum Spanning Tree. However, there are a few important details which ensure the correctness of the algorithm:
Definition:
s: starting point
t: destination
d[i]: array of distances from s
w(u,v): weigh of edge u to v
1. Initially, we have an array of distances d[i] which values are all infinity. This means that we do not know yet whether the node i is reachable from our starting point. However, we do know that s is reachable (since it's our starting point anyway) so d[s] = 0 and d[i] = INF for i != s.
2. For an edge with nodes u and v at its end points, an important operation called relax(u,v) is performed as follows: if d[u] > d[v] + w(u,v) then update d[u] = d[v] + w(u,v) (we can also say that the edge u-v is relaxed).
3. Let S be the set of nodes in which the distance from s has already known (that is, if u in S, then d[u] is guaranteed to be the total weight of the minimum path between s and u). At first, S = {s}. Then for each element in S, we examine its edges and perform the relax(u,v) operation.
4. After we have iterated through all element in S, we choose the node that is not yet inside S which has the smallest d[i], and add it in S (hence the greedy choice!). If the node happens to be t, then we've found d[t] which is the total weight of the minimum path from s (which is how we defined S earlier). If the node is not t, then repeat 3 until we cannot add anymore nodes into S in which case t is not reachable from s.
It remains to prove that in step 4, the node that we added to S indeed has the property that d[i] is the value of its minimum weight path from s, and the proof can be very interesting :D.
The implementation of this algorithm is usually done using a heap data structure such as priority queue to choose the minimum node in step 4, although a normal array can also be used if the number of nodes are not too big. Below is a sample implementation in C++:
Given a undirected graph with non-negative weighted edges, a starting point s, and a destination t, find the path with minimum weight.
Dijkstra's Algorithm:
A greedy algorithm can be devised to solve this problem. Suppose we already have a minimum path using several nodes. Then the intuitive thing to do is to add a node to the last node in our path such that its weight is the lowest. This is basically the intuition behind Dijkstra's algorithm, which resembles Prim's algorithm for Minimum Spanning Tree. However, there are a few important details which ensure the correctness of the algorithm:
Definition:
s: starting point
t: destination
d[i]: array of distances from s
w(u,v): weigh of edge u to v
1. Initially, we have an array of distances d[i] which values are all infinity. This means that we do not know yet whether the node i is reachable from our starting point. However, we do know that s is reachable (since it's our starting point anyway) so d[s] = 0 and d[i] = INF for i != s.
2. For an edge with nodes u and v at its end points, an important operation called relax(u,v) is performed as follows: if d[u] > d[v] + w(u,v) then update d[u] = d[v] + w(u,v) (we can also say that the edge u-v is relaxed).
3. Let S be the set of nodes in which the distance from s has already known (that is, if u in S, then d[u] is guaranteed to be the total weight of the minimum path between s and u). At first, S = {s}. Then for each element in S, we examine its edges and perform the relax(u,v) operation.
4. After we have iterated through all element in S, we choose the node that is not yet inside S which has the smallest d[i], and add it in S (hence the greedy choice!). If the node happens to be t, then we've found d[t] which is the total weight of the minimum path from s (which is how we defined S earlier). If the node is not t, then repeat 3 until we cannot add anymore nodes into S in which case t is not reachable from s.
It remains to prove that in step 4, the node that we added to S indeed has the property that d[i] is the value of its minimum weight path from s, and the proof can be very interesting :D.
The implementation of this algorithm is usually done using a heap data structure such as priority queue to choose the minimum node in step 4, although a normal array can also be used if the number of nodes are not too big. Below is a sample implementation in C++:
typedef pair<int, int> pii;
struct nd{
int v; //neighboring vertex
int w; //weight of edge u-v
};
vector<vector<nd> > G;
vector<int> p; //parent attr
vector<int> d; //dist attr
void init(int N){//no of nodes, no of edges
G = vector<vector<nd> >(N+1);
p = vector<int>(N+1);
d = vector<int>(N+1);
for(int i=0;i<N+1;++i)
p[i]=-1, d[i]=MAX;
}
void djikstra(int s, int f){ //starting pt
priority_queue<pii> q;
d[s]=0;
p[s]=-1;
q.push(make_pair(d[s] ,s));
while(!q.empty()){
pii cur = q.top();
q.pop();
int u = cur.second;
int nE = G[u].size();
for(int i=0;i<nE;++i){
int v = G[u][i].v;
int w = G[u][i].w;
if(d[v] > d[u] + w){
d[v] = d[u]+w;
p[v] = u;
q.push(make_pair(-d[v],v));
}
}
}
}
Monday, June 23, 2014
a bit of codechef: (June Cook-Off 2014) Knapsack Problem
Problem Statement:
(June Cook-Off 2014) Knapsack Problem
Summary:
Given \(3\leq N \geq 100000\) items with weights \(1\leq w_i \leq 2\) and costs \(1\leq c_i \leq 10^9\), output maximum costs of each \(M\) from 1 to total sum of all weights.
Solution:
At first it seems like the problem can be solved by normal Knapsack DP problems, with the recursion \(S(w) = \max_{w_i \in W} \{S(w-w_i) + c_i\} \), but \(N\) and hence \(M\) is too big for this to finish quickly enough. There are also only 2 value for weights. This suggests a more specialized algorithm to output all costs in the most efficient manner.
For me this is a very interesting problem, and the following observation is the key to solving it:
1. Given \(M\), we can try all \(m\) and \(n\) such that \(2m+n \leq M\). Furthermore, given \(m\) and \(n\), the maximum cost would be to choose \(m\) items of biggest cost with weight equals to 2, and \(n\) items of biggest cost with weight 1. Now we only need a way to choose combination of \(m\) and \(n\) effectively, and therefore the second observation:
2. Given \(m,n\) which optimizes the cost when the total weight is \(M\), we can find \(m',n'\) of \(M+1\) by taking the maximum of either \(m+1,n\) or \(m,n+1\) (we also have to ensure that the resulting \(m'\) and \(n'\) does not exceed the total 2s and 1s, or else maximum cost of \(M+1\) is equal to \(M\)
The two observations above are enough for us to develop a bottom-up DP by storing the combination of \(m,n\) for each \(M\).
(June Cook-Off 2014) Knapsack Problem
Summary:
Given \(3\leq N \geq 100000\) items with weights \(1\leq w_i \leq 2\) and costs \(1\leq c_i \leq 10^9\), output maximum costs of each \(M\) from 1 to total sum of all weights.
Solution:
At first it seems like the problem can be solved by normal Knapsack DP problems, with the recursion \(S(w) = \max_{w_i \in W} \{S(w-w_i) + c_i\} \), but \(N\) and hence \(M\) is too big for this to finish quickly enough. There are also only 2 value for weights. This suggests a more specialized algorithm to output all costs in the most efficient manner.
For me this is a very interesting problem, and the following observation is the key to solving it:
1. Given \(M\), we can try all \(m\) and \(n\) such that \(2m+n \leq M\). Furthermore, given \(m\) and \(n\), the maximum cost would be to choose \(m\) items of biggest cost with weight equals to 2, and \(n\) items of biggest cost with weight 1. Now we only need a way to choose combination of \(m\) and \(n\) effectively, and therefore the second observation:
2. Given \(m,n\) which optimizes the cost when the total weight is \(M\), we can find \(m',n'\) of \(M+1\) by taking the maximum of either \(m+1,n\) or \(m,n+1\) (we also have to ensure that the resulting \(m'\) and \(n'\) does not exceed the total 2s and 1s, or else maximum cost of \(M+1\) is equal to \(M\)
The two observations above are enough for us to develop a bottom-up DP by storing the combination of \(m,n\) for each \(M\).
Sunday, June 22, 2014
a bit of codechef: Sums in a Triangle
Problem Statement:
CodeChef: Sums in a Triangle
Summary:
Given a triangle with numbers on it, find the maximum weight path from top to bottom.
Solution:
This problem can be very overwhelming especially for a huge triangle such that a brute force solution (trying all different paths from top to bottom, and output the maximum weighted path) will take exponential time. Luckily, we can solve this problem efficiently using a concept called Dynamic Programming (DP).
Let's illustrate with the following triangle:
1
1 3
2 4 5
1 1 2 1
Let position \((i,j)\) denote \(i\)-th row and \(j\)-th column of the triangle, with topmost position is \((1,1)\). Furthermore, denote \(d(i,j)\) the value residing at position \((i,j)\).
It might not be immediately obvious which path to take, but suppose that we are at position \((i,j)\), and we know before hand the weight \(w(i+1,j)\), which is the maximum weight of the path starting from \((i+1,j)\) and also \(w(i,j+1)\), the maximum weight of the path starting from \((i,j+1)\). Then we can just choose whichever the highest, and follow that path to obtain the maximum weight path from our position \((i,j)\). Hence we can write:
$$ w(i,j) = max\{w(i+1,j),w(i,j+1)\} + d(i,j) $$
We have actually find a recursion to solve the problem! By using the optimal solutions from the subproblems, we construct an optimal solution for our current problem. If we implement the above recursion expression, we can solve the problem, but you'll notice that for large values, the algorithm can take very long to finish (and how long it is, it may take even years for large enough triangles). This is because a lot of time is spent to recalculate values that we already know, since many subproblems actually overlap. To avoid this, we can create a 2D array to store the values of \(w(i,j)\), and forces our algorithm to look up to this table and return its value whenever possible. If \(w(i,j)\) has already been calculated, we can just return the value. Only when \(w(i,j)\) has not yet been found that we explicitly proceed with the calculation, and update the value of \(w(i,j)\). Since the possible values of \((i,j)\) are only \(O(N^2)\), and each update only happens once throughout the completion of our algorithm, the running time of this top-down DP approach is \(O(N^2)\).
Another way to solve this problem is by a bottom-up approach: From the bottom of the triangles, we update the adjacent row immediately above it by explicitly choosing which path we want to follow which maximize the weight, using the same recursive expression we have derived above. As an illustration, I'll show you step by step the updates on the triangle:
Initial:
1
1 3
2 4 5
1 1 2 1
First Update:
1
1 3
3 6 7
Second Update:
1
7 10
Last Update:
11
Hence maximum path will result in weight 11, and now the problem looks very simple! Bottom-up DP implementation usually are simpler, faster to code, and easier to debug than its twin top-down DP. However, top-down approach gives us a very intuitive and easy way to transform our recursive expressions into a more efficient algorithm. Note that this approach cannot be used on problems where subproblems are not overlapping, or the problem does not exhibit a optimal substructure characteristic.
A simple implementation of bottom-up DP for this problem is illustrated below:
CodeChef: Sums in a Triangle
Summary:
Given a triangle with numbers on it, find the maximum weight path from top to bottom.
Solution:
This problem can be very overwhelming especially for a huge triangle such that a brute force solution (trying all different paths from top to bottom, and output the maximum weighted path) will take exponential time. Luckily, we can solve this problem efficiently using a concept called Dynamic Programming (DP).
Let's illustrate with the following triangle:
1
1 3
2 4 5
1 1 2 1
Let position \((i,j)\) denote \(i\)-th row and \(j\)-th column of the triangle, with topmost position is \((1,1)\). Furthermore, denote \(d(i,j)\) the value residing at position \((i,j)\).
It might not be immediately obvious which path to take, but suppose that we are at position \((i,j)\), and we know before hand the weight \(w(i+1,j)\), which is the maximum weight of the path starting from \((i+1,j)\) and also \(w(i,j+1)\), the maximum weight of the path starting from \((i,j+1)\). Then we can just choose whichever the highest, and follow that path to obtain the maximum weight path from our position \((i,j)\). Hence we can write:
$$ w(i,j) = max\{w(i+1,j),w(i,j+1)\} + d(i,j) $$
We have actually find a recursion to solve the problem! By using the optimal solutions from the subproblems, we construct an optimal solution for our current problem. If we implement the above recursion expression, we can solve the problem, but you'll notice that for large values, the algorithm can take very long to finish (and how long it is, it may take even years for large enough triangles). This is because a lot of time is spent to recalculate values that we already know, since many subproblems actually overlap. To avoid this, we can create a 2D array to store the values of \(w(i,j)\), and forces our algorithm to look up to this table and return its value whenever possible. If \(w(i,j)\) has already been calculated, we can just return the value. Only when \(w(i,j)\) has not yet been found that we explicitly proceed with the calculation, and update the value of \(w(i,j)\). Since the possible values of \((i,j)\) are only \(O(N^2)\), and each update only happens once throughout the completion of our algorithm, the running time of this top-down DP approach is \(O(N^2)\).
Another way to solve this problem is by a bottom-up approach: From the bottom of the triangles, we update the adjacent row immediately above it by explicitly choosing which path we want to follow which maximize the weight, using the same recursive expression we have derived above. As an illustration, I'll show you step by step the updates on the triangle:
Initial:
1
1 3
2 4 5
1 1 2 1
First Update:
1
1 3
3 6 7
Second Update:
1
7 10
Last Update:
11
Hence maximum path will result in weight 11, and now the problem looks very simple! Bottom-up DP implementation usually are simpler, faster to code, and easier to debug than its twin top-down DP. However, top-down approach gives us a very intuitive and easy way to transform our recursive expressions into a more efficient algorithm. Note that this approach cannot be used on problems where subproblems are not overlapping, or the problem does not exhibit a optimal substructure characteristic.
A simple implementation of bottom-up DP for this problem is illustrated below:
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int m[104][104];
int main(){
int TC;
scanf("%d",&TC);
for(int T=0;T<TC;++T){
int n;
scanf("%d",&n);
for(int i=0;i<n;++i){
for(int j=0;j<=i;++j){
scanf("%d",&m[i][j]);
}
}
for(int i=n-2;i>=0;--i){
for(int j=0;j<=i;++j){
m[i][j]=max(m[i][j]+m[i+1][j],m[i][j]+m[i+1][j+1]);
}
}
printf("%d\n",m[0][0]);
}
return 0;
}
a bit of codechef: Prime Polindromes
Problem Statement:
CodeChef - Prime Polindromes
Summary:
Given an integer \(N\), find the smallest integer \(M \geq N\) such that \(M\) is a palindrome and prime number. Limit: \(1\leq N \leq 10^6\).
Solution:
It is considered an easy problem in CodeChef (Oh my God..) and actually it's not that easy. At first it is tempting to try one by one palindromes \(P\) which is bigger than \(N\) by checking for each whether it is prime. That means for each \(P\), we have to check that \(2,3,4,5,\ldots ,P-1\) do not divide \(P\), this will take \(O(P^2)\) time, and it is bad since the limit for \(N\) is \(10^6\). Even with the fact that we just need to check until \(\sqrt{P}\), this approach will definitely result in a TLE (Time Limit Exceeded). So?
Certainly we have to choose different strategy, a different perspective. What if, we generate all primes we need beforehand? We can construct an array \(A\) consisting of around 1 million elements of 0 or 1, such that if \(i\) is a prime number, \(A[i] = 1\), and 0 otherwise. As such, if we want to check whether \(P\) is a prime, we just need to get the value of \(A[P]\), hence \(O(1)\) for the primality check. This is a dramatic decrease from our initial \(O(P^2)\)!
How can we generate all primes up to 1 million++? This is where this discussion about Sieve of Eratosthenes becomes useful. By running the algorithm to an appropriate value of \(i\), we will generate all primes needed. This will take at most \(N \times (\frac{1}{2}+\frac{1}{3}+\ldots + \frac{1}{N}) = O(N \log{N})\), which means there are around \(10^6 \times \log{10^6} = 6\times 10^6\) computations to generate the primes, quite manageable.
Finally, we just need to observe that a palindrome with even-numbered digit will never be prime, which can be proven quite easily:
Let \(P = a_0a_1...a_{k-1}a_ka_ka_{k-1}...a_1a_0\) be a palindrome with an even total digit. From here we have quite a few ways to proceed, but the easiest would be to take \(\bmod{11}\) of the palindrome, and you'll observe that \(a_i\) will have alternating sign \(\bmod{11}\), which eventually will cancel out and leads to \(P \equiv 0 \bmod{11}\).
Making use of all the information, here is one possible, and rather messy implementation of our solution:
CodeChef - Prime Polindromes
Summary:
Given an integer \(N\), find the smallest integer \(M \geq N\) such that \(M\) is a palindrome and prime number. Limit: \(1\leq N \leq 10^6\).
Solution:
It is considered an easy problem in CodeChef (Oh my God..) and actually it's not that easy. At first it is tempting to try one by one palindromes \(P\) which is bigger than \(N\) by checking for each whether it is prime. That means for each \(P\), we have to check that \(2,3,4,5,\ldots ,P-1\) do not divide \(P\), this will take \(O(P^2)\) time, and it is bad since the limit for \(N\) is \(10^6\). Even with the fact that we just need to check until \(\sqrt{P}\), this approach will definitely result in a TLE (Time Limit Exceeded). So?
Certainly we have to choose different strategy, a different perspective. What if, we generate all primes we need beforehand? We can construct an array \(A\) consisting of around 1 million elements of 0 or 1, such that if \(i\) is a prime number, \(A[i] = 1\), and 0 otherwise. As such, if we want to check whether \(P\) is a prime, we just need to get the value of \(A[P]\), hence \(O(1)\) for the primality check. This is a dramatic decrease from our initial \(O(P^2)\)!
How can we generate all primes up to 1 million++? This is where this discussion about Sieve of Eratosthenes becomes useful. By running the algorithm to an appropriate value of \(i\), we will generate all primes needed. This will take at most \(N \times (\frac{1}{2}+\frac{1}{3}+\ldots + \frac{1}{N}) = O(N \log{N})\), which means there are around \(10^6 \times \log{10^6} = 6\times 10^6\) computations to generate the primes, quite manageable.
Finally, we just need to observe that a palindrome with even-numbered digit will never be prime, which can be proven quite easily:
Let \(P = a_0a_1...a_{k-1}a_ka_ka_{k-1}...a_1a_0\) be a palindrome with an even total digit. From here we have quite a few ways to proceed, but the easiest would be to take \(\bmod{11}\) of the palindrome, and you'll observe that \(a_i\) will have alternating sign \(\bmod{11}\), which eventually will cancel out and leads to \(P \equiv 0 \bmod{11}\).
Making use of all the information, here is one possible, and rather messy implementation of our solution:
#include <cstdio>
#include <cmath>
//N must have odd digit, if even digit then it's divisible by 11
//N should be less than 10^7
//assume there exist prime of form 1.....1
//generate all primality from 1 to <1020^2
bool prime[1009050];
int pow_10(int n){
int ret=1;
for(int i=0;i<n;++i)
ret*=10;
return ret;
}
int main(){
int N;
scanf("%d",&N);
for(int i=0;i<=1009050;++i)prime[i]=1;//initialization
for(int i=2;i<=1020;++i)
for(int j=2;j<=1009050/i;++j){
prime[i*j]=0;
}
int temp=N,d=0;
while(temp!=0){ //finding num of digit of N
++d;
temp/=10;
}
int s; //starting point of trial and error
if(d%2==1)s=N/pow_10(d/2);
else s=pow_10(d/2);
while(1){ //generating palindromes... messy but correct
int t=s,e=0;
while(t!=0){++e;t/=10;}
int K=s*pow_10(e-1);
for(int i=1;i<e;++i){
K+=(s/pow_10(i))%10*pow_10(e-1-i);
}
if(prime[K] && K>=N){
printf("%d\n",K);
break;
}
++s;
}
return 0;
}
Tuesday, June 17, 2014
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:
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:
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\)
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);
}
Wednesday, May 14, 2014
a bit on backtracking
If there is one thing that computer can do very well, it is backtracking. Backtracking is one of the most fundamental problem solving paradigm: given a problem, try all possible input to come up with the solutions. This is what we did when girlfriends suddenly get angry at us, we need to generate all possibilities very quickly until a solution is found. Implementation of backtracking algorithms usually makes use of recursion, sometimes referred to as 'recursive algorithm'. The advantages of backtracking is a solution set can be produced with minimum knowledge and understanding about the problem itself. Sometimes, the only way to solve a given problem is through backtracking. Yet, this method grows very quickly in terms of complexity, hence can only be applied on problems that work on small set of input.
There are 2 basic type of backtracking algorithm that will be presented here, namely finding subsets and generating permutations. A set H is called a subset of S if and only if H contains only elements in S. A permutation is defined as a rearrangement of elements in an ordered set.
For example, given a set S = {1,2,5}, we have exactly 8 subsets of S: {1,2,5}, {1,2}, {1,5}, {2,5}, {1}, {2}, {5}, and {}.
Given an ordered set P = {1,3,4}, there are exactly 6 permutations using all elements in P: {1,3,4}, {1,4,3}, {3,1,4}, {3,4,1}, {4,1,3}, {4,3,1}.
Backtracking algorithms build valid inputs by adding a new element one by one to an existing set until a solution is found. A simple implementation of backtracking algorithm to find subsets is described as follows:
//a[N] initial set, S[N] is describes the subset of a[N]
//S[i] is 1 if a[i] is in the subset, and 0 otherwise
void backtrack_subset(int a[N],bool S[N],int k){
if(k==N){
printf("{ ");
for(int i=0;i<N;++i){
if(S[i])printf("%d ",a[i]);
}
printf("}\n");
printf("}\n");
return;
}
bool c[2]={true,false}; //new elements
for(int i=0;i<2;++i){
S[k]=c[i];
backtrack_subset(a,S,k+1);
}
}
The function starts with a call backtrack_subset(a,S,0)and terminates when k equals to N, for which a valid subset of a[N] has been constructed. The complexity of this algorithm grows exponentially, as each calls to backtrack_subset will lead to 2 calls of backtrack_subset. My 5-year old Mac withstood (with much struggling) up to N=20.
Next we have an implementation of backtracking on permutations:
void backtrack_perm(int a[N],int P[N],int k){
if(k==N){
printf("{ ");
for(int i=0;i<N;++i){printf("%d ",a[P[i]]);}
printf("}\n");
return;
}
bool ins[N]; //if i is inside P[i], ins[i] = 1, otherwise 0
for(int i=0;i<N;++i)ins[i]=false;
for(int i=0;i<k;++i)ins[P[i]]=true;
int np=0;int c[N]; //c stores possible next element
for(int i=0;i<N;++i){
if(ins[i]==false){
c[np]=i;
++np;
}
}
for(int i=0;i<np;++i){
P[k]=c[i];
backtrack_perm(a,P,k+1,cnt);
}
}
This algorithm has exactly the same idea with the previous one, in which the significant difference is the way it stores the information about whether an element a[i] is already inside the permutation. This algorithm have O(N!) complexity, hence can only be useful for N up to 10. Each call of backtrack_perm leads to another np calls to backtrack_perm where np is the number of available choices of new elements that can be added. My Mac surrendered on N=11 in which I had to hard reboot the poor machine. This idea of recursive calls to next available elements is also used in many other advanced algorithm such as graph traversal algorithms. :)
a bit of array
Algorithm attempts to solve problems through manipulation of data structures, hence data structure and algorithm go hand in hand. They are like Batman and Robin, only less gay (just saying).
One of the most fundamental data structure in any programming platform is array. When we initialize an array, especially in case of static array, we are allocating a fixed amount of blocks of memory to a certain data type, which are accessible by indicating the specific index of the array. The strength of an array structure is that by knowing the index, access operation on arrays takes O(1) time. However, since the size of arrays have to be known before use, there are chances of excessive unused memory allocated which results in lower performance.
Here is one interesting manipulation of array. Consider a problem of printing all prime numbers less than 50,000. A prime number is defined as a number which can only be divided by itself and 1. (Interestingly, 1 is not a prime ladies and gentlemen!)
A simple approach to this problem can be described as follows. For any number between 0 to 50,000, test whether it is prime, then print it. If a number is divisible by any number less than itself (excluding 1), than it is not a prime. Otherwise, we have a prime number.
Here is an interesting implementation of this idea, leveraging on the fact that if a number is a product of two other numbers (excluding 1), then it is not a prime.
#include <stdio.h>
#define N 10000
int main(){
bool a[N]; //for number 1 to 49,999,a[i]=1 if prime, 0 otherwise
for(int i=2;i<N;++i)a[i]=1; //initialize a[i]
for(int i=2;i<=N/2;++i){
for(int j=2;j<=N/i;++j){ //leveraging on symmetry of i*j
a[i*j]=0; //not prime!
}
printf("Primes less than 10,000 are: ");
for(int i=2;i<=N;++i){
if(a[i])printf("%d ",a[i]);
}
printf("\n");
return 0;
}
Leveraging on symmetry of i*j allows us to only check the value of i from 2 to N/2. j must be less than N/i since we are only interested in values of i*j that are less than N.
One of the most fundamental data structure in any programming platform is array. When we initialize an array, especially in case of static array, we are allocating a fixed amount of blocks of memory to a certain data type, which are accessible by indicating the specific index of the array. The strength of an array structure is that by knowing the index, access operation on arrays takes O(1) time. However, since the size of arrays have to be known before use, there are chances of excessive unused memory allocated which results in lower performance.
Here is one interesting manipulation of array. Consider a problem of printing all prime numbers less than 50,000. A prime number is defined as a number which can only be divided by itself and 1. (Interestingly, 1 is not a prime ladies and gentlemen!)
A simple approach to this problem can be described as follows. For any number between 0 to 50,000, test whether it is prime, then print it. If a number is divisible by any number less than itself (excluding 1), than it is not a prime. Otherwise, we have a prime number.
Here is an interesting implementation of this idea, leveraging on the fact that if a number is a product of two other numbers (excluding 1), then it is not a prime.
#include <stdio.h>
#define N 10000
int main(){
bool a[N]; //for number 1 to 49,999,a[i]=1 if prime, 0 otherwise
for(int i=2;i<N;++i)a[i]=1; //initialize a[i]
for(int i=2;i<=N/2;++i){
for(int j=2;j<=N/i;++j){ //leveraging on symmetry of i*j
a[i*j]=0; //not prime!
}
printf("Primes less than 10,000 are: ");
for(int i=2;i<=N;++i){
if(a[i])printf("%d ",a[i]);
}
printf("\n");
return 0;
}
Leveraging on symmetry of i*j allows us to only check the value of i from 2 to N/2. j must be less than N/i since we are only interested in values of i*j that are less than N.
Saturday, May 10, 2014
What is algorithm? Sounds so cheem!
Indeed, the study of algorithm can get even more complex and deep than what the already cheem word 'algorithm' suggests. Personally, it is the study of the art of solving problems by manipulating data and structures to come up with a fast and reliable solution.
1 5 40 45 80 90 120 500 670 700 800 //670 > 500, so 500 must be on the left
1 5 40 45 80 90 120 500 670 700 800 //120 < 500, 500 must be on the right
1 5 40 45 80 90 120 500 670 700 800 //FOUND IT!
Before we dwell too deeply on defining the precise meaning of algorithm and data structures, let's consider the following daily "problem".
Suppose that we have to search for an item from a pile of random stuff. How would we find the item as quickly as possible? Of course one of the most straight forward way is to go through the items in the pile one by one, from the top-most item to the bottom, until we find what we are looking for. If there are 10 items, we can find our item real quick. If we have 20 items, maybe it gets a bit longer. But what if we have 10000 items? Or a million? Our method of scanning the items one by one will take a long time before we get to find the item. Can we do better?
This is the kind of problem that you will often face when dealings with problems and trying to come up with the correct and fast enough algorithm. In this example, there is really not much we can do, given that the stuff are randomly distributed in the pile. The best solution (for now) is really scanning the whole items, and it takes linear time to find our item. Linear time means that the time taken for the algorithm to terminate is proportional to the size of the problem.
However, if we are told that the items are sorted by their weight, e.g. from the lightest to the heaviest, there is a faster solution that beats our linear time method! Let's see the following demonstration.
Suppose the weight of our item is 500kg (wonder what it is huh) and it is inside a pile of items which is sorted by weight:
1 5 40 45 80 90 120 500 670 700 800
If we try to search for the 500kg item linearly from the first item (1kg), we will find our item after 8 steps:
1 5 40 45 80 90 120 500 670 700 800 // nah..
1 5 40 45 80 90 120 500 670 700 800 // not this one..
1 5 40 45 80 90 120 500 670 700 800 // still no..
1 5 40 45 80 90 120 500 670 700 800 // uhh..
1 5 40 45 80 90 120 500 670 700 800 // persevere..
1 5 40 45 80 90 120 500 670 700 800 // cmon..
1 5 40 45 80 90 120 500 670 700 800 // oh god.. why..
1 5 40 45 80 90 120 500 670 700 800 // FOUND IT!
Total: 8 steps
Now let's revise our method by utilising the information that we have. Consider this: If we choose an item from the pile somewhere in the middle, and it turns out to be lighter than 500kg, we can ignore all items that come before it (because they will be lighter that 500kg too!) and start searching on the other half. We effectively eliminate half of our search space in one step! We can repeat the process of choosing the middle item and eliminate one half of the piles for every steps: (the blue colored numbers are the current search space at each step)
1 5 40 45 80 90 120 500 670 700 800 //90 < 500, so 500 must be right
Total: 4 steps
This is called binary search, and this algorithm takes logarithmic time, since the expected number of steps needed is proportionate to the logarithmic curve, which grows much slower than a linear curve. Binary search is an example of the application of a problem solving paradigm called "Divide and Conquer", which divides up its problem space into smaller pieces to work on, one of the most powerful recurring ideas in algorithm study.
Here we can see a huge improvement from 8 steps to 4 steps. I must admit that if we are searching for items of different weight, for example 1kg, the linear method will return faster for this case. However, when the size of the problem becomes really big, e.g 1 million, and the item that we need to find is randomized, the number of steps needed for the linear method may reach 1 million, while for binary search you need at most 20 steps to find the item!
We can see that studying algorithm can give us huge performance boost and impact on the effectiveness of our solutions. Hence, its importance goes without saying, in which its applications can range from remotely useful (such as... almost nothing) to banking, scientific research, DNA sequencing, security, airplanes scheduling, to anything that you can think of!
This simple illustration demonstrates a few common ideas on algorithm and data structure, and there are many more to look forward to.
Subscribe to:
Posts (Atom)