Bipartite Matching - Max Flow Algorithm

Converting Bipartite Matching to Max Flow Algorithm

//This is conversion from Bipartite matching to Max-FLow algorithm.
//Nice way to convert.
//I have used EdmondsKarp algorithm for the conversion.
class PointyWizardHats {
 public:
 int graph[205][205],lnode,rnode,parent[205],visited[200],city;
 bool bfs(int s,int t) 
{
  parent[s]=-1;
  visited[s]=true;
  queue<int> Q;
  Q.push(s);
  while(!Q.empty())
  {
    int u=Q.front();
    Q.pop();
    if(u==t)
      return true;
    for(int v=0;v<city;v++)
    {
      
      if(!visited[v] and graph[u][v]>0)
      {
        Q.push(v);
        visited[v]=true;
        parent[v]=u;
      }
    }
  }
  return false; 
}
int maxflow(int s,int t)
{
   int mflow=0;
   CLR(visited);
   CLR(parent);
   while(bfs(s,t))
   {
    
    CLR(visited);
    int v,u;
    int mi=10000000;
    for(v=t;v!=s;v=parent[v]){u=parent[v];
      mi=min(mi,graph[u][v]);}
    for(v=t;v!=s;v=parent[v])
    {
     u=parent[v];graph[u][v]-=mi;graph[v][u]+=mi;
    }     
    mflow+=mi;
   }
   return mflow; 
}
 
 bool can_be_kept(int bh,int br,int th,int tr) // General Constraint for the problem
 {
  if(br>tr and (th*br>bh*tr))
    return true;
  return false; 
 }
 
 int getNumHats(vector <int> topHeight, vector <int> topRadius, vector <int> bottomHeight, vector <int> bottomRadius) 
 {
  CLR(graph);
  lnode=bottomHeight.size();
  rnode=topHeight.size();
  for(int i=0;i<lnode;i++) 
    graph[0][i+1]=1; //Where 0 is the source it connects to all the u nodes .
  for(int i=0;i<lnode;i++) //Now take all the u nodes starting from 1 to lnode-
    for(int j=0;j<rnode;j++)
      if(can_be_kept(bottomHeight[i],bottomRadius[i],topHeight[j],topRadius[j]))
         graph[i+1][lnode+j+1]=1;
  
  for(int i=0;i<rnode;i++)
    graph[lnode+i+1][rnode+1+lnode]=1;
  city=rnode+lnode+2;
  return maxflow(0,rnode+1+lnode); 
 }
};

Bipartite-Matching

/*First METHOD 
Solved Using kuhn's Algorithm 
Kho-Kho algorithm ~ Take a free vertex and find a augmentation which increase the match atleast by one.
Berge's Theorem ~ A matching M in a Bipartite graph is maximum if and only if there doesn exist any augmenting path.
Run in O(N*M+N*N) */ 
class PointyWizardHats {
 public:
 int parent[55],visited[55],rnode,lnode;
 vector<int> graph[55];
 bool can_be_kept(int bh,int br,int th,int tr) // General Constraint for the problem
 {
  if(br>tr and (th*br>bh*tr))
    return true;
  return false; 
 }
 bool dfs(int u)
 {
   if(visited[u])
      return false;
   visited[u]=true;
   for(int i=0;i<(int)graph[u].size();i++)
   {
     int v=graph[u][i];
     if(parent[v]==-1 or dfs(parent[v]))
     {
       parent[v]=u;
       return true;
     }
   }
   return false;
 }
 int kuhn_salgo()
 {
   SET(parent);  
   for(int i=0;i<lnode;i++)  
   { 
    CLR(visited);  
    dfs(i);
   }
   return rnode-count(parent,parent+rnode,-1);   
 }
 int getNumHats(vector <int> topHeight, vector <int> topRadius, vector <int> bottomHeight, vector <int> bottomRadius) 
 {
  lnode=bottomHeight.size();rnode=topHeight.size();
  LOOP(j,rnode)
   LOOP(i,lnode)
     if(can_be_kept(bottomHeight[i],bottomRadius[i],topHeight[j],topRadius[j]))
        graph[i].push_back(j);
  
  return kuhn_salgo(); 
 }
};

SRM 302

Division 2

250 Pts -

Idea Flow

Input_Constraint ~ One for loop is sufficent.

Question Hints ~ Direct Implementation Problem.

Conclusion ~ Was in right direction.

Learnt lesson ~ Stl makes things faster discussed in previous blog

500 Pts -

Idea Flow

Input_Constraint ~ Question is direction any implementation ll pass the time limit.

