Page 1 of 2
11100 - The Trip, 2007
Posted: Mon Sep 25, 2006 9:26 pm
by SamuraiShaz
how can it be solved (which algorithm)??? there is a lot of output with same results?? what are the tricks in it??
The bags are all exactly the same shape and differ only in their linear dimension which is a positive integer not exceeding 1000000. A bag with smaller dimension will fit in one with larger dimension. You are to compute which bags to pack within which others so as to minimize the overall number of pieces of luggage (i.e. the number of outermost bags). While maintaining the minimal number of pieces you are also to minimize the total number of bags in any one piece that must be carried.
Does this problem statements mean that one need to find the minimum outer bags and as well as minimum inner bags, right??
Posted: Mon Sep 25, 2006 10:16 pm
by Emilio
I solved using a simple straightforward algorithm. You don't need any special algorithm.
Yeah, there are lot of correct outputs.
There are no tricks.
About your question about the problem statement, you must find wich is the smallest number of outermost bags. But the bag that have more bags inside itself must have as few as possible.
For example:
4
1 1 2 3
A correct result is:
1 2
1 3
You could make 2 bags in another manner:
1 2 3
1
but this one is not correct, for the problem specification.
Hope it helps!
Posted: Tue Sep 26, 2006 4:08 am
by vinay
btw , what could be the least no. of bags.........
once u find that the rest involves filling each bag one by one....
Posted: Tue Sep 26, 2006 8:21 pm
by samsayyah
Thank you!
Posted: Tue Sep 26, 2006 8:30 pm
by subbu
Your "max" calculation seems to be flawed.
The "max" variable will not be correct if the maximum value of counter occurs at the end of the array.
For example
on example
4
1 1 1 1
IIUC, max will be 1 according to your code; and not 4 as it should be.
Posted: Mon Oct 23, 2006 5:01 pm
by ckm111
Can somebody give me some test cast , please~
Posted: Wed Oct 25, 2006 10:22 am
by mysword
how to comupte the least no. of bags efficiently?
vinay wrote:btw , what could be the least no. of bags.........
once u find that the rest involves filling each bag one by one....
Posted: Sun Nov 12, 2006 6:46 pm
by smilitude
when i read the problem statement, i sensed a soln with LIS, like i have the array, then i would do an LIS, then omit those on the LIS LIST from the array, then run LIS again, until there is no element left - then print out the lists one by one... but after thinking about
4
1 1 2 3
A correct result is:
1 2
1 3
You could make 2 bags in another manner:
1 2 3
1
this wont work anymore...
But i guess this is the way to find how many least bag we need, then just fill out...
Posted: Sun Nov 12, 2006 8:43 pm
by sunny
smilitude wrote:
But i guess this is the way to find how many least bag we need, then just fill out...
no LIS needed.
Posted: Tue Nov 14, 2006 9:51 am
by smilitude
maybe!
but you can solve one problem in different ways.. my one got accepted using that LIS way.. LIS turns to be very simple when you can sort an array..
Posted: Sun Dec 10, 2006 5:18 pm
by erictwpt
I got lots of WAs...
Is this answer correct?
INPUT
10
1 1 1 2 2 2 3 3 3 3
OUTPUT
4
1 2 3
1 2 3
1 2 3
3
Thank you all!
Posted: Sun Dec 10, 2006 5:31 pm
by helloneo
erictwpt wrote:I got lots of WAs...
Is this answer correct?
INPUT
10
1 1 1 2 2 2 3 3 3 3
OUTPUT
4
1 2 3
1 2 3
1 2 3
3
Thank you all!
I guess your output is ok..
But I think the output should be more like..
Did you check Emilio's test case..?
Posted: Sun Dec 10, 2006 5:42 pm
by erictwpt
helloneo wrote:
I guess your output is ok..
But I think the output should be more like..
Did you check Emilio's test case..?
Yes I did, and I got the correct output.
Here are another I/O and i am not sure if the first one is correct.
Thank you for your reply.
Code: Select all
INPUT
10
1 1 1 2 2 2 3 3 4 4
10
1 1 1 1 1 2 3 4 5 6
Code: Select all
OUTPUT
3
1 2 3 4
1 2 3 4
1 2
5
1 2
1 3
1 4
1 5
1 6
i,
11100
Posted: Sun Feb 18, 2007 2:42 pm
by pvncad
hii,
I tried solving this using following logic.
1. sort the array
2. find the max number of repitation.( we require this many bags}
3. then, print the list
for (i = 0; i < min_bags; i ++) {
for(j = i ; j < n; j += min_bags)
printf("%d", bags[j]);
printf("\n");
}
i got WA for this, but it was able to solve testcases mentioned here
Could you please let me know where I am doing worng
thanks
Posted: Sun Jun 24, 2007 10:26 pm
by ankit.arora
hi! I am getting WA can anyone please help me out..... here's my code!
Code: Select all
#include<iostream>
using namespace std;
int main()
{
int n,i,j,count,max,temp,prev;
int arr[10010];
while(cin>>n)
{
if(n==0)
break;
for(i=0;i<n;i++)
cin>>arr[i];
for(i=0;i<n;i++)
{
for(j=i;j<n;j++)
{
if(arr[i]>arr[j])
{
temp=arr[j];
arr[j]=arr[i];
arr[i]=temp;
}
}
}
max=1;
count=1;
for(i=1;i<n;i++)
{
if(arr[i-1]==arr[i])
count++;
else if(count>max)
{
max=count;
count=1;
}
else
count=1;
}
cout<<max<<"\n";
for(i=0;i<max;i++)
{
cout<<arr[i];
for(j=i+max;j<n;j+=max)
cout<<" "<<arr[j];
cout<<"\n";
}
cout<<"\n";
}
}
Thanks!!!!