LightOJ [1212]

Problem
1212 - Double Ended Queue

Idea Flow

Input_Constraint ~ All operation must be done in O(1)

Question Hints ~ Cake Walk

Conclusion ~ Just follow what problem statement tells.

Learnt lesson ~ Can try different DS other than deque. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

package net.egork; import java.io.PrintWriter; import java.util.ArrayDeque; import java.util.Deque; import java.util.Scanner; public class L1212 { private static final String CASE = "Case"; private static final String SPACE = " "; private static final String COLON = ":"; private static final String PUSHLEFT = "pushLeft"; private static final String PUSHRIGHT = "pushRight"; private static final String POPLEFT = "popLeft"; private static final String POPRIGHT = "popRight"; private static final String QUEUEFULL = "The queue is full"; private static final String PSLEFT = "Pushed in left: "; private static final String PSRIGHT = "Pushed in right: "; private static final String QUEUEEMPTY = "The queue is empty"; private static final String POSLEFT = "Popped from left: "; private static final String POSRIGHT = "Popped from right: "; public void solve(int testNumber, Scanner in, PrintWriter out) { int testCase; testCase = in.nextInt(); for (int i = 1; i <= testCase; i++) { Deque<Integer> deque = new ArrayDeque<Integer>(); int sizeDeque, n; sizeDeque = in.nextInt(); n = in.nextInt(); String getLine; String command[]; System.out.println(CASE + SPACE + i + COLON); in.nextLine(); while (n > 0) { getLine = in.nextLine(); command = getLine.split(" "); if (command[0].equals(PUSHLEFT)) { if (checkFull(deque.size(), sizeDeque)) { System.out.println(QUEUEFULL); } else { deque.addFirst(Integer.parseInt(command[1])); System.out.println(PSLEFT + command[1]); } } else if (command[0].equals(PUSHRIGHT)) { if (checkFull(deque.size(), sizeDeque)) { System.out.println(QUEUEFULL); } else { deque.addLast(Integer.parseInt(command[1])); System.out.println(PSRIGHT + command[1]); } } else if (command[0].equals(POPLEFT)) { if (deque.isEmpty()) { System.out.println(QUEUEEMPTY); } else { System.out.println(POSLEFT + deque.getFirst()); deque.removeFirst(); } } else if (command[0].equals(POPRIGHT)) { if (deque.isEmpty()) { System.out.println(QUEUEEMPTY); } else { System.out.println(POSRIGHT + deque.getLast()); deque.removeLast(); } } n--; } } } private boolean checkFull(int size, int sizeDeque) { return size == sizeDeque; } }

LightOJ[1303]

Problem 
1303 - Ferris Wheel

Idea Flow

Input_Constraint ~ Total number of passengers and total number of seats are 20, 20 respectively.

Question Hints ~ Cake Walk

Conclusion ~ proper use of indexing and arrayList can solve the problem.

Learnt lesson ~ Solver need to analyze the time complexity.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82

package net.egork; import java.util.ArrayList; import java.util.List; import java.util.Scanner; import java.io.PrintWriter; public class L1303 { private static final String CASE = "Case"; private static final String SPACE = " "; private static final String COLON = ":"; int n, m, cursor; private int totalTime; public void solve(int testNumber, Scanner in, PrintWriter out) { int testCase; testCase = in.nextInt(); for (int i = 1; i <= testCase; i++) { cursor = 0; totalTime = 0; n = in.nextInt(); m = in.nextInt(); int dp[][] = new int[n + 2][m + 2]; int circularArray[] = new int[m + 2]; List<Integer> integerList = new ArrayList<Integer>(); for (int j = 1; j <= n; j++) integerList.add(j); do { cursor = (cursor + 1) % m; int outPerson = circularArray[cursor]; circularArray[cursor] = 0; if (isNeeded(dp, outPerson)) { integerList.add(outPerson); } int findPerson = getPerson(integerList, dp); if (findPerson >= 0) { int personNumber = integerList.get(findPerson); dp[personNumber][cursor] = 1; integerList.remove(findPerson); circularArray[cursor] = personNumber; } totalTime += 5; } while (!isFWEMPTY(circularArray)); System.out.println(CASE + SPACE +i + COLON + SPACE + totalTime); } } private boolean isFWEMPTY(int[] circularArray) { for (int i = 0; i < m; i++) { if (circularArray[i] > 0) return false; } return true; } private boolean isNeeded(int[][] dp, int person) { if (person == 0) return false; for (int i = 0; i < m; i++) { if (dp[person][i] == 0) return true; } return false; } private int getPerson(List<Integer> integerList, int[][] dp) { int sz = integerList.size(); for (int i = 0; i < sz; i++) { if (dp[integerList.get(i)][cursor] == 0) { return i; } } return -1; } }

