## 11045 - My T-shirt suits me

Moderator: Board moderators

Ankur Jaiswal
New poster
Posts: 31
Joined: Sat Apr 01, 2006 6:24 am
Contact:

### 11045 - My T-shirt suits me

What is the approach to solve this problem??
Is it simple backtracking or is there some trick?
People have solved it in very less time.
So i guess there might be some trick.

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

### Re: 11045 How to solve?

Ankur Jaiswal wrote:What is the approach to solve this problem??
Is it simple backtracking or is there some trick?
People have solved it in very less time.
So i guess there might be some trick.
there is no trick in this problem .
studying @ ntu csie

rammestain
New poster
Posts: 18
Joined: Fri Apr 21, 2006 11:34 am
I tried to solve this problem with dynamic programming but got TLE,
Is there any greedy approach for solving this problem?

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain
Backtracking is enough

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
i used simple backtracking, so whenever i found a wrong way i just pruned, that took only 0.012sec
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:
i agree with SRX . this problem is a classic example of maximum flow( or matching what ever u say ) . this problem can be solved by backtracking due to the small limit given . if the limit is extended to 50 students each having 50 choices of t shirt sizes then i guess matching is the only way to go .
clarify me if i am wrong .
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
I used maximum flow and got it Accepted. The following test cases can be helpful.

Input:

Code: Select all

``````2
6 6
L XL
XL XS
XS XXL
XXL M
S M
L XS
6 6
L XL
XL XS
XS XXL
XXL XL
S M
L XS``````
Output:

Code: Select all

``````YES
NO``````
Ami ekhono shopno dekhi...
HomePage

mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)
Hi

I Have also solved this problem with Back Tracking approch. But if the Problem range is higher then my Back Tracking approch will not work.
Then maximum flow have to be considered.

Thanks
Mohiul Alam Prince

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Contact:
rammestain wrote:I tried to solve this problem with dynamic programming but got TLE
I have solved the problem using memoization.

visited[a][c][d][e][f] becomes true when I have tried giving 'a' no of XS, 'b' no of S .... 'f' no of XXL t-shirts
Where's the "Any" key?

C
New poster
Posts: 35
Joined: Mon Apr 17, 2006 1:04 pm
Hi, I also solved it with back-tracking. But how can i approach this problem with max-flow??
Could anyone give me any hints ?
what's the weight of edge and source and sink ??

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:
Yes, how to implement it into maximum flow problem ??? And also could you give me some more input and output ??? Thx...

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### flow..

I also solved this problem with max-flow..

Here is, how it goes:

Suppose you have M volunteers, then you have to consider (M + 6 + 2) nodes..
6 ---> number of distinct T-Shirts and
2 ---> source and sink.

Node 0 --> source
node 1 - M ---> the M voulunteers
node (M+1) - (M+6) ---> the T-Shirts
node M+7 ---> sink

initially source(0) is connected with all the nodes from (1 - M) with a cost of 1 and nodes (M+1) to (M+6) are connected to the sink(M+7) with a cost that is equal to number of available T-Shirts of each type.

Then ( from the input ) ..
a volunteer ( 1 - M ) is connected to a T-Shirt( (M+1) - (M+6) ) if that T-Shirts fits him and the cost is 1.

Then simply apply MAX-Flow and see if you can succeed M times(that is when your answer will be 'yes').

New poster
Posts: 32
Joined: Tue Feb 13, 2007 1:31 pm

### Re: 11045 - My T-shirt suits me

Sample test cases:

Code: Select all

``````2
6 6
L XL
XL XS
XS XXL
XXL M
S M
L XS
6 6
L XL
XL XS
XS XXL
XXL XL
S M
L XS
``````
I support the algorithm: Reduce method and Match method

Reduce method seems Greedy
1.declare a variable called limit = N / 6.
2.count how many ppl suits in each size.(0 is the first one, M - 1 is the last one)
Take the first sample test case is

Code: Select all

``````limit = 1

XXL: 2 3
XL: 0 1
L: 0 5
M: 3 4
S: 4
XS: 1 2 5
``````
run while loop, reduce the the ppl in the each size which the number of size is <= limit.
still run while loop untill it cant reduce.

Code: Select all

``````<step1>
XXL: 2 3
XL: 0 1
L: 0 5
M: 3
S:
XS: 1 2 5

