10154 - Weights and Measures

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

vina
New poster
Posts: 1
Joined: Wed May 11, 2005 5:57 am

Post by vina » 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 :)
======================
O<-< ~~~
======================

Jeff
New poster
Posts: 7
Joined: Mon May 02, 2005 5:39 pm

10154 WA

Post by Jeff » 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;
	}

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Post by jagadish » 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
if u can think of it .. u can do it in software.

kissksh
New poster
Posts: 3
Joined: Sat Sep 24, 2005 10:11 am
Contact:

....

Post by kissksh » Sun Dec 04, 2005 3:37 pm

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


In my program that got AC,

the answer is 7.




p.s sorry my poor English.

seogi81
New poster
Posts: 2
Joined: Mon Feb 06, 2006 3:24 pm
Location: Korea

Post by seogi81 » 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..)

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
New poster
Posts: 31
Joined: Sat Apr 01, 2006 6:24 am
Contact:

getting WA

Post by Ankur Jaiswal » 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:

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
New poster
Posts: 2
Joined: Tue Nov 07, 2006 1:59 am

10154 gots WA, help please!

Post by appdnails » 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 */

appdnails
New poster
Posts: 2
Joined: Tue Nov 07, 2006 1:59 am

Post by appdnails » Thu Nov 16, 2006 9:25 pm

Anyone? please! I need your help!

thx.

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes » Mon Jul 23, 2007 3:25 pm

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

User avatar
ferrizzi
New poster
Posts: 23
Joined: Thu Mar 30, 2006 5:42 pm
Location: Brazil

Post by ferrizzi » 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!
Regards,
[]'s
Andre

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Post by andmej » 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:

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.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re:

Post by andmej » Sun Jun 22, 2008 8:37 am

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.
How can I calculate the minimum weight that a stack of k turtles has? Is this something like Kadane's algorithm?
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

AliSaleh
New poster
Posts: 2
Joined: Fri May 25, 2007 10:08 pm
Location: Egypt
Contact:

Re: 10154 - Weights and Measures

Post by AliSaleh » 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.

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
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Re: 10154 - Weights and Measures

Post by stcheung » Fri Oct 03, 2008 10:23 am

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
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Re: 10154 - Weights and Measures

Post by stcheung » Fri Oct 03, 2008 10:42 am

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.

Post Reply

Return to “Volume 101 (10100-10199)”