OJ Board

Posted: **Fri Mar 24, 2006 4:19 pm**

Why WA.
I don't know
please help

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

Posted: **Fri Mar 24, 2006 5:28 pm**

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

Posted: **Sun Apr 02, 2006 12:27 pm**

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

Posted: **Tue Apr 04, 2006 11:05 pm**

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

Posted: **Wed Apr 05, 2006 12:35 am**

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

Posted: **Thu Apr 20, 2006 11:47 pm**

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

Posted: **Fri Apr 21, 2006 9:31 am**

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.

Posted: **Sun Apr 23, 2006 11:31 am**

Please Help !!! Got WA here :

Code: Select all

ACed...

Posted: **Mon Apr 24, 2006 6:50 am**

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"

Posted: **Mon Apr 24, 2006 1:53 pm**

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

Posted: **Thu May 11, 2006 10:11 pm**

i don't know why i got WA ,

Code: Select all

// code removed

Posted: **Sat May 20, 2006 10:06 pm**

arsalan_mousavian wrote:i don't know why i got WA ,

Your solution's not working for

Code: Select all

The correct answer is

Code: Select all

Posted: **Sun May 21, 2006 5:47 pm**

Martin Macko wrote:
arsalan_mousavian wrote: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

thanks in advance

Posted: **Sun May 21, 2006 6:15 pm**

arsalan_mousavian wrote: 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.

Posted: **Sun May 21, 2006 6:49 pm**

thanks a lot , i got AC

OJ Board

11003 - Boxes

11003 - Boxes

WA here...

Thx !!! :D