<step2>
XXL: 2
XL: 0 1
L: 0 5
M:
S:
XS: 1 2 5

<step3>
XXL:
XL: 0 1
L: 0 5
M:
S:
XS: 1 5
``````
it remains 0, 1, 5 have no T-Shirts to wear, total is 3 radish.
it remains XL, L, XS size, total is 3 hole.

Match method is

Code: Select all

``````             if(hole * limit < radish)
System.out.println("NO");
else
System.out.println("YES");
``````
Of course, if just use Reduce method make it done, output is YES
If reduce method is not enough, use Match method.

Code: Select all

``````YES
NO
``````
Hope it will help.

junior boy
New poster
Posts: 1
Joined: Sat Sep 04, 2010 10:33 pm

### Re: 11045 - My T-shirt suits me

Is anybody have important testcases?
This is my code i can't understand Why it has gotten wrong answer?

i used fordfolkerson method it has gotten wrong answer at 1.2 seconds .

If somebody have judge testcases and answsers it will help

thank's

Code: Select all

``````#include<iostream>
#include<vector>
#include<string>

#define NN 1024 // the maximum number of vertices[0,n-1],[i][j] = i->j edge
#define MAX_CAP 2000000000000000000

using namespace std;

long int cap[NN][NN];// adjacency matrix (fill this up) [0, n-1]
long int fnet[NN][NN];// flow network  [0, n-1]
long int q[NN], qf, qb, prev[NN];// BFS
int size[6];
string si[6]={"XS","S","M","L","XL","XXL"};

long int fordFulkerson( long int n, long int s, long int t );
int s_to_i(string);

int main(){
long int num,N,M;
string temp;
cin>>num;
for(int knum=0;knum<num;knum++){
cin>>N>>M;
for(int kk=0;kk<6;kk++)
size[kk]=0;
for(int k1=0;k1<M+N+2;k1++)
for(int k2=0;k2<M+N+2;k2++)
cap[k1][k2]=0;
for(int kM=0;kM<M;kM++){
for(int k1=0;k1<2;k1++){
cin>>temp;
cap[N/6*s_to_i(temp)+size[s_to_i(temp)]][kM+N]=1;
size[s_to_i(temp)]++;size[s_to_i(temp)]%=(N/6);

}
}
for(int k1=0;k1<N;k1++)
cap[N+M][k1]=1;
for(int k1=0;k1<M;k1++)
cap[k1+N][N+M+1]=1;

/*for(int k1=0;k1<N+M+2;k1++)
for(int k2=0;k2<N+M+2;k2++)
if(cap[k1][k2]!=0)cout<<k1<<" "<<k2<<" "<<cap[k1][k2]<<endl;*/

if(fordFulkerson(N+M+2,N+M,N+M+1)==M)
cout<<"YES"<<endl;
else cout<<"NO"<<endl;

}
return 0;
}

long int fordFulkerson( long int n, long int s, long int t ){
memset( fnet, 0, sizeof( fnet ) );// init the flow network
long int flow = 0;
while( true ){
memset( prev, -1, sizeof( prev ) );// find an augmenting path
qf = qb = 0;
prev[q[qb++] = s] = -2; //Enqueue
while( qb > qf && prev[t] == -1 )//BFS //Dequeue
for( long int u = q[qf++], v = 0; v < n; v++ )
if( prev[v] == -1 && fnet[u][v] - fnet[v][u] < cap[u][v] )
prev[q[qb++] = v] = u;
if( prev[t] == -1 ) break;// see if we're done
long int bot = 0x7FFFFFFF;
for( long int v = t, u = prev[v]; u >= 0; v = u, u = prev[v] ) // get the bottleneck capacity
bot = min(bot,cap[u][v]-fnet[u][v]+fnet[v][u]);
for( long int v = t, u = prev[v]; u >= 0; v = u, u = prev[v] )// update the flow network
fnet[u][v] += bot;
flow += bot;
}
return flow;
}

int s_to_i(string s){
for(int k=0;k<6;k++)
if(s==si[k])return k;
}
``````

jerrzey
New poster
Posts: 1
Joined: Tue May 10, 2011 1:00 pm

### Re: 11045 - My T-shirt suits me

This is such a great resource that you are providing and it's really easy for me to SEE what you were talking about.