Problem Statement:
UVa 434 - Matty's Blocks
Summary:
This problem pertains to a matrix of size K x K, where each entry is a non-negative integer.
Let the maximum values on each row be max_row[0 .. K-1], and the maximum values on each column be max_col[0 .. K - 1].
E.g.
[ 1 4 2 5 3 ] --> 5
[ 8 1 7 6 0 ] --> 8
[ 3 3 4 1 5 ] --> 5 max_row
[ 6 5 0 3 2 ] --> 6
[ 2 4 1 6 6 ] --> 6
v v v v v
8 5 7 6 5
max_col
Our job is to fill in the matrix to fulfil those requirements. In general there are more than one way to do it. Compute:
1. Minimum sum of entries possible.
2. Maximum sum of entries possible.
Note that no constraint is placed on K in the original problem statement. It can be small, it can be very large.
Showing posts with label UVa. Show all posts
Showing posts with label UVa. Show all posts
Thursday, March 16, 2017
Friday, April 3, 2015
UVa 607 - Scheduling Lectures
Problem Statement:
UVa 607 - Scheduling Lectures
Solution:
I think I've spent more time than I should on this problem.. But indeed there are tricky parts and non-obvious parts that make the assessment of the complexity of the solution difficult to intuitively comprehend.
Let D[i][k] be the minimum dissatisfaction index (DI) incurred if we have the i-th lecture ending at k-th topic. This translates to a very simple dynamic programming relationship: D[i][k] = min { D[i-1][j] + cost(j, k) } for all j that satisfy the constraints. The cost(j, k) function is the DI function given in the problem statement. With this approach, we have an \( O(LN^2) \) run time complexity, a very bad one.
UVa 607 - Scheduling Lectures
Solution:
I think I've spent more time than I should on this problem.. But indeed there are tricky parts and non-obvious parts that make the assessment of the complexity of the solution difficult to intuitively comprehend.
Let D[i][k] be the minimum dissatisfaction index (DI) incurred if we have the i-th lecture ending at k-th topic. This translates to a very simple dynamic programming relationship: D[i][k] = min { D[i-1][j] + cost(j, k) } for all j that satisfy the constraints. The cost(j, k) function is the DI function given in the problem statement. With this approach, we have an \( O(LN^2) \) run time complexity, a very bad one.
Monday, March 30, 2015
UVa 12324 - Phillip J. Fry Problem
Problem Statement:
UVa 12324 - Phillip J. Fry Problem
Solution:
One of the classical dynamic programming problem. But might still be interesting to discuss.
Let S[i][k] be the minimum amount of time needed to finish trips [i..n]. Then the following relationship holds:
S[i][k] = min { S[i+1][k+b[i]] + t[i], S[i+1][k+b[i]-1] + t[i]/2 }
Direct implementation of this approach will result in a TLE at UVa, so you will need to prune the search space by considering the following observation: In a trip sequences with length n, you can consume at most n spheres. With that you can reduce the search space sufficiently to pass the time limit.
UVa 12324 - Phillip J. Fry Problem
Solution:
One of the classical dynamic programming problem. But might still be interesting to discuss.
Let S[i][k] be the minimum amount of time needed to finish trips [i..n]. Then the following relationship holds:
S[i][k] = min { S[i+1][k+b[i]] + t[i], S[i+1][k+b[i]-1] + t[i]/2 }
Direct implementation of this approach will result in a TLE at UVa, so you will need to prune the search space by considering the following observation: In a trip sequences with length n, you can consume at most n spheres. With that you can reduce the search space sufficiently to pass the time limit.
Wednesday, March 18, 2015
UVa 10690 - Expression Again
Problem Statement:
UVa 10690 - Expression Again
Solution:
I like this problem. Let A be the sum of the n numbers on the left, and S be the sum of all n+m numbers. Notice that the choice of A will determine the sum of the m numbers on the right, namely S-A. Our goal is to maximise and minimise A(S-A), where S is fixed. If we know beforehand all possible values of A, then the problem reduces to simply iterating through all choices of A and keeping track of the minimum and maximum A(S-A).
UVa 10690 - Expression Again
Solution:
I like this problem. Let A be the sum of the n numbers on the left, and S be the sum of all n+m numbers. Notice that the choice of A will determine the sum of the m numbers on the right, namely S-A. Our goal is to maximise and minimise A(S-A), where S is fixed. If we know beforehand all possible values of A, then the problem reduces to simply iterating through all choices of A and keeping track of the minimum and maximum A(S-A).
Tuesday, March 17, 2015
UVa 10364 - Square
Problem Statement :
Solution:
This is an innocent looking problem, but actually it is a variant of set partitioning, an NP complete problem. To solve the problem, I used a bitmasking technique coupled with a dynamic programming technique to come up with an \( O(N2^N) \) solution. While I like the problem itself, to pass the time limit on UVa, you may require some optimisations to the plain DP implementation, which makes the experience a little bit unappealing to me.
Wednesday, March 11, 2015
UVa 563 - Crimewave
Problem Statement:
UVa 563 - Crimewave
Solution:
At first, the problem seems to be of an undirected graph maximum flow, which can be tedious to do. Furthermore, each vertices (i.e. crossings) on the map has a capacity of 1. We need to transform this representation into a more friendly one, and as it turns out, we can transform this problem into our old familiar directed graph maximum flow.
UVa 563 - Crimewave
Solution:
At first, the problem seems to be of an undirected graph maximum flow, which can be tedious to do. Furthermore, each vertices (i.e. crossings) on the map has a capacity of 1. We need to transform this representation into a more friendly one, and as it turns out, we can transform this problem into our old familiar directed graph maximum flow.
Wednesday, December 17, 2014
UVa 11167: Monkeys in the Emei Mountain
Problem Statement:
UVa 11167 - Monkeys in the Emei Mountain
Solution:
A pretty tough maxflow problem. Oh yes, this is a bipartite matching problem between N monkeys and 50000 time intervals. The simplest way to think about this problem is to have N nodes representing monkeys, 50000 nodes representing time intervals, and two nodes S and T which are source and sink respectively. A monkey has to drink v times, hence we add an edge between S and that monkey with capacity v. This monkey can drink from time interval s to t, so we add an edge to each time interval from s to t by capacity 1 each. Finally, each time interval can only be shared between M monkeys, so for each time interval we add an edge to T with capacity M. The maximum flow from S to T will give us the maximum bipartite matching between the monkeys and the time intervals. If this maximum flow exactly equals to the total times all monkeys have to drink, we have found a valid matching.
UVa 11167 - Monkeys in the Emei Mountain
Solution:
A pretty tough maxflow problem. Oh yes, this is a bipartite matching problem between N monkeys and 50000 time intervals. The simplest way to think about this problem is to have N nodes representing monkeys, 50000 nodes representing time intervals, and two nodes S and T which are source and sink respectively. A monkey has to drink v times, hence we add an edge between S and that monkey with capacity v. This monkey can drink from time interval s to t, so we add an edge to each time interval from s to t by capacity 1 each. Finally, each time interval can only be shared between M monkeys, so for each time interval we add an edge to T with capacity M. The maximum flow from S to T will give us the maximum bipartite matching between the monkeys and the time intervals. If this maximum flow exactly equals to the total times all monkeys have to drink, we have found a valid matching.
Saturday, November 15, 2014
UVa 787 - Maximum Sub-sequence
Problem Statement:
787 - Maximum Sub-sequence
Solution:
Interesting DP problem, but the problem requires Big Integer implementation. Anyway the term "subsequence" here actually does not mean what you think it means, in this problem it refers to consecutive sequence of elements. The idea is simply to find an efficient way to calculate all resulting products off any consecutive sequences, which are only 10K of them since there are only 100 elements. This can be done using a DP technique in \(O(N^2)\).
787 - Maximum Sub-sequence
Solution:
Interesting DP problem, but the problem requires Big Integer implementation. Anyway the term "subsequence" here actually does not mean what you think it means, in this problem it refers to consecutive sequence of elements. The idea is simply to find an efficient way to calculate all resulting products off any consecutive sequences, which are only 10K of them since there are only 100 elements. This can be done using a DP technique in \(O(N^2)\).
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 greedy: UVa 100249 - The Grand Dinner
Problem Statement:
UVa 100249 - The Grand Dinner
Summary:
Given several groups of people, each group consisting of several people, and given several tables of varying capacities, is it possible to place everyone in the tables such that people from the same group are not seated in the same table? If so, print out the possible arrangement.
Solution:
Apparently the problem is solvable by modeling it as some kind of matching problem and by finding the max-flow on the matching graph. However, apparently also, the problem can be solved using a greedy strategy by first sorting the groups in order of size, as well as the table in order of capacity, and start trying to assign each person in the group starting from the largest group down the sorted order of tables. Haven't thought of a proof yet...
UVa 100249 - The Grand Dinner
Summary:
Given several groups of people, each group consisting of several people, and given several tables of varying capacities, is it possible to place everyone in the tables such that people from the same group are not seated in the same table? If so, print out the possible arrangement.
Solution:
Apparently the problem is solvable by modeling it as some kind of matching problem and by finding the max-flow on the matching graph. However, apparently also, the problem can be solved using a greedy strategy by first sorting the groups in order of size, as well as the table in order of capacity, and start trying to assign each person in the group starting from the largest group down the sorted order of tables. Haven't thought of a proof yet...
#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <utility> using namespace std; /* First IDEA: sort by no of ppl, sort by table for each group, go through table in sorted order assign what is available if possible, print arragement, otherwise no arrangement is possible proof: dunno yet */ vector<pair<int,int> > ppl, tbl; int pp[73] /*, tt[53]*/; int ppp[73][103], ttt[73]; int main(){ int N,M; while( cin >> M >> N ){ if(N+M==0) break; ppl.clear(); tbl.clear(); for(int i=0;i<M;++i){ int u; cin >> u; ppl.push_back(make_pair(u,i)); } for(int i=0;i<N;++i){ int u; cin >> u; tbl.push_back(make_pair(u,i)); } sort(ppl.begin(), ppl.end()); sort(tbl.begin(), tbl.end()); reverse(ppl.begin(), ppl.end()); reverse(tbl.begin(), tbl.end()); for(int i=0;i<M;++i){ pp[ppl[i].second] = i; } for(int i=0;i<N;++i){ //tt[tbl[i].second] = i; ttt[i] = tbl[i].first; } bool ok = true; for(int i=0;i<M;++i){ int sz = ppl[i].first; int k = 0; for(int j=0;j<sz;++j){ bool found = false; for(;k<N;++k){ if(ttt[k] > 0){ found = true; ppp[i][j] = tbl[k].second; --ttt[k]; break; } } if(!found){ ok = false; break; } ++k; } if(!ok) break; } if(!ok) printf("0\n"); else { printf("1\n"); for(int i=0;i<M;++i){ int sz = ppl[pp[i]].first; for(int j=0;j<sz;++j){ if(j != 0) printf(" "); printf("%d", ppp[pp[i]][j]+1); } printf("\n"); } } } return 0; }
Saturday, September 20, 2014
a bit of greedy: UVa 10037 - Bridge
Problem Statement
UVa 10037 - Bridge
Summary:
(A very famous puzzle actually) \(N\) people trying to cross the bridge with one flashlight. Only groups with at most \(2\) people can cross the bridge, and a group has to carry flashlight in order to cross. Each person has a speed, which is the time needed for him to cross the bridge. Furthermore, the time needed for a group to cross the bridge is as fast as the slowest person in that group. Find the minimum time needed to cross everyone off to the other side.
Solution:
There is a greedy "intuition" (or is it? :( ) as follows:
The proof to the intuition is somewhat more elaborate, by representing the problem as a graph problem.
UVa 10037 - Bridge
Summary:
(A very famous puzzle actually) \(N\) people trying to cross the bridge with one flashlight. Only groups with at most \(2\) people can cross the bridge, and a group has to carry flashlight in order to cross. Each person has a speed, which is the time needed for him to cross the bridge. Furthermore, the time needed for a group to cross the bridge is as fast as the slowest person in that group. Find the minimum time needed to cross everyone off to the other side.
Solution:
There is a greedy "intuition" (or is it? :( ) as follows:
/* Suggested Greedy algo: Incremental construction: The idea is to always bring the first and second slowest to the other side with the help of the first and second fastest say the fastests are A<B and the slowest are X>Y then we have 2 cases: 1. M = (A,X) + (A,0) + (A,Y) + (A,0) M = 2*A + X + Y 2. M' = (A,B) + (A,0) + (X,Y) + (B,0) M' = 2*B + A + X And incrementally choosing the minimum of M and M' at each step. Proof? I dont know */
The proof to the intuition is somewhat more elaborate, by representing the problem as a graph problem.
a bit of greedy: UVa 10026 - Shoemaker's Problem
Problem Statement:
UVa 10026 - Shoemaker's Problem
Summary:
Given a list of jobs, we can only work on one job each day. Each job \(i\) takes \(t_i\) days to complete and for each day of not starting on the job, we must pay \(s_i\) fine. Once we start on a job, we will finish it before starting the next job. We are to find the best permutation/arrangement of the jobs that minimizes the total fine incurred.
Solution:
A great application of exchange argument that establishes the relationship that must hold in an optimal arrangement amongst all permutation. This optimization problem reduces to sorting problem.
UVa 10026 - Shoemaker's Problem
Summary:
Given a list of jobs, we can only work on one job each day. Each job \(i\) takes \(t_i\) days to complete and for each day of not starting on the job, we must pay \(s_i\) fine. Once we start on a job, we will finish it before starting the next job. We are to find the best permutation/arrangement of the jobs that minimizes the total fine incurred.
Solution:
A great application of exchange argument that establishes the relationship that must hold in an optimal arrangement amongst all permutation. This optimization problem reduces to sorting problem.
#include <iostream> #include <cstdio> #include <algorithm> #include <vector> using namespace std; /* The correct greedy algo and its proof: sort by fine/time Proof: s is fine, t is days Suppose that (s_1,t_1), (s_2,t_2), ..., (s_n,t_n) is the optimal arrangement such that the total fine is the lowest. Hence we have O = s_1 (0) + s_2 (t_1) + s_3 (t_1 + t_2) + ... + s_i (t_1 + t_2 + ... + t_{i-1}) + s_{i+1} (t_1 + t_2 + ... + t_{i-1} + t_i) + ... Since O is optimal, by exchange argument, if we exchange the position of s_i,t_i and s_{i+1},t_{i+1}, we will have total fine O' which will cannot be lower than O: O' = ... + s_{i+1} (t_1 + t_2 + ... + t_{i-1}) + s_i (t_1 + t_2 + ... + t_{i-1} + t_{i+1}) + ... hence O' - O >= 0 <=> s_{i+1} (-t_i) + s_i (t_{i+1}) >= 0 <=> s_i/t_i >= s_{i+1}/t_{i+1} Hence in the optimal arrangement, s_i comes before s_{i+1} iff s_i/t_i >= s_{i+1}/t_{i+1} */ vector<int> arr, s, t; bool comp(const int& L, const int& R){ if(s[L] * t[R] == s[R] * t[L]) return L < R; return s[L] * t[R] < s[R] * t[L]; } int main(){ int TC; cin >> TC; bool flag = false; while(TC--){ if(flag) printf("\n"); flag = true; int N; cin >> N; arr.clear(); s.clear(); t.clear(); for(int i=0;i<N;++i){ int u,v; cin >> u >> v; s.push_back(u); t.push_back(v); arr.push_back(i); } sort(arr.begin(), arr.end(), comp); for(int i=0;i<N;++i){ if(i != 0) printf(" "); printf("%d", arr[i]+1); } printf("\n"); } return 0; }
Monday, September 15, 2014
a bit of uva: UVa 11026 - A Grouping Problem
Problem Statement:
UVa 11026 - A Grouping Problem
Summary:
We are given \(a_1,a_2,\ldots,a_n\) and a number \(K\) which defines the sum of products of permutation of length K, e.g. \(K=1\) is \(a_1+a_2+\ldots+a_n\), \(K=2\) is \(a_1a_2 + a_2a_3+ \ldots + a_{n-1}a_n\) and so on and so forth. Find the maximum of these sum of products \(\mod{M}\).
Solution:
Despite the technicality, this problem has a very nice recursive formulation:
Let \(S(k,n)\) be the sum of products of permutation of length \(k\) amongst \(n\) elements. Then we have \(S(k,n) = a_n * S(k-1,n-1) + S(k, n-1)\). This is actually derived from the factorization of \(a_n\) from all the terms that contain \(a_n\). From here, we can do a bottom-up DP to arrive at the answer. Here is a sample implementation:
UVa 11026 - A Grouping Problem
Summary:
We are given \(a_1,a_2,\ldots,a_n\) and a number \(K\) which defines the sum of products of permutation of length K, e.g. \(K=1\) is \(a_1+a_2+\ldots+a_n\), \(K=2\) is \(a_1a_2 + a_2a_3+ \ldots + a_{n-1}a_n\) and so on and so forth. Find the maximum of these sum of products \(\mod{M}\).
Solution:
Despite the technicality, this problem has a very nice recursive formulation:
Let \(S(k,n)\) be the sum of products of permutation of length \(k\) amongst \(n\) elements. Then we have \(S(k,n) = a_n * S(k-1,n-1) + S(k, n-1)\). This is actually derived from the factorization of \(a_n\) from all the terms that contain \(a_n\). From here, we can do a bottom-up DP to arrive at the answer. Here is a sample implementation:
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; typedef long long Long; Long MOD, a[1003], dp[1003][1003]; int N; // Recursion: S(k, n) = a_n * S(k-1, n-1) + S(k, n-1) int main(){ for(int i=0;i<1003;++i){ dp[0][i] = 1; } while(cin >> N >> MOD){ if(N+MOD == 0) break; for(int i=1;i<=N;++i){ cin >> a[i]; } for(int i=1;i<=N;++i){ for(int j=i;j<=N;++j){ dp[i][j] = (a[j] * dp[i-1][j-1])%MOD; if(j > i) dp[i][j] += dp[i][j-1]; dp[i][j] %= MOD; if(dp[i][j] < 0) dp[i][j] += MOD; } } Long ans = 0; for(int i=1;i<=N;++i){ ans = max(ans, dp[i][N]); } cout << ans << endl; } return 0; }
Friday, September 12, 2014
a bit of uva: UVa 10688 - The Poor Giant
Problem Statement:
UVa 10688 - The Poor Giant
Summary:
There are \(N\) apples, and each apples have weight \(K+1, K+2, \ldots, K+N\). There is exactly one apple which is "sweet", and all other apples' taste is measured against the sweet apple: an apple is "bitter" iff it weighs less than sweet apple, otherwise it is a "sour" apple. For a sequence of apples, we have a function \(C(\{a_i\}, k) = \text{minimum total weight of apples eaten before encountering } a_k\), and we want to minimize \(S = \sum_{k=1}^{N} C(\{a_i\}, k) \).
Solution:
Rather than trying all possible sequences and simulating the eating process one by one to arrive at S (which has an exponential complexity btw), we can solve this problem by breaking it into a smaller sub problems by recursion. Furthermore, this problem exhibits an optimal substructure property, as will be clear once we have derived the recursive relationship.
Suppose we have \(M(L,R)\) which is the minimum total weight of apples required for all \(k = L \ldots R\). Let's say we choose \(a_i\) (\(L \leq i \leq R\)) to be eaten first. If \(a_i\) is the sweet apple, then the simulation will terminate. Otherwise, \(a_i\) is not a sweet apple, hence it can be sour or bitter, then we need to find both \(M(L,i-1)\) and \(M(i+1, R)\) to cover both cases. We will end up with the following recursion: \(M(L,R) = min_{L\leq i \leq R} \{ (R-L+1)a_i + M(L,i-1) + M(i+1,R) \}\).
Since there are a lot of overlapping subproblems, we can memoize the results based on the parameter \(L\) and \(R\). This will cut down the running time to \(O(N^3)\).
Implementation in C++:
UVa 10688 - The Poor Giant
Summary:
There are \(N\) apples, and each apples have weight \(K+1, K+2, \ldots, K+N\). There is exactly one apple which is "sweet", and all other apples' taste is measured against the sweet apple: an apple is "bitter" iff it weighs less than sweet apple, otherwise it is a "sour" apple. For a sequence of apples, we have a function \(C(\{a_i\}, k) = \text{minimum total weight of apples eaten before encountering } a_k\), and we want to minimize \(S = \sum_{k=1}^{N} C(\{a_i\}, k) \).
Solution:
Rather than trying all possible sequences and simulating the eating process one by one to arrive at S (which has an exponential complexity btw), we can solve this problem by breaking it into a smaller sub problems by recursion. Furthermore, this problem exhibits an optimal substructure property, as will be clear once we have derived the recursive relationship.
Suppose we have \(M(L,R)\) which is the minimum total weight of apples required for all \(k = L \ldots R\). Let's say we choose \(a_i\) (\(L \leq i \leq R\)) to be eaten first. If \(a_i\) is the sweet apple, then the simulation will terminate. Otherwise, \(a_i\) is not a sweet apple, hence it can be sour or bitter, then we need to find both \(M(L,i-1)\) and \(M(i+1, R)\) to cover both cases. We will end up with the following recursion: \(M(L,R) = min_{L\leq i \leq R} \{ (R-L+1)a_i + M(L,i-1) + M(i+1,R) \}\).
Since there are a lot of overlapping subproblems, we can memoize the results based on the parameter \(L\) and \(R\). This will cut down the running time to \(O(N^3)\).
Implementation in C++:
int dp[503][503]; int a[503]; int rec(int L, int R){ if(R <= L) return 0; if(R-L == 1) return a[L]*2; if(R-L == 2) return a[L+1]*3; if(dp[L][R] != -1) return dp[L][R]; int ret = MAXINT; for(int i=L; i<= R; ++i){ ret = min(a[i]*(R-L+1) + rec(L,i-1) + rec(i+1,R), ret); } dp[L][R] = ret; return ret; }
Wednesday, September 10, 2014
a bit of uva: UVa 10003 - Cutting Sticks
Problem Statement:
UVa 10003 - Cutting Sticks
Summary:
You are given a stick with length L, and N points where you need to cut the stick. Find the minimum total cost of cutting the sticks if the cost of each cutting operation is defined as the length of the stick before cutting.
Solution:
I like this problem because it can be solved with a very neatly written program! :P
Firstly notice that after each operation of cutting, we form two subproblems which are essentially the same as the original problem, hence the determination of the minimum cost can be done recursively. The recursion relationship is: let \(M(L,R)\) be the minimum cost needed to complete the necessary cuts from between point \(L\) and \(R\), then we have \(M(L,R) = min_{L < k < R}\{ \text{len}(L,R) + M(L, k) + M(k, R) \} \). Then we just need a memoization table to store all possible values of M(L,R), since the subproblems often overlap (and hence Dynamic Programming to the rescue!) and really there are at most \(O(N^2)\) subproblems.
Sample C++ implementation:
UVa 10003 - Cutting Sticks
Summary:
You are given a stick with length L, and N points where you need to cut the stick. Find the minimum total cost of cutting the sticks if the cost of each cutting operation is defined as the length of the stick before cutting.
Solution:
I like this problem because it can be solved with a very neatly written program! :P
Firstly notice that after each operation of cutting, we form two subproblems which are essentially the same as the original problem, hence the determination of the minimum cost can be done recursively. The recursion relationship is: let \(M(L,R)\) be the minimum cost needed to complete the necessary cuts from between point \(L\) and \(R\), then we have \(M(L,R) = min_{L < k < R}\{ \text{len}(L,R) + M(L, k) + M(k, R) \} \). Then we just need a memoization table to store all possible values of M(L,R), since the subproblems often overlap (and hence Dynamic Programming to the rescue!) and really there are at most \(O(N^2)\) subproblems.
Sample C++ implementation:
int a[55]; int N; int dp[55][55]; //0 stores 0, N+1 stores full length //1 indexed int rec(int L, int R){ if(L+1 == R) return 0; if(dp[L][R] != -1) return dp[L][R]; int ans = MAXINT; for(int i=L+1;i<R;++i){ ans = min(ans, a[R] - a[L] + rec(L, i) + rec(i, R)); } dp[L][R] = ans; return ans; }
Wednesday, August 27, 2014
a bit of uva: Trainsorting - An intereseting application of LIS
Problem Statement:
UVa 11456 - Trainsorting
Summary:
Given \( S = \{a_1,a_2, \ldots, a_n\} \) where all \(a_i\) are distinct integers, and a dequeue \(D\) (initially empty), and operations push_back, push_front (which push an element to the back or to the front of D) or skip (which skips the element, of course) performed on elements in S from left to right, find the maximum length of D such that the elements inside are in increasing order.
(I have the talent to turn the summary of the problem into a more confusing piece of crap haha)
To approach this problem, we need knowledge on Longest Increasing Subsequence (LIS) and its direct variant, Longest Decreasing Subsequence (LDS).
Let me describe the algorithm to solve this problem first:
let LIS[i] be an array which stores the longest increasing subsequence in [i .. N]
let LDS[i] be an array which stores the longest decreasing subsequence in [i .. N]
set ans = 0
For \(a_i\) in \(S\):
Either use \(a_i\) as the pivot or not.
If use \(a_i\) as pivot:
\( \text{ans} = \max\{ans, \text{LIS[i]} + \text{LDS[i]} - 1 \} \)
Otherwise skip \(a_i\) and never look back :P
In the end of the for loop, \(\text{ans}\) will be the longest \(D\) possible.
Proof for optimality of \(D\): WLOG, assume that \(D = D_i\) where \(D_i\) is the longest dequeue constructed using elements in [i .. N] only. Suppose (for the sake of contradiction) that we can append some additional elements to \(D_i\) using elements in [1 .. (i-1)] to form \(D'_i\), and let the element added with the smallest index be \(a_j\) (where \(j < i\)). Clearly \(|D'_i| > |D_i|\). However, we also have \(|D_j| \leq |D_i|\) where \(D_j\) is the longest dequeue constructible using elements in [j .. N]. This means that \(|D_i| \geq |D_j| \geq |D'_i| > |D_i|\), a contradiction. Hence \(D\) must have been optimal in the first place, which completes the proof on the correctness on the algorithm.
UVa 11456 - Trainsorting
Summary:
Given \( S = \{a_1,a_2, \ldots, a_n\} \) where all \(a_i\) are distinct integers, and a dequeue \(D\) (initially empty), and operations push_back, push_front (which push an element to the back or to the front of D) or skip (which skips the element, of course) performed on elements in S from left to right, find the maximum length of D such that the elements inside are in increasing order.
(I have the talent to turn the summary of the problem into a more confusing piece of crap haha)
To approach this problem, we need knowledge on Longest Increasing Subsequence (LIS) and its direct variant, Longest Decreasing Subsequence (LDS).
Let me describe the algorithm to solve this problem first:
let LIS[i] be an array which stores the longest increasing subsequence in [i .. N]
let LDS[i] be an array which stores the longest decreasing subsequence in [i .. N]
set ans = 0
For \(a_i\) in \(S\):
Either use \(a_i\) as the pivot or not.
If use \(a_i\) as pivot:
\( \text{ans} = \max\{ans, \text{LIS[i]} + \text{LDS[i]} - 1 \} \)
Otherwise skip \(a_i\) and never look back :P
In the end of the for loop, \(\text{ans}\) will be the longest \(D\) possible.
Proof for optimality of \(D\): WLOG, assume that \(D = D_i\) where \(D_i\) is the longest dequeue constructed using elements in [i .. N] only. Suppose (for the sake of contradiction) that we can append some additional elements to \(D_i\) using elements in [1 .. (i-1)] to form \(D'_i\), and let the element added with the smallest index be \(a_j\) (where \(j < i\)). Clearly \(|D'_i| > |D_i|\). However, we also have \(|D_j| \leq |D_i|\) where \(D_j\) is the longest dequeue constructible using elements in [j .. N]. This means that \(|D_i| \geq |D_j| \geq |D'_i| > |D_i|\), a contradiction. Hence \(D\) must have been optimal in the first place, which completes the proof on the correctness on the algorithm.
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.
Sunday, August 17, 2014
a bit of uva: UVa 10125 - Sumsets
Problem Statement:
UVa 10125 - Sumsets
Summary:
Given a set \(S\) of distinct integers, find the largest \(d\) such that \(a + b + c = d\) where \(a,b,c,d\) are all distinct elements in S.
Simple brute force approach will give an \(O(N^4)\) complexity, which is bad since \(|S|\) can be as large as 1000 in this problem. Therefore the problem begs for a more efficient approach, and indeed an \(O(N^2\lg{N})\) solution exist, and we need to utilize binary search to achieve this running time.
Firstly, notice that the problem can be restated as finding \(a,b,c,d\) that satisfy \(a+b = d - c\). This simple restatement of the problem has a huge implication: we can find all possible values of \(a+b\) in \(O(N^2)\) time, similarly for \(d-c\), hence total we need \(O(N^2)\) to generate all \(a+b\) and all \(d-c\), which can be stored in two arrays or vectors, say \(P\) and \(Q\) respectively. Next, we sort \(P\) and \(Q\). Why sorting? so that we can do a binary search! From here on the task is simple; we need to try all elements in \(P\) and find whether there exist an element with the same value in \(Q\). If there is, then check whether they have distinct \(a,b,c,d\), and if so we update our answer on \(d\).
Each binary search has time complexity of \(O(\lg{N^2})\), which happen \(N^2\) times, so we have running time of \(O(N^2\lg{N})\) over all. Beautiful isn't it.
UVa 10125 - Sumsets
Summary:
Given a set \(S\) of distinct integers, find the largest \(d\) such that \(a + b + c = d\) where \(a,b,c,d\) are all distinct elements in S.
Simple brute force approach will give an \(O(N^4)\) complexity, which is bad since \(|S|\) can be as large as 1000 in this problem. Therefore the problem begs for a more efficient approach, and indeed an \(O(N^2\lg{N})\) solution exist, and we need to utilize binary search to achieve this running time.
Firstly, notice that the problem can be restated as finding \(a,b,c,d\) that satisfy \(a+b = d - c\). This simple restatement of the problem has a huge implication: we can find all possible values of \(a+b\) in \(O(N^2)\) time, similarly for \(d-c\), hence total we need \(O(N^2)\) to generate all \(a+b\) and all \(d-c\), which can be stored in two arrays or vectors, say \(P\) and \(Q\) respectively. Next, we sort \(P\) and \(Q\). Why sorting? so that we can do a binary search! From here on the task is simple; we need to try all elements in \(P\) and find whether there exist an element with the same value in \(Q\). If there is, then check whether they have distinct \(a,b,c,d\), and if so we update our answer on \(d\).
Each binary search has time complexity of \(O(\lg{N^2})\), which happen \(N^2\) times, so we have running time of \(O(N^2\lg{N})\) over all. Beautiful isn't it.
Wednesday, August 6, 2014
a bit of uva: UVa 104 - Arbitrage
Problem Statement:
UVa 104 - Arbitrage
Summary:
Given an adjacency matrix, find the shortest cycle such that the product of the edges is bigger than 1.01
I was stuck on this problem for a while (I sincerely think that this question is difficult! haha) because a lot of people said they solved this problem simply by running Floyd-Warshall on the graph. However, I really don't think that the implementation is that obvious. Eventually, I learnt a way to solve the problem, it resembles Floyd-Warshall, but not exactly the same. It borrows the main idea that we can incrementally build an optimal path by considering k = 1,2,...,N one by one.
The idea is this:
Suppose we are given a path with \(m\) edges for each pair of vertices \( (i,j) \)such that the product of the edges is maximum (in other words, the optimal path using \(m\) edges). Then to find the optimal path between \(i,j\) using \(m+1\) edges can be done by trying all \(k = 1,2,3,\ldots, N\) and choose \(k\) such that the path i-k-j (where i-k has \(m\) edges, k-j is a direct edge\) is optimal. That means, we take D[i][j][m+1] = max of ( D[i][k][m] * D[k][j][1] ) for k = 1,2,...,N. Now it remains to prove that the path we found is indeed optimal, and the proof is by contradiction. Suppose that there is \(p\) = i-k'-j (where i-k' has m edges, k'-j is a direct edge) with \(k' \neq k\) such that the product of its edges are larger than that of i-k-j. Furthermore, suppose that \(q\) is the path i-k'-j such that i-k' is the optimal path using m edges. Then we have: product of edges of \(p\) \(\leq\) product of edges of \(q\) < product of edges of i-k-j, contradiction. Therefore i-k-j found must have been optimal.
As such we can solve the problem by iterating through m starting from m = 2, with the initial condition of m=1 which is the initial adjacency matrix. We also need to maintain a path matrix to reconstruct the path found. This is done by storing the information about the parent of j in a path between i and j: At first, every parent of j is i for all i-j. During the progress of the algorithm, if i-k-j is larger than i-j, update par[i][j] = k (since the parent of j is now k).
Implementation:
UVa 104 - Arbitrage
Summary:
Given an adjacency matrix, find the shortest cycle such that the product of the edges is bigger than 1.01
I was stuck on this problem for a while (I sincerely think that this question is difficult! haha) because a lot of people said they solved this problem simply by running Floyd-Warshall on the graph. However, I really don't think that the implementation is that obvious. Eventually, I learnt a way to solve the problem, it resembles Floyd-Warshall, but not exactly the same. It borrows the main idea that we can incrementally build an optimal path by considering k = 1,2,...,N one by one.
The idea is this:
Suppose we are given a path with \(m\) edges for each pair of vertices \( (i,j) \)such that the product of the edges is maximum (in other words, the optimal path using \(m\) edges). Then to find the optimal path between \(i,j\) using \(m+1\) edges can be done by trying all \(k = 1,2,3,\ldots, N\) and choose \(k\) such that the path i-k-j (where i-k has \(m\) edges, k-j is a direct edge\) is optimal. That means, we take D[i][j][m+1] = max of ( D[i][k][m] * D[k][j][1] ) for k = 1,2,...,N. Now it remains to prove that the path we found is indeed optimal, and the proof is by contradiction. Suppose that there is \(p\) = i-k'-j (where i-k' has m edges, k'-j is a direct edge) with \(k' \neq k\) such that the product of its edges are larger than that of i-k-j. Furthermore, suppose that \(q\) is the path i-k'-j such that i-k' is the optimal path using m edges. Then we have: product of edges of \(p\) \(\leq\) product of edges of \(q\) < product of edges of i-k-j, contradiction. Therefore i-k-j found must have been optimal.
As such we can solve the problem by iterating through m starting from m = 2, with the initial condition of m=1 which is the initial adjacency matrix. We also need to maintain a path matrix to reconstruct the path found. This is done by storing the information about the parent of j in a path between i and j: At first, every parent of j is i for all i-j. During the progress of the algorithm, if i-k-j is larger than i-j, update par[i][j] = k (since the parent of j is now k).
Implementation:
void floyd(){ for(int s=1;s<N;++s) //0 indexed for(int k=0;k<N;++k) for(int i=0;i<N;++i) for(int j=0;j<N;++j){ double temp = arb[i][k][s-1]*arb[k][j][0]; if(temp > arb[i][j][s]){ arb[i][j][s] = temp; par[i][j][s] = k; //since par[k][j][0] = k } } }
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.
Subscribe to:
Posts (Atom)