11003 - Boxes

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

Moderator: Board moderators

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

11003 - Boxes

Post by sds1100 » Fri Mar 24, 2006 4:19 pm

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
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » 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
Where's the "Any" key?

Rafski
New poster
Posts: 1
Joined: Sun Apr 02, 2006 11:13 am
Location: Earth :)

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

Fixxxer
New poster
Posts: 5
Joined: Tue Aug 30, 2005 6:20 pm

Post by Fixxxer » 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 :wink:
can anyone give any hint

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Wed Apr 05, 2006 12:35 am

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

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » Thu Apr 20, 2006 11:47 pm

i have solved this problem using DP with O(n^3) algorithm , but i got TLE :cry:
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

Post by Timo » Fri Apr 21, 2006 9:31 am

Hi arsalan_mousavian :D

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.

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

Post by jan_holmes » Sun Apr 23, 2006 11:31 am

Please Help !!! Got 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

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

:D

"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

Post by jan_holmes » Mon Apr 24, 2006 1:53 pm

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

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » Thu May 11, 2006 10:11 pm

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.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » 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

2
2000 2000
2000 2000
0
The correct answer is

Code: Select all

2

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » 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

 2
800 800
800 800
0
thanks in advance

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

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

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » Sun May 21, 2006 6:49 pm

thanks a lot , i got AC :lol:

Post Reply

Return to “Volume 110 (11000-11099)”