LightOJ [1113]

Problem 
1113 - Discover the Web

Idea Flow

Input_Constraint ~ All operation must be done in O(1)

Question Hints ~ Cake Walk

Conclusion ~ Just follow what problem statement tells.

Learnt lesson ~ Solver need to analyze the time complexity.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

package net.egork; import java.util.ArrayList; import java.util.Scanner; import java.io.PrintWriter; import java.util.Stack; public class L1113 { private static final String FORWARD = "FORWARD"; private static final String VISIT = "VISIT"; private static final String BACK = "BACK"; private static final String QUIT = "QUIT"; private static final String IGNORED = "Ignored"; private static final String URL = "http://www.lightoj.com/"; public void solve(int testNumber, Scanner in, PrintWriter out) { int testCase; testCase = in.nextInt(); String query[]; String current; for (int i = 1; i <= testCase; i++) { System.out.println("Case " + i + ":"); Stack<String> forwardStack = new Stack<String>(); Stack<String> backwardStack = new Stack<String>(); current = URL; while (true) { query = in.nextLine().split(" "); if (query[0].equals(FORWARD)) { if (forwardStack.isEmpty()) { System.out.println(IGNORED); } else { backwardStack.add(current); current = forwardStack.peek(); forwardStack.pop(); System.out.println(current); } } else if (query[0].equals(VISIT)) { backwardStack.push(current); forwardStack.clear(); current = query[1]; System.out.println(current); } else if (query[0].equals(BACK)) { if (backwardStack.isEmpty()) { System.out.println(IGNORED); } else { forwardStack.add(current); current = backwardStack.peek(); backwardStack.pop(); System.out.println(current); } } else if (query[0].equals(QUIT)) { break; } } } } }

SRM 304

Idea Flow

Input Constraint ~  Given set of N points and we need to form convex polygon in order to                                                   maximize the area. 

Question Hints    ~  Solution of an triangle can be use for polygon.

Conclusion           ~  Different start points starting from n-1| 0 |1 and dp can be found.

Learnt lesson       ~  Geometric problem are easy, just need time to understand what they want.

Algorithm 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

best[0] = best[1] = 0; // Here I am moving the point 1. for(int i = 2 ; i < n ; i++) { best[i] = max(best[i - 1], best[i - 2] + sqrtIt(x[i], y[i], x[i-2], y[i-2])); } double res = best[n - 1]; // Now lets try moving the point 0. best[0] = 0; best[1] = sqrtIt(x[n-1], y[n-1], x[1], y[1]); best[2] = best[1]; for(int i = 3; i < n; i++ ) { best[i] = max(best[i - 1], best[i-2] + sqrtIt(x[i], y[i], x[i-2], y[i-2])); } res = max(best[n - 1], res); //Now moving point n - 1. best[0] = sqrtIt(x[n-2], y[n-2], x[0], y[0]); best[1] = best[0]; for(int i = 2 ; i < n - 1 ; i++) { best[i] = max(best[i - 1], best[i-2] + sqrtIt(x[i], y[i], x[i-2], y[i-2])); } res = max(best[n - 2], res);

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