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 

}