11100 - The Trip, 2007

[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??

[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!

[vinay]

btw , what could be the least no. of bags.........

once u find that the rest involves filling each bag one by one....

[samsayyah]

Thank you!

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

[ckm111]

Can somebody give me some test cast , please~

[mysword]

how to comupte the least no. of bags efficiently?

btw , what could be the least no. of bags.........

once u find that the rest involves filling each bag one by one....

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

[sunny]

But i guess this is the way to find how many least bag we need, then just fill out...

no LIS needed.

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

[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!

[helloneo]

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

Code: Select all

4
1 2 3
1 2 3
1 3
2 3

Did you check Emilio's test case..?

[erictwpt]

I guess your output is ok..
But I think the output should be more like..

Code: Select all

4
1 2 3
1 2 3
1 3
2 3

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

[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

[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!!!!