11003 - Boxes

[sds1100]

Why WA.
I don't know
please help

Code: Select all

#include <fstream.h>
int a[10001][2],max,max2,idx,data[10001][2];
void main(){
	int n,i,j;
	cin >> n;
	for(i=n-1;i>=0;i--)cin >> a[i][0] >> a[i][1];
	data[0][0]=a[0][0];data[0][1]=1;
	for(i=1;i<n;i++){
		max=0;max2=0;
		for(j=0;j<i;j++){
			if(a[i][1]>=data[j][0]&&max<data[j][1]){
				max=data[j][1];
				max2=data[j][0];
			}
		}
		data[i][0]=a[i][0]+max2;
		data[i][1]=max+1;
	}
	max=max2=0;
	for(i=0;i<n;i++)if(data[i][0]>max)max=data[i][1];
	cout << max << endl;
}

[Solaris]

The first line of each set of input is an integer N (1 ≤ N ≤ 1000). This is followed by N lines, each with two integers, both ≤ 3000, representing the weight and maximum load of each box respectively.

Input ends with a case where N = 0.

There can be multiple input sets. I am not sure whether your code handles that. After you edit your code to take multiple sets .. test with the following Input:

5
19 15
7 13
5 7
6 8
1 2
5
19 20
21 50
20 40
20 40
5 5
0

Output:

4
4

[Rafski]

I'm getting WA and I don't know what's wrong with my approach. Maybe I didn't think about some tricky case. Please take a look at my code

Code: Select all

    const int N = 1000;
    int n;
    int weight[N];
    int load[N];
    int bestSumWeight[N]; // bestSumWeight[i] - weight of highest tower
                          // built from boxes [1..i-1] + weight[i]
    int bestSumHeight[N]; // height of highest tower from boxes [1..i-1] + 1
    while( scanf("%d", &n) == 1 && n != 0 ) {
        for(int i = n-1; i >= 0; --i)
            scanf("%d %d", &weight[i], &load[i]);

        bestSumWeight[0] = weight[0];
        bestSumHeight[0] = 1;
        for(int i = 1; i < n; ++i) {
            int bestW = 0;
            int bestH = 0;
            //find highest tower from boxes [0..i-1] with weight <= load[i]
            for(int j = i-1; j >= 0; --j) {
                if( bestSumWeight[j] <= load[i] ) {
                    if( (bestSumHeight[j] > bestH) ||
                        (bestSumHeight[j] == bestH && bestSumWeight[j] < bestW) ) {
                        bestH = bestSumHeight[j];
                        bestW = bestSumWeight[j];
                    }
                }
            }
            bestSumWeight[i] = bestW + weight[i];
            bestSumHeight[i] = bestH + 1;
        }
        printf("%d\n", *max_element(bestSumHeight, bestSumHeight+n));
    }

Thanks in advance

[Fixxxer]

Consider following case

5
2 10
2 10
2 21
20 1
1 2

output should be 4

anyway i used memoization but got TLE
can anyone give any hint

[sclo]

If you defined the correct function to do the dp on, it is not going to TLE

[arsalan_mousavian]

i have solved this problem using DP with O(n^3) algorithm , but i got TLE
can someone give me a Hint plz ?
Thanks in Advance . . .

[Timo]

Hi arsalan_mousavian

This problem very similiar with Knapsack Problem.
In Knapsack Problem we want maximum profit that we can take, but in this
problem we want maximum box that we can take.

I will describe to you my algo

let's we define:

best(i,j) -> the maximum box that I can take from the first i box with j maximum loading.

the base case is :
best(1,maxLoad[1]) = 1
best(2,maxLoad[2]) = 1
.
.
.
best(n,maxLoad[n]) = 1

after that you can create two loop to fill the table best(i,j)
the final answer is the maximum from [best(n,0)...best(n,3000)]

if best(i-1,j) >0 then
{
// if we choose to take the box
if(j-weight>=0) then
{
k=min(maxLoad,j-weight)
best(i,k) = max(best(i,k) , best(i,j) )
}

// if we choose to not take the box
best(i,j) = max(best(i,j) , best(i-1,j) )
}

I hope you understand my algo.
Sorry for my poor English.
The runtime for my algo only O(3000*n), you should get AC with this.

[jan_holmes]

Please Help !!! Got WA here :

Code: Select all

ACed...

[Timo]

Code: Select all

code removed...
 

I have change a little part of your code.
This one should be AC.



"sorry jan_holmes topik yg aku post sebelumnya ada kesalahan sedikit,
gara2 aku kamu jadi dapet WA, thanx untuk koreksi yang kamu berikan, manusia tidak luput dari kesalahan"

[jan_holmes]

ok,Timo... Thx banget yah !!!!

[arsalan_mousavian]

i don't know why i got WA ,

Code: Select all

// code removed 

[Martin Macko]

i don't know why i got WA ,

Your solution's not working for

Code: Select all

2
2000 2000
2000 2000
0

The correct answer is

Code: Select all

2

[arsalan_mousavian]

i don't know why i got WA ,

Your solution's not working for

Code: Select all

2
2000 2000
2000 2000
0

The correct answer is

Code: Select all

2

would you please tell me why this happens , because it gives the right output
for the case :

Code: Select all

 2
800 800
800 800
0

thanks in advance

[Martin Macko]

would you please tell me why this happens , because it gives the right output
for the case:...

Small hint: maximum tower weight may be higher than 3000. Read the problem statement more carefully.

[arsalan_mousavian]

thanks a lot , i got AC