11045 - My T-shirt suits me

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

Moderator: Board moderators

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

11045 - My T-shirt suits me

Post by Ankur Jaiswal » Sun Jun 04, 2006 5:04 pm

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?

Post by SRX » Sun Jun 04, 2006 5:10 pm

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 .
just think about matching .
:D
studying @ ntu csie

rammestain
New poster
Posts: 18
Joined: Fri Apr 21, 2006 11:34 am

Post by rammestain » Sun Jun 04, 2006 5:18 pm

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

Post by Emilio » Sun Jun 04, 2006 5:33 pm

Backtracking is enough

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Sun Jun 04, 2006 5:49 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

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

Post by Riyad » Mon Jun 05, 2006 6:32 pm

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue Jun 06, 2006 1:06 am

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

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

Post by mohiul alam prince » Tue Jun 06, 2006 11:50 am

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
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Tue Jun 06, 2006 5:53 pm

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

Post by C » Tue Jun 06, 2006 9:07 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 ??

Thanks in advance!

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes » Tue Jun 06, 2006 9:14 pm

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

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

flow..

Post by sohel » Wed Jun 07, 2006 11:17 am

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
New poster
Posts: 32
Joined: Tue Feb 13, 2007 1:31 pm

Re: 11045 - My T-shirt suits me

Post by deadangelx » Fri Jan 02, 2009 4:30 am

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
New poster
Posts: 1
Joined: Sat Sep 04, 2010 10:33 pm

Re: 11045 - My T-shirt suits me

Post by junior boy » Sat Sep 04, 2010 10:51 pm

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 :D

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

Post by jerrzey » Tue May 10, 2011 1:04 pm

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:

Post Reply

Return to “Volume 110 (11000-11099)”