11045 - My T-shirt suits me

[Ankur Jaiswal]

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]

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 .
just think about matching .

[rammestain]

I tried to solve this problem with dynamic programming but got TLE,
Is there any greedy approach for solving this problem?

[Emilio]

Backtracking is enough

[ayon]

i used simple backtracking, so whenever i found a wrong way i just pruned, that took only 0.012sec

[Riyad]

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 .

[Jan]

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

[mohiul alam prince]

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]

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

[C]

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

Thanks in advance!

[jan_holmes]

Yes, how to implement it into maximum flow problem ??? And also could you give me some more input and output ??? Thx...

[sohel]

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

[deadangelx]

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.

The answer is

Code: Select all

YES
NO

Hope it will help.

[junior boy]

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]

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