Posted:

**Wed May 11, 2005 6:02 am**you can't put [3 40] and [10 500] on [20 30] because the turtle [20 30] has only 10 remain strength

Page **3** of **5**

Posted: **Wed May 11, 2005 6:02 am**

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

Posted: **Sat Aug 20, 2005 5:33 am**

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

Posted: **Sat Aug 20, 2005 7:52 am**

there has been enough discussion on this problem made already:

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

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

Posted: **Sun Dec 04, 2005 3:37 pm**

Sorry , but the answer is not 8.Red Scorpion wrote: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

In my program that got AC,

the answer is 7.

p.s sorry my poor English.

Posted: **Mon Feb 06, 2006 4:00 pm**

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

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

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

Posted: **Sat Jun 03, 2006 11:17 am**

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:

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

Posted: **Tue Nov 07, 2006 2:25 am**

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 */

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

throne[i++].weight = w;

}

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

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

return 0;

}

/* @END_OF_SOURCE_CODE */

Posted: **Thu Nov 16, 2006 9:25 pm**

Anyone? please! I need your help!

thx.

thx.

Posted: **Mon Jul 23, 2007 3:25 pm**

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

Posted: **Thu Jul 26, 2007 7:27 pm**

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!

Thank you!

Posted: **Fri Mar 21, 2008 6:11 am**

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:

I appreciate your help!

Thanks.

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

Let p

Now, suppose I want to find dp

Notice that dp

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

Thanks.

Posted: **Sun Jun 22, 2008 8:37 am**

How can I calculate the minimum weight that a stack of k turtles has? Is this something like Kadane's algorithm?Adrian Kuegel wrote: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.

Posted: **Sun Aug 31, 2008 7:02 am**

Plz Help I always get WA.

I 've redden all this thread and made all what you said I can't solve it.

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());
}
```

Posted: **Fri Oct 03, 2008 10:23 am**

For kissish's post above:

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?Sorry , but the answer is not 8.

In my program that got AC,

the answer is 7.

Posted: **Fri Oct 03, 2008 10:42 am**

To Alisaleh:

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

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.Plz Help I always get WA.

I 've redden all this thread and made all what you said I can't solve it.

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