code with chinmay.c

This blog is for those who wants to understand the network flow. Honestly telling no explanation is better than Topcoder's one. So jump into the explanation. Here I will share the implementation. So anyone who after reading the tutorial still cannot implement can look through the code to grasp the idea.

Max Flow 1
Max Flow 2

BASIC FORD FULKERSON CODE( BFS implementation)

/*
network flow 
ford fulkerson by chinmay Rakshit
date 18/11/2015
*/
#include <bits/stdc++.h>
using namespace std;
int min(int a,int b)
{
    return (a<b)?a:b;
}
int main()
{
    int n,m,adj[101][101]={0},x,y,z,scr,des,cost=0,parent[101]={0};//adjacent matrix
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++)
    {
        scanf("%d %d %d",&x,&y,&z);
        adj[x][y]=z;
    }
    scanf("%d %d",&scr,&des);
    while(1)
    {
        int flag=0;
        queue<int>q;
        q.push(scr);
        while(!q.empty())
        {
            int f=q.front();
            q.pop();
            for(int i=1;i<=n;i++)
            {
                if(adj[f][i]!=0 && parent[i]==0 && i!=scr)
                {
                    parent[i]=f;
                    if(i==des)
                    {
                        flag=1;
                        while(!q.empty())
                            q.pop();
                        break;
                    }
                    q.push(i);
                }
            }
        }
        //BFS to find the parent.....
        if(flag!=1)
            break;
        int local=1e9,i;
        for(i=des;i!=1;i=parent[i])
            local=min(local,adj[parent[i]][i]);
        // to find the lowest in the augumented path
        cost+=local;
        for(i=des;i!=1;i=parent[i])
        {
            adj[parent[i]][i]-=local;
            adj[i][parent[i]]+=local;
        }
        //making cancelation and addition to the flow.....
        memset(parent,0,(n+1)*sizeof(int));
    }
    printf("%d\n",cost );
    return 0;
}

for the above code to check consider the flow given in the topcoder's site.

input
7 10
1 2 3
2 3 3
4 1 1
4 3 4
3 4 1
3 7 1
7 3 1
4 5 4
5 6 2
6 7 3

1 7

output
2

BASIC FORD FULKERSON CODE( PFS implementation)

/*
Network flow was done earlier on bfs 
now I trying in PFS(Priority first search)
going through the full details...
*/
#include <bits/stdc++.h>
using namespace std;

typedef struct $
{
 int from; //parent
 int vertex; // current node
 int priority; // the cost associated (from) --> (vertex)
}node;


class mycomparison
{
public:
 bool operator() (const node &lhs, const node &rhs) const
 {
  return (lhs.priority < rhs.priority);
 }
};

int main(int argc, char const *argv[])
{
 std::priority_queue< node, std::vector<node>, mycomparison > pq;
 node x;
 
 int n, m,start, end, capacity, source, sink ,adj[101][101] = {0};
 int path_capacity = 0;

 cin >> n >> m;
 for (int i = 0; i < m; ++i)
 {
  cin >> start >> end >> capacity;
  adj[start][end] = capacity;
 }
 
 cin >> source >> sink;

 while(1)
 {
  int flag = 0;
  x.vertex = source;
  x.priority = 1e9;
  x.from = -1;
  pq.push(x);
  
  
  int from[101] = {0};
  int local = 0;
  while(!pq.empty())
  {
   node aux = pq.top();
   pq.pop();
   int where = aux.vertex;
   int cost = aux.priority;
   from[where] = aux.from;

   cout << from[where] << " " << where << " " << cost << "\n";
   if( where == sink)
   {
    flag = 1;
    local = cost;
    while(!pq.empty())
     pq.pop();
    break;
   }

   for(int i=0; i<=n; i++)
   {
    if( adj[where][i]>0 and from[i]==0)
    {
     int new_cost = min(cost, adj[where][i]);
     //makes sure that the cost should be less than the host ex: 4 3 1 in the output
     x.vertex = i;
     x.priority = new_cost;
     x.from = where;
     pq.push(x);
    }
   }
  }
  
  if(flag == 0)
   break;

  path_capacity += local;
  int where = sink;
  while ( from[where] >-1)
  {
   int prev = from[where];
   adj[prev][where] -= local;
   adj[where][prev] += local;
   where = prev;
  }
 }
 cout << path_capacity;
 
 return 0;
}

