I am doing this programming challenge which can be found at www.interviewstreet.com (its the first challenge worth 30 points).
When I submitted the solution, I was returned a result which said that the answer was wrong because it only passed 1/11 test cases. However, I feel have tested various cases and do not understand what I am doing wrong. It would be helpful to know what those test cases could be so that I can test my program.
Here is the question (in between the grey lines below):
Quadrant Queries (30 points)
There are N points in the plane. The ith point has coordinates (xi, yi). Perform the following queries:
1) Reflect all points between point i and j both including along the X axis. This query is represented as "X i j"
2) Reflect all points between point i and j both including along the Y axis. This query is represented as "Y i j"
3) Count how many points between point i and j both including lie in each of the 4 quadrants. This query is represented as "C i j"
Input:
The first line contains N, the number of points. N lines follow.
The ith line contains xi and yi separated by a space.
The next line contains Q the number of queries. The next Q lines contain one query each, of one of the above forms.
All indices are 1 indexed.
Output:
Output one line for each query of the type "C i j". The corresponding line contains 4 integers; the number of points having indices in the range [i..j] in the 1st,2nd,3rd and 4th quadrants respectively.
Constraints:
1 <= N <= 100000
1 <= Q <= 100000
You may assume that no point lies on the X or the Y axis.
All (xi,yi) will fit in a 32-bit signed integer
In all queries, 1 <=i <=j <=N
Sample Input:
4
1 1
-1 1
-1 -1
1 -1
5
C 1 4
X 2 4
C 3 4
Y 1 2
C 1 3
Sample Output:
1 1 1 1
1 1 0 0
0 2 0 1
Explanation:
When a query says "X i j", it means that take all the points between indices i and j both including and reflect those points along the X axis. The i and j here have nothing to do with the co-ordinates of the points. They are the indices. i refers to point i and j refers to point j
'C 1 4' asks you to 'Consider the set of points having index in {1,2,3,4}. Amongst those points, how many of them lie in the 1st,2nd,3rd and 4th quads respectively?' The answer to this is clearly 1 1 1 1.
Next we reflect the points between indices '2 4' along the X axis. So the new coordinates are :
1 1
-1 -1
-1 1
1 1
Now 'C 3 4' is 'Consider the set of points having index in {3,4}. Amongst those points, how many of them lie in the 1st,2nd,3rd and 4th quads respectively?' Point 3 lies in quadrant 2 and point 4 lies in quadrant 1. So the answer is 1 1 0 0
I'm coding in PHP and the method for testing is with STDIN and STDOUT.
Any ideas on difficult test cases to test my code with? I don't understand why I am failing 10 / 11 test cases.
Also, here is my code if you're interested:
// The global variable that will be changed
$points = array();
/******** Functions ********/
// This function returns the number of points in each quadrant.
function C($beg, $end) {
// $quad_count is a local array and not global as this gets reset for every C operation
$quad_count = array("I" => 0, "II" => 0, "III" => 0, "IV" => 0);
for($i=$beg; $i<$end+1; $i++) {
$quad = checkquad($i);
$quad_count[$quad]++;
}
return $quad_count["I"]." ".$quad_count["II"]." ".$quad_count["III"]." ".$quad_count["IV"];
}
// Reflecting over the x-axis means taking the negative value of y for all given points
function X($beg, $end) {
global $points;
for($i=$beg; $i<$end+1; $i++) {
$points[$i]["y"] = -1*($points[$i]["y"]);
}
}
// Reflecting over the y-axis means taking the negative value of x for all given points
function Y($beg, $end) {
global $points;
for($i=$beg; $i<$end+1; $i++) {
$points[$i]["x"] = -1*($points[$i]["x"]);
}
}
// Determines which quadrant a given point is in
function checkquad($i) {
global $points;
$x = $points[$i]["x"];
$y = $points[$i]["y"];
if ($x > 0) {
if ($y > 0) {
return "I";
} else {
return "IV";
}
} else {
if ($y > 0) {
return "II";
} else {
return "III";
}
}
}
// First, retrieve the number of points that will be provided. Make sure to check constraints.
$no_points = intval(fgets(STDIN));
if ($no_points > 100000) {
fwrite(STDOUT, "The number of points cannot be greater than 100,000!
");
exit;
}
// Remember the points are 1 indexed so begin key from 1. Store all provided points in array format.
for($i=1; $i<$no_points+1; $i++) {
global $points;
list($x, $y) = explode(" ",fgets(STDIN)); // Get the string returned from the command line and convert to an array
$points[$i]["x"] = intval($x);
$points[$i]["y"] = intval($y);
}
// Retrieve the number of operations that will be provied. Make sure to check constraints.
$no_operations = intval(fgets(STDIN));
if($no_operations > 100000) {
fwrite(STDOUT, "The number of operations cannot be greater than 100,000!
");
exit;
}
// Retrieve the operations, determine the type and send to the appropriate functions. Make sure i <= j.
for($i=0; $i<$no_operations; $i++) {
$operation = explode(" ",fgets(STDIN));
$type = $operation[0];
if($operation[1] > $operation[2]) {
fwrite(STDOUT, "Point j must be further in the sequence than point i!
");
exit;
}
switch ($type) {
case "C":
$output[$i] = C($operation[1], $operation[2]);
break;
case "X":
X($operation[1], $operation[2]);
break;
case "Y":
Y($operation[1], $operation[2]);
break;
default:
$output[$i] = "Sorry, but we do not recognize this operation. Please try again!";
}
}
// Print the output as a string
foreach($output as $line) {
fwrite(STDOUT, $line."
");
}
UPDATE:
I finally found a test case for which my program fails. Now I am trying to determine why. This is a good lesson on testing with large numbers.
10
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
12
C 1 10
X 1 3
C 5 5
Y 2 10
C 10 10
C 1 10
X 1 3
C 5 5
Y 2 10
C 10 10
X 3 7
C 9 9
I am going to test this properly by initializing an error array and determining which operations are causing an issue.
