10154 - Weights and Measures

[vina]

you can't put [3 40] and [10 500] on [20 30] because the turtle [20 30] has only 10 remain strength

[Jeff]

I don't know why....

Code: Select all

#include<stdio.h>
#include<stdlib.h>
	int all;
	int table[5608];
	typedef struct wei
	{
		int self,other;
	}ori;
	ori ary[5608];
	int comp(void const *a,void const *b)
	{
		return (*(ori*)a).other-(*(ori*)b).other;
	}
	int in()
	{
		all=0;
		while(scanf("%d %d",&ary[all].self,&ary[all].other)==2)
		{
			ary[all].other-=ary[all].self;
			all++;
		}
		qsort(ary,all,sizeof(ori),comp);
		return 0;
	}
	int lis()
	{
		int i,n=0,wei,j;
		for(i=0;i<all;i++)
		{
			wei=0;
			for(j=0;j<n;j++)
			{
				wei+=table[j];
				if(ary[i].other<wei)
					break;
			}
			if(j==n)
				table[n++]=ary[i].self;
			else if(ary[i].self<table[j])
				table[j]=ary[i].self;
		}
		return n;
	}
	int main()
	{
		in();
		printf("%d\n",lis());
		return 0;
	}

[jagadish]

there has been enough discussion on this problem made already:

http://online-judge.uva.es/board/viewto ... 2&start=15

[kissksh]

try this

100 101
200 300
10 500
1 1000
20 30
40 40
500 901
152 199
1 2
3 40
2 1000

output:
8

Sorry , but the answer is not 8.


In my program that got AC,

the answer is 7.




p.s sorry my poor English.

[seogi81]

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..)

so i used STL map( map< pair<int, int>, int > )
pair<int, int> means (n,w), and i used top-down approach with memoization..

it didn't get TLE, but WA..
i think it means my method isn't time-critical.

i tested all the sample input above..
is my method wrong?? could anybody help me?

sorry about my poor english...

and this is my sample input already sorted by strength( and i think it is a critical sample..)

Code: Select all

1     2
20   21
3     24
2     26
1     27
1     27
2     27

and my answer is 6 ( 1,3,4,5,6,7 or 1,2,4,5,6,7)

[Ankur Jaiswal]

I am first sorting the input by strength and then by weight.
Then i am calculating their difference, followed by LIS on the difference.
Is this algo wrong??
If yes , where?
here's my code:

Code: Select all

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef struct t{
        int w;
        int s;
}turtles;
bool compare(turtles a, turtles b){
        if(a.s<b.s)
                return true;
        if(a.s==b.s && a.w<b.w)
                return true;
        return false;
}
int main(){
        turtles arr[5607];
        int i,j,k,max;
        int diff[5607],l[5607];
        i=0;
        while(scanf("%d%d",&arr[i].w,&arr[i].s)!=EOF)
                i++;
        sort(arr,arr+i,compare);
        for(j=0;j<i;j++){
                printf("%d %d\n",arr[j].s,arr[j].w);
                diff[j]=arr[j].s-arr[j].w;
                l[j]=1;
        }
        for(j=0;j<i-1;j++)
                for(k=j+1;k<i;k++)
                        if(diff[k]>diff[j])
                                if(l[j]+1 > l[k])
                                        l[k]=l[j]+1;
        max=0;
        for(j=0;j<i;j++)
                if(max<l[j])
                        max=l[j];
        printf("%d\n",max);
        return 0;
}

[appdnails]

I don't understand, I tested several critical cases (including all in this forum) and all of them give me the correct answer, but UVA insists in giving me WA.

Let's explain my algo:
First I sort the turtles in increasing order of the strength , them I compare their weights one per one, from top to bottom. That is, first I compare the top turtle with all the other turtles, them I compare the second, them the third...,
and at the same time I update the weight of the tower. The answer is the largest tower that I can do.
For example:
Input:
100 1000
10 100
1 10

sorting:
1 10
10 100
100 1000

comparing:
1 + 10 < 100, them the tower have at least lenght 2, but
1 + 10 + 100 < 1000, them the tower have lenght 3.

I can't find where is the error, can anyone help me?

Here is my code:

/* @BEGIN_OF_SOURCE_CODE */

#include <stdio.h>

#include <stdlib.h>

/* @JUDGE_ID: xxxxxxx 10154 C "" */

struct turtle {
int strength;

int weight;

};


int cmp (const void *a, const void *b)

{

struct turtle *s1 = (struct turtle *) a;

struct turtle *s2 = (struct turtle *) b;


return(s1->strength > s2->strength);
}



int yertle(struct turtle throne2[], int N)

{

int j, t, totalweight=0;
int *lenght = (int *) malloc(N*sizeof(int));

/* Just to verify if the weight is greater than strength */
for (j=0; j<N; j++)
if (throne2[j].weight > throne2[j].strength)
lenght[j] = 0;
else
lenght[j] = 1;


for (j=0; j<N-1; j++)
{
totalweight = throne2[j].weight;

for (t=j+1; t<N; t++)
{
if (totalweight+throne2[t].weight < throne2[t].strength)
{
totalweight+=throne2[t].weight;
lenght[j]++;
}
else if (totalweight+throne2[t].weight == throne2[t].strength)
{
lenght[j]++;
break;
}
}
}

t=0;
for (j=0; j<N; j++)
if (t < lenght[j])
t = lenght[j];
free(lenght);
return (t);

}



int main()

{

int i=0, w, s;

struct turtle throne[5608];


while (scanf("%d %d", &w, &s) == 2)

{

throne.strength = s;
throne[i++].weight = w;

}

qsort( throne, i, sizeof(struct turtle), cmp);

printf("max = %d\n", yertle(throne, i));

return 0;

}
/* @END_OF_SOURCE_CODE */

