My solution to this programming challenge is wrong because it outputs the wrong answer for 10/11 test cases. What are those test cases?

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 <= 10000开发者_StackOverflow社区0

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!\n");
    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!\n");
    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!\n");
        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."\n");
}

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.

---

I discovered a test case that failed and understood why. I am posting this answer here so it's clear to everyone.

I placed a constraint on the program so that j must be greater than i, otherwise an error should be returned. I noticed an error with the following test case:

10
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1
C 2 10

The error returned for the operation C. Essentially the program believed that "2" was greater than "10". The reason for this I discovered was the following:

When using fgets(), a string is returned. If you perform string operations such as explode() or substr() on that line, you are converting the numbers in that initial string into a string again. So this means that the 10 becomes "10" and then after string operations becomes "0".

One solution to this is to use the sscanf() function and basically tell the program to expect a number. Example: for "C 2 10" you could use:
$operation_string = fgets(STDIN);
list($type, $begpoint, $endpoint) = sscanf($operation_string, "%s %d %d");

I submitted the new solution using sscanf() and now have 3/11 test cases passed. It did not check any more test cases because the CPU time limit was exceeded. So, now I have to go back and optimize my algorithm.

Back to work! :)

---

To answer, "What are those test cases?" Try this "solution":

<?php
$postdata = http_build_query(
    array(
        'log' => file_get_contents('php://stdin')
    )
);

$opts = array('http' =>
    array(
        'method'  => 'POST',
        'header'  => 'Content-type: application/x-www-form-urlencoded',
        'content' => $postdata
    )
);

$context  = stream_context_create($opts);

file_get_contents('http://myserver/answer.php', false, $context);
?>

On your server:

<?php
$fp = fopen('/tmp/answers.log', 'a');
fputs($fp, $_POST['log']."\n");
fclose($fp);
?>

Edit:

I did that. And came up with this being your main problem (I think):

$operation = explode(" ",fgets(STDIN));

Change that to:

$operation = explode(" ",trim(fgets(STDIN)));

Because otherwise "9" > "41 " due to string comparison. You should make that fix in any place you read a line.

---

As far as I guess, this solution won't work. Even if you solve the Wrong Answer problem, the solution will time out.

I was able to figure out a way for returning the quadrants count in O(1) time.

But not able to make the reflections in lesser time. :(