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\).
Showing posts with label CodeChef. Show all posts
Showing posts with label CodeChef. Show all posts
Monday, June 23, 2014
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;
}
Subscribe to:
Posts (Atom)