[appdnails]

Anyone? please! I need your help!

thx.

[jan_holmes]

EDIT : ACed... I was just assumed that the stack is not more than 1000.

[ferrizzi]

I did this problem using LIS but I get WA. I saw on board that LIS/Greedy based solutions don't work anymore. Could someone that solved this problem using another approach tell me some hints?
Thank you!

[andmej]

Can you explain me what is wrong with my approach? I'm getting Wrong Answer.

Here's an explanation of my dynamic programming algorithm:

First I sort the turtles by strength - weight, from bigger to smaller (That is, the first turtle is the one who can carry the most "real" weight on his back).

Let dp be the maximum number of turtles I can stack such that the i'th turtle is on top.
Let p be the maximum weight that can be stacked over the optimal dp turtles.

Now, suppose I want to find dp with dp[j] and p[j] found for all j between 0 and i (That is, I know the best way of stacking the turtles such that any turtle less than the i'th turtle is on top).

Notice that dp is at least 1 (the i'th turtle alone) and p is at least turtle i'th strength - weight. Then I only have to check if I can stack the i'th turtle on top of the j'th smaller turtle, for j < i, and take the maximum of all these values. I can only stack turtle i'th on top of turtle j'th if the weight of i is less than p[j]. If I can stack it, then the new p will be the minimum between: (p[j] - weight) and (strength - weight).
That is, the new stack will be able to support either what it already could support minus the weight of the new turtle or only what the new turtle can support.

Here's my code:

Code: Select all

#include <vector>
#include <algorithm>
#include <iostream>
#include <cassert>

using namespace std;

struct turtle{
  int w,s;
  turtle(int W, int S) : w(W), s(S) {}
  bool operator < (const turtle &y) const{
    return (s - w < y.s - y.w) ||
      (s - w == y.s - y.w && w < y.w) ||
      (s - w == y.s - y.w && w == y.w && y.s < y.w);
  }
  bool operator == (const turtle &y) const{return w == y.w && s == y.s;}
};
bool operator > (const turtle &x, const turtle &y){return !(x == y) && !(x < y);}

int main(){
  vector<turtle> t;
  int x, y;
  while (cin >> x >> y){
    assert(x <= y);
    t.push_back(turtle(x,y));
  }
  sort(t.begin(), t.end(), greater<turtle>() );

  vector<int> p(t.size()), dp(t.size());
  for (int i=0; i<t.size(); ++i){
    dp[i] = 1;
    p[i] = t[i].s - t[i].w;
    for (int j=0; j<i; ++j){
      if (t[i].w <= p[j]){
        if (dp[i] < dp[j] + 1){
          dp[i] = dp[j] + 1;
          p[i] = min(p[j] - t[i].w, t[i].s - t[i].w);
        }
      }
    }
  }
  cout << *(max_element(dp.begin(), dp.end())) << endl;
  return 0;
}

I appreciate your help!

Thanks.

[andmej]

I am not sure if your greedy is correct. At first I got Accepted with a greedy algorithm, for which I found a counter example.
Here is the correct way how to solve the problem:
First, you can sort by strength. Prove:
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.
Now you can use DP: 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) or else mw(i,k) = mw(i-1,k). Answer is maximum k with mw(n,k)<infinity.

How can I calculate the minimum weight that a stack of k turtles has? Is this something like Kadane's algorithm?

[AliSaleh]

Plz Help I always get WA.
I 've redden all this thread and made all what you said I can't solve it.

Code: Select all

#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define max 5650

struct element{
	int weight;
	int stren;
};
element sorted[max];

int LIS(int count);
int comp(const void *X,const void *Y){
	const element *x=(const element *)X;
	const element *y=(const element *)Y;

	if(x->stren<y->stren)
                return false;
        if(x->stren==y->stren && x->weight<y->weight)
                return false;
        return true;
}

int main()
{
	element temp;	
	int i;

	for(i=0;;i++){
		cin>>temp.weight;
		if(cin.eof())
			break;
		cin>>temp.stren;		
		sorted[i]=temp;
	}
	qsort(sorted,i,sizeof(element),comp);
	cout<<LIS(i)<<endl;
	return 0;
}

int LIS(int count){
   vector<int> best(count,1);
   for(int i=0;i<count;i++){      
      for(int j=0;j<=i-1;j++)
		  if ( sorted[i].stren > sorted[j].stren )
			  best[i] = (best[i]>best[j]+1)? best[i]:best[j]+1;
		  else if(sorted[i].stren == sorted[j].stren)
			  if(sorted[i].weight > sorted[j].weight)
				  best[i] = (best[i]>best[j]+1)? best[i]:best[j]+1;
   }
   return *max_element(best.begin(),best.end());
}

[stcheung]

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?

[stcheung]

To Alisaleh:

Plz Help I always get WA.
I 've redden all this thread and made all what you said I can't solve it.

Perhaps you stopped reading in the middle Basically you are treating it as LIS too literally. And it doesn't even look close. As Adrian pointed out, this might actually not be a LIS problem after all, even though it looks similiar enough. Anyways, I suggest you reread the problem description first. Keep in mind that a turtle has to support the weight of all the turtles above him, which I don't really see in your code. Then try solving it with Adrian's DP approach instead. His post is on the 2nd page and contains the following recurrence formula.

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)
or else mw(i,k) = mw(i-1,k).
Answer is maximum k with mw(n,k)<infinity.

By the way, you probably will run into memory limit issue like I did if you simply use a double array to store the mw[k] above. Just keep in mind that at any given step, you only need the mw values for i-1.