## 10154 - Weights and Measures

Moderator: Board moderators

### Re: 10154 - Weights and Measures

Here is my code:
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 5607
int MIN(int a,int b)
{
return a<b?a:b;
}

typedef struct
{
int strenght,weight;
}turtle;

bool CMP(const turtle& a,const turtle& b)
{
if(a.strenght!=b.strenght)
{
return a.strenght>b.strenght;
}
return a.weight>b.weight;
}

turtle a[MAXN+10];
int l[MAXN+10],p[MAXN+10];
int main(){
//freopen("weights.in","r",stdin); freopen("weights.out","w",stdout);
int i,j,pos=0;

while(scanf("%d%d",&a[pos].weight,&a[pos].strenght)!=EOF)
{
pos++;
}

sort(a,a+pos,CMP);

int max,maxlen=0,k;
for(i=0;i<pos;++i)
{
max=0;
l[i]=1;
p[i]=a[i].strenght-a[i].weight;
for(j=0;j<i;++j)
{
if(a[i].weight<=p[j])
{
if(l[i]<=l[j]+1)
{
l[i]=l[j]+1;
k=MIN(p[j]-a[i].weight,a[i].strenght-a[i].weight);
if(k>max)
{
p[i]=k;
max=k;
}
}
}
}
if(l[i]>maxlen)maxlen=l[i];
}
printf("%d\n",maxlen);
return 0;
}
Igor9669
Learning poster

Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: 10154 - Weights and Measures

RS (residual strength) = Actualstrength (AS) - weight(W)

RS = AS - W
if i 've RS1 < RS2 how would i order and why ?You are odering it from bottom{maximum residual strenght at bottom} (turtle 2)RS2 < (turtle 1) RS1 because RS2 can carry more weight.lets say AS1 = 1000, W1=900, AS2=800, W2=600, now RS2 < RS1 but we cannot order T2<T1, this is because residues doesnot tell anything about the total strength.AS1=1200,W1=900 RS1=300, AS2=900,W2=200, RS2=700 , you cannot do T2 < T1 ie T1 on top of T2 (just on the basis of residue) but T1 < T2 is certainly possible.

Ordering by weight,============
maximum weight (turtle TMW) at bottom position 1 and total height is H.

TMW is at position 1. and the ordering is TMW1 < TK < TP < TZ ... H .If TMW1 is at position p instead of 1 , we can form a total height of H as per the above ordering. If i could somehow find a turtle with strength that could carry the weight of H turtles i'm increasing the height of the turtle. That means we can still increase our height by ordering by weight if we can find a better turtle.

Ordering by strength.

Maximum Strength(Turtle TMS) at bottom position 1 and total height H.

TMS is at position 1. and the ordering is TMS < TK < TP < TZ ... H .

Here we have something. TMS>= WMS + WK + WP + WZ + .. WH