Question 1)

ROOK ATTACK

Problem Statement

You have been given a rows-by-cols chessboard, with a list of squares cut out. The list of cutouts will be given in a String[] cutouts. Each element of cutouts is a comma-delimited lists of coords. Each coord has the form (quotes for clarity) "r c". If coord "r c" appears in an element of cutouts, it means that the square at row r column c (0-based) has been removed from the chessboard. This problem will involve placing rooks on a chessboard, so that they cannot attack each other. For a rook to attack a target piece, it must share the same row or column as the target. Your method will return an int that will be the maximum number of rooks that can be placed on the chessboard, such that no pair of rooks can attack each other. Rooks cannot be placed on cut out squares. The cut out squares do not affect where the rooks can attack.

Definition

Class:	RookAttack
Method:	howMany
Parameters:	int, int, String[]
Returns:	int
Method signature:	int howMany(int rows, int cols, String[] cutouts)
(be sure your method is public)

Constraints

rows will be between 1 and 300 inclusive.

cols will be between 1 and 300 inclusive.

cutouts will contain between 0 and 50 elements inclusive.

Each element of cutouts will contain between 3 and 50 characters inclusive.

Each element of cutouts will be a comma delimited list of coords. Each coord will be of the form "r c", where

r and c are integers, with no extra leading zeros,
r is between 0 and rows-1 inclusive,
and c is between 0 and cols-1 inclusive.

Each element of cutouts will not contain leading or trailing spaces.

Examples

{}

Returns: 8

........ 
........ 
........ 
........ 
........ 
........ 
........ 
........

{"0 0","0 1","1 1","1 0"}

Returns: 0

XX 
XX

{"0 0","1 0","1 1","2 0","2 1","2 2"}

Returns: 2

X.. 
XX. 
XXX

{"0 0","1 2","2 2"}

Returns: 3

X.. 
..X 
..X

{}

Returns: 200

#line 90 "RookAttack.cpp"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, string> pp;

class RookAttack {
 public:

 std::vector<int> lst[300];
 int row_col[300], col_row[300];

