## 11100 - The Trip, 2007

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

Moderator: Board moderators

SamuraiShaz
New poster
Posts: 9
Joined: Mon Feb 21, 2005 10:42 am
Location: Dhaka

### 11100 - The Trip, 2007

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

Sharing a bit of knowledge takes you one step closer to immortality!

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain
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
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:
btw , what could be the least no. of bags.........

once u find that the rest involves filling each bag one by one....
If I will myself do hashing, then who will do coding !!!

samsayyah
New poster
Posts: 1
Joined: Sat Aug 19, 2006 6:27 pm
Thank you!
Last edited by samsayyah on Wed Sep 27, 2006 11:44 am, edited 1 time in total.

subbu
New poster
Posts: 28
Joined: Fri May 30, 2003 12:47 am
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
New poster
Posts: 2
Joined: Sat Jan 21, 2006 7:36 pm
Can somebody give me some test cast , please~

mysword
New poster
Posts: 26
Joined: Sun Mar 06, 2005 8:52 am
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....

smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am
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...
fahim
#include <smile.h>

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET
smilitude wrote: But i guess this is the way to find how many least bag we need, then just fill out...
no LIS needed.

smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am
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..
fahim
#include <smile.h>

erictwpt
New poster
Posts: 6
Joined: Mon Oct 10, 2005 5:13 am
Location: Taiwan
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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
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..

Code: Select all

``````4
1 2 3
1 2 3
1 3
2 3
``````
Did you check Emilio's test case..?

erictwpt
New poster
Posts: 6
Joined: Mon Oct 10, 2005 5:13 am
Location: Taiwan
helloneo wrote: 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.

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

New poster
Posts: 27
Joined: Sun Feb 18, 2007 2:14 pm

### i, 11100

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
New poster
Posts: 11
Joined: Tue May 22, 2007 10:09 pm
Location: India
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!!!!