## 11003 - Boxes

Moderator: Board moderators

sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm

### 11003 - Boxes

Why WA.
I don't know

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
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Contact:
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
Where's the "Any" key?

Rafski
New poster
Posts: 1
Joined: Sun Apr 02, 2006 11:13 am
Location: Earth :)
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 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)

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

Fixxxer
New poster
Posts: 5
Joined: Tue Aug 30, 2005 6:20 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

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
If you defined the correct function to do the dp on, it is not going to TLE

arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:
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
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia
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 :
.
.
.

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

Last edited by Timo on Mon Apr 24, 2006 6:43 am, edited 1 time in total.
"Life is more beautiful with algorithm"

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

### WA here...

Code: Select all

``````ACed...
``````
Last edited by jan_holmes on Tue Apr 25, 2006 1:01 pm, edited 1 time in total.

Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia

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"
Last edited by Timo on Tue Apr 25, 2006 4:07 am, edited 1 time in total.
"Life is more beautiful with algorithm"

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

### Thx !!! :D

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

arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:
i don't know why i got WA ,

Code: Select all

``````// code removed
``````
Last edited by arsalan_mousavian on Sun May 21, 2006 6:47 pm, edited 1 time in total.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
arsalan_mousavian wrote:i don't know why i got WA ,

Code: Select all

``````2
2000 2000
2000 2000
0``````

Code: Select all

``2``

arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:
Martin Macko wrote:
arsalan_mousavian wrote:i don't know why i got WA ,

Code: Select all

``````2
2000 2000
2000 2000
0``````

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

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
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.

arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:
thanks a lot , i got AC