Uva 10154 – Weights and Measures
Link: 10154 – Weights and Measures
Solution: DP
Discussion:
* Sort the turtle ascending according to their strength( Not residual strength). If equal strength, that according weight
Proof From Uva Forum:
Assume the solution would have a turtle that is stacked upon a turtle with smaller strength. Then the turtle with smaller strength has to carry also the weight of the turtle with bigger strength. So it is also possible to exchange them, because if the turtle with smaller strength can carry at least both weights, then of course the turtle with bigger strength can.
DP Solution from Uva :
Go through the list of turtles that is sorted ascending by strength (because I try to stack a tower of turtles upon ith turtle, therefore the turtle with smallest strength has to go first). In each step calculate the minimum weight that a stack of k turtles has. If it is impossible to have a stack of k turtles, define this as Infinity. Lets define this as mw(i,k) (i is number of step).
mw(i,k) = min(mw(i-1,k),mw(i-1,k-1)+weight(i)) if mw(i-1,k-1)+weight(i)<=strength(i)
else mw(i,k) = mw(i-1,k).
Answer is maximum k with mw(n,k)<infinity.
This problem helped me to think dp problems with a different angle.
Click to See Code
#include <bits/stdc++.h>
using namespace std;
const int N = 5610;
pair<int,int> b[N];
int n=0;
int dp[N][N];
bool cmp(pair<int,int> a,pair<int,int> b)
{
if(a.second == b.second) return a.first < b.first;
return a.second < b.second;
}
int main()
{
n=1;
while(scanf("%d %d",&b[n].first,&b[n].second)==2) {
n++;
}
sort(b+1,b+n,cmp);
int f = 0;
for(int i= 0;i < n; i ++) {
for(int j= 0; j < n ; j++ ) dp[i][j] = 1e8;
}
dp[0][0] = 0;
for(int i = 1; i < n; i ++ ) {
dp[i][0] = 0;
for(int j = 1; j < n ; j ++ ) {
dp[i][j] = dp[i-1][j];
if(dp[i-1][j-1] + b[i].first <= b[i].second) {
dp[i][j] = min(dp[i][j] , dp[i-1][j-1] + b[i].first);
}
}
}
for(int i = 1; i < n; i ++ ) {
for(int j = 1; j < n ; j ++ ) {
if(dp[i][j] < 1e8) {
f= max(f,j);
}
}
}
printf("%d\n",f);
}
Uva 10164 – Number Game
Link: 10164 – Number Game
Solution : Backtracking
The backtracking solution has complexity of O(n^3) but passes quickly. As it finds answer very quickly and return from recursion.
Three state:
calc(sum,cnt,ind) => sum = summation of numbers that are taken, cnt = # of elements taken, ind = current position.
Two options: 1.we can take current number then recurse 2. or not to take and recurse
If anytime we find a solution, we directly return.
Click to See Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1<<10;
int dp[N]; // This stores the number taken.
int a[N*2];
int n;
bool flag = 0;
void calc(int sum,int cnt, int ind)
{
if(cnt==n){
if(sum % n ==0){
flag = 1; // found a solution
printf("Yes\n");
for(int i = 0; i < n;i ++) {
if(i)printf(" ");
printf("%d",dp[i]);
}
printf("\n");
}
return;
}
if(flag) return; // If already found a solution, then return
if(ind >= 2*n-1) return;
dp[cnt] = a[ind];
calc(sum + a[ind], cnt+1, ind+1); // Taking a[ind]
calc(sum,cnt,ind+1); // Not taking ind
}
int main()
{
while(scanf("%d",&n) && n) {
for(int i = 0; i < 2*n -1;i ++ ) {
scanf("%d",&a[i]);
}
memset(dp,0,sizeof dp);
flag = 0;
calc(0,0,0);
if(!flag) printf("No\n");
}
}
Code for Fun 