 bool find_match(int source)
 {
  int parent[300], current_row, curent_col;
  for(int i=0;i<=300;i++)
   parent[i]=-1;
  parent[source] = source;

  queue<int> q;
  q.push(source);


  int flag = 0;
  while( !flag and !q.empty())
  {
   current_row = q.front();
   printf("current row = %d\n", current_row);
   q.pop();
  

   //loop over all the columns.
   for(int i=0; i<lst[current_row].size(); i++)
   {
    curent_col = lst[current_row][i];//picking up a column
    printf("current_col = %d\n", curent_col);

    
    int row_connecting_this_col = col_row[curent_col];
    printf("/*denotes the row number to which the column is linked*/\n row_connecting_this_col = %d\n", row_connecting_this_col);


    if(row_connecting_this_col == -1)
    {
     flag = 1;
     break;
    }
    if(parent[row_connecting_this_col] == -1)
    {
     printf("row_connecting_this_col is here setting its parent as %d\n", current_row);
     q.push(row_connecting_this_col);
     parent[row_connecting_this_col] = current_row;
    }
   }
  }
  if(!flag)
   return false;

  while(parent[current_row] != current_row)
  {
   int column_in_this_row = row_col[current_row];
   row_col[current_row] = curent_col;
   col_row[curent_col] = current_row;
   
   printf("column_in_this_row = %d\n", column_in_this_row);
   printf("row_col[%d] = %d\n",current_row, curent_col);
   printf("col_row[%d] = %d\n",curent_col, current_row);

   current_row = parent[current_row];
   curent_col = column_in_this_row;
   
   printf("current_row = %d\n", current_row);
   printf("curent_col = %d\n", curent_col);
  }
  row_col[current_row] = curent_col;
  col_row[curent_col] = current_row;

  printf("OUT row_col[%d] = %d\n",current_row, curent_col);
  printf("OUT col_row[%d] = %d\n",curent_col, current_row);
  printf("_____________________________________\n");
  
  return true;
 }
 int howMany(int rows, int cols, vector <string> cutouts) {
  
  int adj[303][303] = {0};
  int ret = 0;
  memset(row_col, -1, sizeof(row_col));
  memset(col_row, -1, sizeof(col_row));

  int cuts_len = cutouts.size();
  for(int i=0; i< cuts_len; i++)
  {
   stringstream ss(cutouts[i]);
   int r,c;
   ss >> r >> c;
   adj[r][c] = 1;
  }
 
  for(int i=0;i<rows;i++)
   for(int j=0;j<cols;j++)
    if(adj[i][j] == 0)
     lst[i].push_back(j);
     
  for(int i=0; i<rows; i++)
   ret += find_match(i);

  return ret;
 }
};


// Powered by FileEdit
// Powered by CodeProcessor

Run it and do analyse the output using the print statements given,

Question 2

GRADUATION

Problem Statement

You are a student advisor at TopCoder University (TCU). The graduation requirements at TCU are somewhat complicated. Each requirement states that a student must take some number of classes from some set, and all requirements must be satisfied for a student to graduate. Each class is represented as a single distinct character. For example, one requirement might be "Take any 2 classes of B, C, D, or F." Further complicating the matter is the fact that no class can be used to satisfy more than one requirement. And so students come to you all the time, dazed and confused, because they don't know how close they are to satisfying the requirements so that they can graduate!

Each class is represented as a distinct single character whose ASCII value is between 33 and 126, inclusive, but is also not a numeric character ('0'-'9'). You will be given a String classesTaken, which represents the classes that a given student has taken. You will also be given a String[] requirements, which lists the requirements needed to graduate. Each String in requirements will start with a positive integer, followed by some number of classes. For example, the requirement "Take any 2 classes from B, C, D, or F" would be represented in requirements as "2BCDF".

Your method should return a String representing the classes that the student needs to take in order to graduate, in ASCII order. Classes may not be taken more than once. If there is more than one set that will allow the student to graduate, return the smallest set. If there are multiple smallest sets, return the lexicographically smallest of these. Finally, if there is no set that will enable this student to graduate, return "0".

Definition

Class:	Graduation
Method:	moreClasses
Parameters:	String, String[]
Returns:	String
Method signature:	String moreClasses(String classesTaken, String[] requirements)
(be sure your method is public)

Notes

Classes may not be taken more than once.

Constraints

classesTaken will be between 0 and 50 characters in length, inclusive.

each character in classesTaken will be a valid class (ASCII value between 33 to 126 inclusive and not a digit).

there will be no duplicate classes in classesTaken.

requirements will contain between 1 and 50 elements, inclusive.

each element of requirements will contain a positive integer with no leading zeros between 1 and 100, inclusive, followed by some number of valid classes.

each element of requirements will be between 1 and 50 characters in length, inclusive.

there will be no duplicate classes in any given element of requirements

Examples

"A"

{"2ABC","2CDE"}

Returns: "BCD"

The student must take two classes from {A,B,C}, and two from {C,D,E}. He has already taken A.

"+/NAMT"

{"3NAMT","2+/","1M"}

Returns: ""

The student has already fulfilled all the requirements - you should congratulate him for his achievement!

"A"