Question Hints ~ Each position is of character 2

Conclusion ~ Using Set operation safe lot of time I was sorting each time.

Learnt lesson ~ Learnt to use Set operation.

1000 Pts -

Idea Flow

Input_Constraint ~ Question is clear and bruteforce ll timelimit

Question Hints ~ Since we need to take oly the factor. Running till sqrt(N) ll pass the time limit.

Conclusion ~ I used queue and solved the problem didn come up with the dp solution.

Learnt lesson ~ Using dp would have fasten things up, But why dp works thing about it .

Things to ponder

Does first computed current state from any previous state is the final solution or we need to find minimum from all previous state.

.i.e

if(j+i<=M )
  dp[j+i]=min(dp[j+i],dp[i]+1);
if(i+l<=M )
  dp[i+l]=min(dp[i+l],dp[i]+1);

is't equivalent to

if(j+i<=M and dp[j+i] not visited )
  dp[j+i]=dp[i]+1;
if(i+l<=M and dp[j+l] not visited )
  dp[i+l]=dp[i]+1;

STL Function n Little bit of Strings

STL - SET

Intialization

SET

set<int> myset;

SET Iterator

set<int>::iterator it;

Insertion in SET

myset.insert(value);

Deletion in SET

myset.erase(value);
|
it=myset.find(value)
 myset.erase(it,myset.end()); //to remove all element >=value 

Traversing in SET

for(it=myset.begin();it!=myset.end();it++)
 cout<<(*it);

Lower_bound in SET

it=myset.lower_bound(value);
//return an index >=value.

Upper_bound in SET

it=myset.upper_bound(value);
//return an index >value.
//Note if there is no answer >=value then it return the iterator to my.end();

String Operation

string h;
h.find(“-”); //return the index where the charater is found.
h.erase(pos,number_of_character_to_be_erased);
h.erase(pos);//erase the character in that index 

SRM 301

Division 2

250 Pts - InsertionSortCount  

Idea Flow

Input_Constraint ~ We cannot use more than two loops.

Question Hints ~ "Must know insertion sort :p".

Conclusion ~ Straight forward check ll run within in runtime.

Learnt lesson ~ take index j and check number of number from [0..j-1] is > j. So those corresponds to the result. 

500 Pts - IndicatorMotionReverse 

Idea Flow

Input_Constraint ~ 1 sec is the time-limit so string-length can be the number of operation.

Question Hints ~ "Understand that it is a direct implementation program.

Conclusion ~ Finding shorter way to code is more important.

Learnt lesson ~ Sometimes it's is better to expand the input and then get answer from the expanded string.

1000 Pts - CorrectingParenthesization 

Idea Flow

Input_Constraint ~ Problem allows maximum of 50^4 operation that is 4 for loop for the give problem.

Question Hints ~ Gives idea that we need use dynamic programming approach.

Conclusion ~ Fixing two brackets and solving for other sub-problem.

Learnt lesson ~ Must learn how to convert this to bottom-up approach or the iterative method.

int run(int i,int j)
{
   if(i>j)
     return 0;
   int &res=dp[i][j];
   if(res!=-1)
     return res;
   res=run(i+1,j-1)+enc(ans[i],ans[j]);
   for(int k=i+1;k<j;k+=2)
    res=min(res,run(i,k)+run(k+1,j));
   return res;
 
}

SRM 300

Division 2

250 pts - Taxi 

Idea Flow
Input_Constraint ~ We cannot use more than one loop.
Question Hints ~ "Segments parallel to the axes".
Conclusion ~ We need to find the triangle sum of a+b is given. Need to find the whether an right triangle can be formed or not with the given constraint.
Learnt lesson ~ Fast and correct interpretation of question is needed. (drawing diagrams ll help out).

500 pts - Dating 

Idea Flow
Input_Constraint ~ Brute Force is possible.
Question Hints ~ "Given all letters are distinct".
Conclusion ~ Do imagine the question as a straight queue rather than circular queue. More easy to code and solution is small.
Learnt lesson ~ Spend some time to think for an alternative idea.

1000 pts - CircleOrder 

Idea Flow

Input_Constraint ~ Brute Force is possible. 

Question Hints ~ "Circular track so landing spot and initial car position must be in Circular order.

Conclusion ~ Above hint isn sufficient to come up with the solution and need to find whether all character is able to reach the destination.

Learnt lesson ~ Understanding the question and little tweek ll provide the solution. So trying for different cases ll be provide better understanding of the question and you ll come to an implementation.