10154 - Weights and Measures

[Igor9669]

Please tell me what's wrong???
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;
}

[tryit1]

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 5700
turtle tarr[MAX];
int mw[MAX][MAX];

bool
operator< (const turtle & a, const turtle & b)
{
  if (a.s != b.s)
    return a.s < b.s;
  return a.w > b.w;
}

int
main ()
{
  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;
}


[eduardoufv]

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???

[pdwd]

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 5
5 7


[DJWS]

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.

[Bruno]

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!

[DD]

For kissish's post above:

Sorry , but the answer is not 8.


In my program that got AC,

the answer is 7.

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.

[Leo66]

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;
}

[ghadir]

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

[37squared]

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;
}

[brianfry713]

Print a newline at the end of the output. For this input:

Code: Select all

384 1271
778 1694
794 1130
387 880
650 1072
363 391
691 751
764 1691
541 968
173 910

AC output is 4