If TMS is at position p instead of 1 ,we can form a total hieght of H as per above ordering. Can i find a turtle of greater strength than TMS so that it could carry itself + total height H.If it were present say TX, then it can carry WMS + WK + WP +WZ +..WH + WX<=TSX(turtle X's strength) . So contradiction.

maximum height of first i turtles when ordered by increasing order of strength and the corresponding weight Cummulative weight.

Same heights different weights , store lower weights because a good turtle will be able to carry more.

That made me to stop thinking and code below

height[i+1]=1

for(all j <=i)

if(W[i+1]+CW[j]<=TS[i+1]) {
if(h[j]+1>height[i+1]){
height[i+1]=h[j]+1;
CW[i+1]=CW[j] + W[i+1];
}
if(h[j]+1==height[i+1]){
height[i+1]=h[j]+1;
if(CW[i+1]>CW[j]+W[i+1]) CW[i+1]=CW[j] + W[i+1];
}
}

until i found this

101 101
100 201
99 300
98 301
5 302

This approach has a fault with it . Best approach is 2,3,4,5 where as we always do do 1,2.

If turtle 1 can be stacked on turtle 2. we loose any stacking such as 2,3,4,5, because we always say height[2]=2 (since is 1 can be on top 2 ).
So one way to get rid of this is to store the turtles by heights with least weight. Now can i+1 the turtle contribute increasing heights made by i turtles. What is the maximum height.
mw(th,i) = min( mw(th,i-1),mw(th-1,i)+curturtle); This means minimum weight of turtles with height th using first i turtles is mw(th,i) is equal to

minimum of
minimum weight of turtles of height th formed by first i-1 turtles.
minimum weight of turtles of height th-1 formed by SOME i-1 turtles and this current turtle. ( *This is important because the curtutle can only take previous i-1 turtles because it is sorted in increasing order of strength *, had it been not ordered we cannot say whether curturtle can take any of the i-1 turtles. )

You can optimize space seeing that ith height requies only i-1th row. Similar to LCS.

Code: Select all
`#include<cstdio>#include<cmath>#include<cstring>#include<cstdlib>#include<cassert>#include<ctime>#include<algorithm>#include<iterator>#include<iostream>#include<cctype>#include<string>#include<vector>#include<map>#include<set>#include<queue>#include<list>using namespace std;typedef long long lint;typedef unsigned long long ulint;struct turtle{  int w, s;};int n = 0;#define MAX 5700turtle tarr[MAX];int mw[MAX][MAX];booloperator< (const turtle & a, const turtle & b){  if (a.s != b.s)    return a.s < b.s;  return a.w > b.w;}intmain (){  int i = 1, j, a, b;  while (scanf (" %d %d", &a, &b) != EOF)    {      tarr[i].w = a;      tarr[i].s = b;      i++;      n++;    }  sort (tarr+1, tarr + n+1);  int ans = 1, BIG = (1<<30);  for (i = 1; i <= n; i++)  for (j = 0; j <= n; j++)     mw[i][j] = BIG;// printf("n=%d\n",n);  mw[0][0]=0;  for (i = 1; i <= n; i++)    {      for (int h = 1; h <= i; h++)   {          mw[h][i]=mw[h][i-1];     if ((mw[h - 1][i - 1] + tarr[i].w) < tarr[i].s)       mw[h][i] = min(mw[h][i],mw[h - 1][i - 1] + tarr[i].w);     else if ((mw[h - 1][i - 1] + tarr[i].w) == tarr[i].s)       mw[h][i] = min (mw[h][i], mw[h - 1][i - 1] + tarr[i].w);     if (mw[h][i] < BIG) ans = max (ans, h);   }    }  printf ("%d\n", ans);  return 0;}`

tryit1
Experienced poster

Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

### Re: 10154 - Weights and Measures

My code is

Code: Select all
`#include<iostream>#include<cmath>#include<cstdlib>#include<iomanip>#include<string>#include<map>#include<list>#include<queue>#include<stack>using namespace std;class tartaruga {   public :      int weight;   int strength;   int real;   int cont;   int ant;         bool operator<(const tartaruga &e) const{      return weight > e.weight;   }};int compare (const void * a, const void * b){  tartaruga v1 = *(tartaruga*) a;  tartaruga v2 = *(tartaruga*) b;     if (v1.strength != v2.strength){   return v1.strength - v2.strength;    }  else      return v1.weight - v2.weight;       }  int main (){   int x, y;   tartaruga bando[10000];   int ind = 0;   while(cin >> x){      cin >> y;            tartaruga t;      t.weight = x;      t.strength = y;      t.real = x;      t.cont = 1;      bando[ind] = t;      ind++;         }      qsort(bando,ind,sizeof(tartaruga),compare);      /*for (int i = 0; i<ind; i++)      cout << bando[i].weight << " " << bando[i].strength << endl;         cout << endl;*/         for (int i = 0; i<ind; i++){      for (int j = i+1; j<ind; j++){                           if (bando[j].real+bando[i].weight <= bando[j].strength){            if (bando[i].cont + 1 > bando[j].cont){                                 bando[j].cont = bando[i].cont + 1;                  bando[j].ant = i;                  bando[j].real+=bando[i].weight;               }                                             }                  /*for (int e = 0; e<ind; e++){               cout << bando[e].weight << " " << bando[e].strength << " " << bando[e].cont << endl;         }         cout << endl;*/            }   }      int max = 0;   int pmax;      for (int i = 0; i<ind; i++){      if (max < bando[i].cont){         max = bando[i].cont;         pmax = i;      }            }            cout << max << endl;      /*for (int i = 0; i<max; i++){      cout << bando[pmax].weight << " " << bando[pmax].strength << " "<< bando[pmax].real << endl;;      pmax = bando[pmax].ant;      }*/                                    return 0;}`

but i just get WA. Can you help me please??? Maybe any tip or input???
eduardoufv
New poster

Posts: 1
Joined: Sat Jun 19, 2010 2:27 am

### Re:

seogi81 wrote:I used DP

Let me explain my algorithm.

first, sort turtles by strength..

Let, H[n][w] = maximum stack height, using 1'st~n'th turtles.
and total weight is no more than 'w'

H[n][w] =
1 (if n=1 and weight[n] <= w)
0 (if n=1 and weight[n] > w)

this is initialization..

and recursively,

H[n][w] =
max( H[n-1][ min(strength[n] - weight[n], w - weight[n]) ] + 1, H[n-1][w]) (if weight[n] <= w)
H[n-1][w] (if weight[n] > w)

but, it is impossible to make such a big table regarding all possible w( there's not specification about maximum strength of any turtle..)

Space of subproblems seems correctly. I decided to start from the strongest turtle and try to put next one on the top of the stack, so in this case you need dp[i][j] - max height of the stack using first i turtles, when remaining strength (to put other turtles on the top) is >= j. When you limit second dimension by 66100 and make memory optimization dp[2][66100] it is accepted. Probably your approach could be also correct with such limitation. However the best solution was suggested by Adrian Kuegel.

For those of you, who wish to sort by residual strength, consider such an example:
Code: Select all
`1 55 7`
pdwd
New poster

Posts: 19
Joined: Sat May 15, 2010 4:35 pm

### Re: 10154 - Weights and Measures

This problem can be modelled as a scheduling problem. It exists a O(nlogn) greedy algorithm which is better than modified-LIS method mentioned here. See Hodgson's algorithm.
DJWS
Learning poster

Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan

### Re: 10154 - Weights and Measures

I used the greedy approach, but its giving WA :/, I tried all the inputs here on this thread and its all ok. Could anyone post more inputs? Thank you!
Bruno
New poster

Posts: 22
Joined: Thu Oct 01, 2009 9:03 pm

### Re: 10154 - Weights and Measures

stcheung wrote:For kissish's post above:
Sorry , but the answer is not 8.

In my program that got AC,

My AC program (submitted on 10/3/2008) did return 8 for the answer. No offense, but given they have rejudged the submissions, maybe yours is no longer considered AC?

My A.C. program also gives 8.
Have you ever...

Wanted to work at best companies?
Struggled with interview problems that could be solved in 15 minutes?
Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.
DD
Experienced poster

Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California

### Re: 10154 - Weights and Measures

Hi,

Why W.A?
Code: Select all
`#include<iostream>#include<algorithm>#include<vector>using namespace std;struct zolwie   {      int w, m;      zolwie(): w(0), m(0)      {}      zolwie(int _w, int _s): w(_w), m(_s-_w)      {}      bool operator<(zolwie const & ref) const        {            return(m>ref.m);           }   };int main(){   vector<zolwie> tab;    long liczba1, liczba2;   bool ok = true;   while (cin >> liczba1 >> liczba2)   {      tab.push_back(zolwie(liczba1, liczba2));   }      int ilosc = 1;   sort(tab.begin(), tab.end());   for(int j= 1; j<tab.size(); j++)   {      if(tab[j].w<=tab[j-1].m&&tab[j].w<=tab[0].m)      {         for(int k= j-2; k>=0; k--)         {            if(tab[j].w>tab[k].m)            {               ok = false;               tab.erase(tab.begin() + j);               break;            }         }         if(ok)         {            for(int k= j-2; k>=0; k--)               tab[k].m-=tab[j].w;            tab[j-1].m-=tab[j].w;            ilosc++;         }         ok = true;      }      else      {         tab.erase(tab.begin() + j);         j--;      }   }      cout << ilosc;      //system("pause");   return 0;}`
Leo66
New poster

Posts: 2
Joined: Sun May 01, 2011 5:11 pm

### Re: 10154 - Weights and Measures

hi
plz give me a compeleted code for this problem
i need this
ok
plz help me
i most send this for my teacher if i do not this
then i ....
tank you
New poster

Posts: 1
Joined: Sat Jul 07, 2012 11:27 am

### Re: 10154 - Weights and Measures

I hav tried all the critical inputs given in ths forum and got correct answers for all.... my algo uses DP(not exactly LIS, actually quite different from it)...
m quite sure tht my algo is correct... m missing somethng silly(either silly inputs or some output format)... tried debugging a lot... couldnt find nythng... if ny1 can plz help me, i ll b highly grateful...
Here's my code:
Code: Select all
`#include<iostream>using namespace std;int pile_weight=0; int largest_stack(int weight[],int capacity[],int n,int maximum,int pos){      int dp[6000]={0};      bool included[6000]={0};      dp[1]=maximum;included[pos]=1;/*initializing the sequence*/       int i=1,j,max,position,current_capacity,flag=0,stack_pos=0,next_weight,top=0,bottom=0;       while(dp[i]>=0)      {            i++;max=-250000;position=-1;            for(j=1;j<=n;j++)            {                  if(included[j]==0)                  {                        top=capacity[j]<dp[i-1]-weight[j]?capacity[j]:dp[i-1]-weight[j];                        bottom=capacity[j]-pile_weight<dp[i-1]?capacity[j]-pile_weight:dp[i-1];                        current_capacity=top>bottom?top:bottom;                        if(max<current_capacity)                        {                              max=current_capacity;                              position=j;                              next_weight=weight[j];                        }                  }            }            pile_weight+=next_weight;            dp[i]=max;            included[position]=1;      }      return(i-1);} int main(){      int wt[6000],strength[6000],capacity[6000];      int i=1,max=-250000,max_length,pos;       while(cin>>wt[i]>>strength[i])      {            capacity[i]=strength[i]-wt[i];            if(max<capacity[i])            {                  max=capacity[i];                  pos=i;                  pile_weight=wt[i];            }            i++;      }       max_length=largest_stack(wt,capacity,i-1,max,pos);      cout<<max_length;       return 0;}`
37squared
New poster

Posts: 6
Joined: Sun Sep 16, 2012 4:15 pm

### Re: 10154 - Weights and Measures

Print a newline at the end of the output. For this input:
Code: Select all
`384 1271778 1694794 1130387 880650 1072363 391691 751764 1691541 968173 910`
AC output is 4
brianfry713
Guru

Posts: 1870
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Previous