{"100%*Klju"}

Returns: "0"

No matter how hard you try, you can't take 100 classes out of 6. TCU had better fix their policies quick.

""

{"5ABCDE","1BCDE,"}

Returns: ",ABCDE"

"CDH"

{"2AP", "3CDEF", "1CDEFH"}

Returns: "AEP"

#line 72 "Graduation.cpp"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,vector<int> > pp;

class Graduation {
 public:
 vector<int> req_Lst[127];
 vector<int> classes;
 int B_A[127]={0}, A_B[127]={0};
 
 string play(int source)
 {
  int parent[127] = {0}, current_req, current_class, req_to_class;
  for(int i=0; i<=126; i++)
   parent[i] = -1;
  parent[source] = source;

  queue<int> q;
  q.push(source);
  int flag = 0;
  while(!flag and !q.empty())
  {
   current_class = q.front();
   q.pop();
   
   for(int i=0; i<req_Lst[current_class].size();i++)
   {
    current_req = req_Lst[current_class][i];
    req_to_class = B_A[current_req];
    if(req_to_class == -1)
    {
     flag = 1;
     break;
    }
    if(parent[req_to_class] != -1)
    {
     parent[req_to_class] = source;
     q.push(req_to_class);
    }
   }
  }
  if(!flag)
   return "";

  while(parent[current_class] != current_class)
  {
   int class_to_req = A_B[current_class];
   A_B[current_class] = current_req;
   B_A[current_req] = current_class;

   current_req = class_to_req;
   current_class = parent[current_class];
  }

  A_B[current_class] = current_req;
  B_A[current_req] = current_class;

  string ss;
  ss.push_back((char)source);
  return ss;
 }
 string moreClasses(string classesTaken, vector <string> requirements) 
 {
  
  int a[127] = {0};
  vector<pp> vpp;
  
  memset(A_B, -1, sizeof(A_B));
  memset(B_A, -1, sizeof(B_A));
  for(int i=0; i< requirements.size() ;i++)
  {
   const char *s = requirements[i].c_str();
   int x = 0;
   vector<int> v;
   for(int j=0; j<strlen(s); j++)
   {
    if('0'<=s[j] and s[j]<='9')
     x = x*10 + s[j]-'0';
    else
    {
     v.push_back(s[j]);
     a[s[j]] = 1;
    }
   }
   vpp.push_back(pp(x,v));
  }
  
  for(int i=0;i<classesTaken.size(); i++)
   a[classesTaken[i]]=0;
 
  for(int i=0; i<=126; i++)
   if(a[i] == 1)
    classes.push_back(i);
         
  sort(classes.begin(), classes.end());
  //creating of vector of classes is done set A
  
  
  int co = 0;
  for(int i=0; i<vpp.size(); i++)
  {
   pp f = vpp[i];
   vector<int> req;
   for(int j=0; j<f.first; j++)
    req.push_back(co++);
   vector<int> v = f.second;
   for(int j=0; j<v.size(); j++)
    req_Lst[v[j]].insert(req_Lst[v[j]].end(), req.begin(), req.end());
  } 
  
  /*
  testing of the required list created for the classes
  for(int i = 0; i< 127;i++)
  {
   if(req_Lst[i].size()==0)
    continue;
    
   cout << (char)i << " :";
   for(int j=0; j<req_Lst[i].size(); j++)
    cout << req_Lst[i][j] << " ";
   cout << "\n";
  }
  */
  
  for(int i=0;i<classesTaken.size();i++)
  { 
   play(classesTaken[i]);
  }
  
  string ac = "";
  for(int i=0;i<classes.size();i++)
  {
   ac += play(classes[i]);
  }
  return ac;
 }
};

code with chinmay.c

Friday, 17 March 2017

Network Flow codes.

Problem Statement

Definition

Constraints

Examples

Problem Statement

Definition

Notes

Constraints

Examples

Translate

catagories