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());