SRM 304

Division 2

250 Pts -

Idea Flow

Input_Constraint ~ Problem Constraint was very lenient.

Question Hints ~ Need to understand the question and finding a optimized method could solve the problem more easy. 

Conclusion ~ Finding factors till sqrt. Figured out in the first glance

Learnt lesson ~ Spend time on writing code in your note.

500 Pts -

Idea Flow

Input_Constraint ~ Comparatively easy. Easier than 250 pts  

Question Hints ~ Any approach ll be within the timelimit.

Conclusion ~ To avoid floating point errors. we add the sums and then divide the number and finding corresponding decimal value at last to find precision errors.

Learnt lesson ~ If computing method is same divide the number in the last step. So that comparison is easy for us. 

1000 Pts -

Idea Flow

Input_Constraint ~

Question Hints ~

Conclusion ~

Learnt lesson ~ 

SRM 303

Division 2

250 Pts -

Idea Flow

Input_Constraint ~ An geometry problem constructing a graph and brute forcing solution would time out. 

Question Hints ~ All line are parallel to any one of the axes

Conclusion ~ Need to be good at geometry.

Learnt lesson ~ Knowing to define the solution first, then write the code.

Awesome solution from Editorial 

500 Pts -

Idea Flow

Input_Constraint ~ Brute force won't pass the time limit

Question Hints ~ Know always addition of scaling factor keeps on increasing.

Conclusion ~ Don't rely on previous memory. Won't work out in a running contest.

Learnt lesson ~ Better solution which run in sqrt(n) need to be understood.

1000 Pts -

Idea Flow

Input_Constraint ~ Very clear problem statement easy to understood.

Question Hints ~ Gives us hint that maximum number of factors for number can be 13 only.

Conclusion ~ Since repetition reduce the number of permutation in a number. We can conclude the it runs within time limit. 

Learnt lesson ~ We need to come up with a valid support, to support our assumption made.

int left = max(min(s1x1, s1x2), min(s2x1, s2x2)); //Gives second most left point
  int right = min(max(s1x1, s1x2), max(s2x1, s2x2));  //Gives second most right point
  int bottom = max(min(s1y1, s1y2), min(s2y1, s2y2)); //Gives second most bottom point
  int top = min(max(s1y1, s1y2), max(s2y1, s2y2)); //Gives second most top point 

  if(bottom > top || left > right) //Now if the bottom is > the top point or the left > right point then there is no intersection
    return "NO";

  if(top == bottom && left == right) //If all point is converging at a middle point.
    return "POINT";    

  return "SEGMENT"; //Else segment easy way to check like dis 

}

Stringstream,Sprintf,next_permutation

Many Time we need to convert the number to string.
So I bring you methods where you can convert the number to string.

Lets us declare enumeration function that tell whether it's Integer or Float value.

enum Type
{
    INT,FLOAT
};

In C++

string convert2string(void *value,int type)
{
 stringstream convertor;
 string result;
 switch(type)
 {
  case INT:
    convertor<<*static_cast<int*>(value);
                  break;
  case FLOAT:
    convertor<<*static_cast<float*>(value);
                                break;
 }
 convertor>>result;
 return result;

}

In C

string convert2stringc(void *value,int type)
{
  char buffer[80];
  switch(type)
  {
   case INT:
    sprintf(buffer,"%d",*(int*)value);
    break;
   case FLOAT:
    sprintf(buffer,"%f",*(float*)value);
    break;
  }
  return buffer; 
}

Next Permutation is very useful which generates all the permutation of the given vector

sort(container.begin(),container.end());
do
{
  //Do all the operation here 
}next_permutation(container.begin(),container.end());

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