11045 - My T-shirt suits me
Moderator: Board moderators
-
- 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.
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.
Re: 11045 How to solve?
there is no trick in this problem .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.
just think about matching .
![:D](./images/smilies/icon_biggrin.gif)
studying @ ntu csie
-
- New poster
- Posts: 18
- Joined: Fri Apr 21, 2006 11:34 am
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 .
![:)](./images/smilies/icon_smile.gif)
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
I used maximum flow and got it Accepted. The following test cases can be helpful.
Input:
Output:
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
Code: Select all
YES
NO
Ami ekhono shopno dekhi...
HomePage
HomePage
-
- Experienced poster
- Posts: 120
- Joined: Sat Nov 01, 2003 6:16 am
- Location: Dhaka (EWU)
-
- Experienced poster
- Posts: 136
- Joined: Fri Apr 15, 2005 3:47 pm
- Location: Singapore
- Contact:
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').
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:
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
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.
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
Of course, if just use Reduce method make it done, output is YES
If reduce method is not enough, use Match method.
The answer is
Hope it will help.
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
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
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 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");
If reduce method is not enough, use Match method.
The answer is
Code: Select all
YES
NO
-
- 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
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
![:D](./images/smilies/icon_biggrin.gif)
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;
}
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. ![:lol:](./images/smilies/icon_lol.gif)
![:lol:](./images/smilies/icon_lol.gif)