April 18, 2018 The Hardest Easiest Problem in Topcoder history

With frequent SRMs on a year-round basis at Topcoder, the number of problems on the platform is constantly growing.
Consequently, some outliers are bound to arise. Some “unexpected” questions that catch many off guard, and furrow the eyebrows of many contestants. Questions whose solutions, need to be thought through thoroughly before diving into.
This week, we’re going to analyze the “hardest easiest problem” in Topcoder SRM history.
That would be “Segments”. “Segments” appeared in Single Round Match 303 Round 1 – Division II, and was the Level One Problem Statement.
The problem statement went in the following manner –
Given 2 line segments either parallel to the X-axis or Y-axis, output “NO” if the line segments do not intersect, output “POINT” if the line segments intersect at a point, and output “SEGMENT” if their intersection forms a line segment.
Now, the question is straightforward, and the input consisted of the start and end co-ordinates of the two line segments. 460 competitors viewed this problem statement of the 472 contestants during the SRM.
But 51.6% of contestants attempted submitting a solution, and the contest closed with this problem having a record-setting overall accuracy of just 9.32%.
Now, let’s analyze the top submissions.
dubna had the best score, solving the question in a little over 6 minutes in Java.
dubna’s solution, was an elegant ad-hoc approach, which unlike most of the contestants who failed system tests, didn’t have to resort to a plethora of corner cases.
dubna’s code is as follows –

public class Segments
{
 public String intersection (int[] s1, int[] s2)
 {
 s1 = norm (s1);
 s2 = norm (s2);
 int x1 = Math.max (s1 [0], s2 [0]);
 int y1 = Math.max (s1 [1], s2 [1]);
 int x2 = Math.min (s1 [2], s2 [2]);
 int y2 = Math.min (s1 [3], s2 [3]);
 if (x1 == x2 && y1 == y2)
 return "POINT";
 if (x1 <= x2 && y1 <= y2)
 return "SEGMENT";
 return "NO";
 }
 public int [] norm (int [] x)
 {
 return new int [] {Math.min (x [0], x [2]), Math.min (x [1], x [3]), Math.max (x [0], x [2]), Math.max (x [1], x [3])};
 }
}

So how does this work?
Let’s break it down.
The norm() function, takes as input the data of a line segment and normalizes them to the form ( {lower X coordinate, lower Y coordinate}, {higher X coordinate, higher Y coordinate} )
The rest of the implementation is easy to follow, but let’s understand the reason this simple approach works.
Consider a similar, albeit different problem statement.
Given two horizontal lines, identify if they intersect at all, or in a point, or in a segment.
The approach to this new problem is simple –
As both are horizontal, we need not bother about the Y-coordinate.
The trick here lies in handling the X-coordinates. Let my two line segments ‘A’ and ‘B’ have starting and ending coordinates (A1, A2) and (B1, B2) [where I normalize my line segments such that A1<=A2 and B1<=B2 and A1<=B1]
Now, I have 3 cases –
CASE 1: ‘A’ does not overlap at all with ‘B’, identified by the boolean expression –
(A2<B1) return “no intersection”;
Photo for below

(Red: ‘A’ | Blue: ‘B’)
CASE 2: ‘A’ touches ‘B’, and their intersection is a point –
(A2 == B1) return “point”;

CASE 3: ‘A’ overlaps partly or wholly with ‘B’ and their intersection forms a segment –
(A2>B1) return “segment”;

Yellow represents overlapping region
And that’s exactly what’s been done here. dubna has abstracted this one dimensional approach into a two-dimensional one, and retained the simplicity of the initial approach.
This approach was also adopted by the highest scorer in C++, yaoxu315 who solved this in a little over 8 minutes.
The implementation of the high scorer in C#, kylo was also clever.

using System;
using System.Collections;
using System.Collections.Generic;
public class Segments
{
 public string intersection(int[] s1, int[] s2)
 {
 byte[,] b = new byte[2010, 2010];
 for(int i = Math.Min(s1[0], s1[2]); i <= Math.Max(s1[0], s1[2]); i++)
 for(int j = Math.Min(s1[1], s1[3]); j <= Math.Max(s1[1], s1[3]); j++)
 {
 b[i + 1000, j + 1000]++;
 }
 for (int i = Math.Min(s2[0], s2[2]); i <= Math.Max(s2[0], s2[2]); i++)
 for (int j = Math.Min(s2[1], s2[3]); j <= Math.Max(s2[1], s2[3]); j++)
 {
 b[i + 1000, j + 1000]++;
 }
 int[] x = new int[3];
 for (int i = 0; i < 2010; i++)
 for (int j = 0; j < 2010; j++)
 x[b[i, j]]++;
 if (x[2] > 1)
 return "SEGMENT";
 if (x[2] == 1)
 return "POINT";
 return "NO";
 }
}

kylo’s solution, exploited the constraints of the problem statement cleverly and generated a grid to, quite literally, “draw” the entire input lines.
By using a positive offset of 1000 to handle negative coordinates, he marked all the points that the first line falls over, in the 2D array b as 1.
Then, iterating over all the points the second line falls over, he incremented the corresponding indices (coordinates) by 1.
Then he checked for the number of elements in the 2D array, whose value equals 2. If such elements occurred exactly once, the two lines intersected over a single point, while if the number of such elements occurred more than once, the lines intersected over a range of points and thus the answer would be “SEGMENT”. Else, the lines didn’t intersect at all.
Both the approaches were very clever, for this tricky problem. The second approach of generating the grid works well in general too for many geometry questions, however its application rests entirely on the size of the input constraints for it requires O(N^2) memory and perhaps even that much time to iterate over, depending on its purpose.
The first approach, although quite clever, may not seem as intuitive to many, but when abstracted from one-dimension to the next, scales up easily. A fun exercise is to now consider, if this two dimensional approach can be scaled up to a three dimensional one.