"Laser treatment" SPOJ challenge

Question

I am trying to solve this problem on SPOJ Brazil. I'm trying to approach the problem with a series of logical conditions and my code looks like this and it works perfectly.

#include <stdio.h>

typedef struct {
    int y1;
    int x1;
    int x2;
    int y2;
}coordinate;



int main(){

    int N, C, i, j, xi, xf, nbacterias;

    coordinate coord[100000];

    scanf ("%d %d", &N, &C);

    for (i = 0; i < N; i++){
        scanf ("%d %d %d %d", &coord[i].x1, &coord[i].y1, &coord[i].x2, &coord[i].y2);
    }


    for (i = 0; i < C; i++){
        scanf ("%d %d", &xi, &xf);
        nbacterias = 0;

        for (j = 0; j< N; j++){
            if ((coord[j].x1 >= xf && coord[j].x2 >= xf) || (coord[j].x2 <= xi && coord[j].x1 <= xi))
                nbacterias++;
            else if ((xf < coord[j].x2 && xf > coord[j].x1 && xi <= coord[j].x1 && xi < coord[j].x2) || (xf < coord[j].x1 && xf > coord[j].x2 && xi <= coord[j].x2 && xi < coord[j].x1))
                nbacterias++;            
            else if ((xi > coord[j].x2 && xi < coord[j].x1 && xf >= coord[j].x1 && xf > coord[j].x2) || (xi>coord[j].x1 && xi < coord[j].x2 && xf >= coord[j].x2 && xf > coord[j].x1))
                nbacterias++;
            else if ((coord[j].x1 < xi && coord[j].x2 > xf) || (coord[j].x2 < xi && coord[j].x1 > xf))
                nbacterias = nbacterias + 2;

        }
        printf ("%d\n", nbacterias);
    }

    return 0;
}

As you can see, I created a coordinate struct and created a series of conditions in which the bacteria could be divided (in two, when they get hit by the laser in the middle; in one, when the laser cuts out a part of it; when the laser doesn't hit the bacteria at all, leaving the whole bacteria; and when the laser hits the entire bacteria, leaving no parts at all).

This solution works, you can test it with the cases given in the problem link I pasted up there. The problem is that when I submit my code it exceeds the time limit. Any ideas on how to optimize this code or if I am missing some gimmick here? By the way, I'm pretty new to competitive programming, so I may not completely grasp complex answers.

Answer 1

Style

Your code looks nice. It is not splitted into small functions and it is not commented but it's easy to understand anyway.

A few easy things could be done to make it more beautiful :

• define variables in the smallest possible scope. With the right version of C, this also include defining variables as part of the for syntax. This makes the code much clearer as it is easier to see where the variable is used.

• define a variable to refer to coord[j].

• use += instead of repeating variable = variable + something.

At this stage, the code looks like :

int main(){
    coordinate coord[100000];

    int N, C;
    scanf ("%d %d", &N, &C);

    for (int i = 0; i < N; i++){
        scanf ("%d %d %d %d", &coord[i].x1, &coord[i].y1, &coord[i].x2, &coord[i].y2);
    }


    for (int i = 0; i < C; i++){
        int xi, xf;
        scanf ("%d %d", &xi, &xf);
        int nbacterias = 0;

        for (int j = 0; j< N; j++){
            coordinate c = coord[j];
            if ((c.x1 >= xf && c.x2 >= xf) || (c.x2 <= xi && c.x1 <= xi))
                nbacterias++;
            else if ((xf < c.x2 && xf > c.x1 && xi <= c.x1 && xi < c.x2) || (xf < c.x1 && xf > c.x2 && xi <= c.x2 && xi < c.x1))
                nbacterias++;
            else if ((xi > c.x2 && xi < c.x1 && xf >= c.x1 && xf > c.x2) || (xi>c.x1 && xi < c.x2 && xf >= c.x2 && xf > c.x1))
                nbacterias++;
            else if ((c.x1 < xi && c.x2 > xf) || (c.x2 < xi && c.x1 > xf))
                nbacterias+=2;

        }
        printf ("%d\n", nbacterias);
    }

    return 0;
}

Tests

Before trying to make things faster, it is a good idea to write automatic tests. At the moment, your code relies on input, output so it is not really easy to tests. It could be nice to separate the concerns: the input/output on one hand, the logic on the other hand.

Let's write a function to perform the logic. Now, we can reuse data from the problem to write a few tests :

#include <stdio.h>
#include <assert.h>

typedef struct {
    int x1;
    int y1;
    int x2;
    int y2;
}coordinate;

int nb_bacteria_after_beam(coordinate coord[], int N, int xi, int xf)
{
    int nbacterias = 0;

    for (int j = 0; j< N; j++){
        coordinate c = coord[j];
        if ((c.x1 >= xf && c.x2 >= xf) || (c.x2 <= xi && c.x1 <= xi))
            nbacterias++;
        else if ((xf < c.x2 && xf > c.x1 && xi <= c.x1 && xi < c.x2) || (xf < c.x1 && xf > c.x2 && xi <= c.x2 && xi < c.x1))
            nbacterias++;            
        else if ((xi > c.x2 && xi < c.x1 && xf >= c.x1 && xf > c.x2) || (xi>c.x1 && xi < c.x2 && xf >= c.x2 && xf > c.x1))
            nbacterias++;
        else if ((c.x1 < xi && c.x2 > xf) || (c.x2 < xi && c.x1 > xf))
            nbacterias+=2;
    }
    return nbacterias;
}


int automatic_tests()
{
    coordinate coord[] = {{1, 0, 4, 0}};
    assert(nb_bacteria_after_beam(coord, 1, 0, 2) == 1);
    assert(nb_bacteria_after_beam(coord, 1, 3, 5) == 1);
    assert(nb_bacteria_after_beam(coord, 1, 2, 3) == 2);
    assert(nb_bacteria_after_beam(coord, 1, 0, 5) == 0);
    coordinate coord2[] = {{2, 0, 4, 0}, {2, 0, 4, 0}};
    assert(nb_bacteria_after_beam(coord2, 2, 0, 1) == 2);
    assert(nb_bacteria_after_beam(coord2, 2, 1, 2) == 2);
    assert(nb_bacteria_after_beam(coord2, 2, 2, 3) == 2);
    assert(nb_bacteria_after_beam(coord2, 2, 3, 4) == 2);
    assert(nb_bacteria_after_beam(coord2, 2, 4, 5) == 2);
    assert(nb_bacteria_after_beam(coord2, 2, 5, 6) == 2);
    coordinate coord3[] = {{0, 0, 3, 5}, {3, 5, 0, 2}};
    assert(nb_bacteria_after_beam(coord3, 2, 0, 3) == 0);
    assert(nb_bacteria_after_beam(coord3, 2, 1, 2) == 4);
    assert(nb_bacteria_after_beam(coord3, 2, 2, 7) == 2);
    return 0;
}

int stdin_tests()
{
    coordinate coord[100000];

    int N, C;
    scanf ("%d %d", &N, &C);

    for (int i = 0; i < N; i++){
        scanf ("%d %d %d %d", &coord[i].x1, &coord[i].y1, &coord[i].x2, &coord[i].y2);
    }

    for (int i = 0; i < C; i++){
        int xi, xf;
        scanf ("%d %d", &xi, &xf);
        printf ("%d\n", nb_bacteria_after_beam(coord, N, xi, xf));
    }

    return 0;
}

int main(){
    return automatic_tests();
}

Please note that I had to reorder members of your struct so that I can simply reuse tests cases from the problem.

Now, I assume (which might not be nor true nor wise) that if anything goes wrong during my changes, I'll detect it almost instantly.

Better performances

At the moment, your code works by implementing the functionality with a straight-forward algorithm considering the different cases.

A simple observation can lead to better algorithm. For instance, if we order (x1,y1) and (x2,y2) in such a way that the left-most end is (x1,y2) and the right-most end is (x2,y2) then we have a much smaller number of situations. Assuming xi < xf, we have a bacteria on the left if and only if x1 < xi and a bacteria on the right if and only if x2 > xf (with the 4 combinations possible : right, left, right + left, none).

Before trying to perform any optimisation, we should try to be in a situation where performances can be properly measured : at the moment, the times are much too short to be analysed and the datasets might not correspond to situations leading to timeout.

Before I go further, the assumption here is that your code is not efficient enough when the number of queries performed on a sample gets huge. (This assumption is based on the fact that the values can be much bigger for the number of cases than the number of bactoeria). We can reproduce such a case by putting the lines doing assert(nb_bacteria_after_beam(....)) in for loops. This gives measurable times on my configuration :

int automatic_tests()
{
    int nb_tests = 10000000;
    coordinate coord[] = {{1, 0, 4, 0}};
    coordinate coord2[] = {{2, 0, 4, 0}, {2, 0, 4, 0}};
    coordinate coord3[] = {{0, 0, 3, 5}, {3, 5, 0, 2}};
    for (int i = 0; i < nb_tests; i++)
    {
        assert(nb_bacteria_after_beam(coord, 1, 0, 2) == 1);
        assert(nb_bacteria_after_beam(coord, 1, 3, 5) == 1);
        assert(nb_bacteria_after_beam(coord, 1, 2, 3) == 2);
        assert(nb_bacteria_after_beam(coord, 1, 0, 5) == 0);
        assert(nb_bacteria_after_beam(coord2, 2, 0, 1) == 2);
        assert(nb_bacteria_after_beam(coord2, 2, 1, 2) == 2);
        assert(nb_bacteria_after_beam(coord2, 2, 2, 3) == 2);
        assert(nb_bacteria_after_beam(coord2, 2, 3, 4) == 2);
        assert(nb_bacteria_after_beam(coord2, 2, 4, 5) == 2);
        assert(nb_bacteria_after_beam(coord2, 2, 5, 6) == 2);
        assert(nb_bacteria_after_beam(coord3, 2, 0, 3) == 0);
        assert(nb_bacteria_after_beam(coord3, 2, 1, 2) == 4);
        assert(nb_bacteria_after_beam(coord3, 2, 2, 7) == 2);
    }
    return 0;
}

On such a dataset, I can already see the benefits of the idea described above. Correspond code looks like :

int nb_bacteria_after_beam(coordinate coord[], int N, int xi, int xf)
{
    int nbacterias = 0;
    assert(xi < xf);

    for (int j = 0; j< N; j++){
        coordinate c = coord[j];
        int x1 = c.x1;
        int x2 = c.x2;
        if (x1 > x2)
        {
            // swap
            int tmp = x1;
            x1 = x2;
            x2 = tmp;
        }
        if (x1 < xi)
            nbacterias++;
        if (x2 > xf)
            nbacterias++;
    }
    return nbacterias;
}

When the number of cases gets huge indeed, it might be worth performing some preprocessing to ensure queries can be performed more efficiently.

We can easily write a procedure to prepare our datasets in such a way that we can apply the trick described above directly.

This leads to much better performances indeed :

void prepare_dataset(coordinate coord[], int N)
{
    for (int j = 0; j< N; j++){
        if (coord[j].x1 > coord[j].x2){
            // swap (to keep things nice, y coord has to be moved too even if it is not useful)
            int tmp = coord[j].x1;
            coord[j].x1 = coord[j].x2;
            coord[j].x2 = tmp;
            tmp = coord[j].y1;
            coord[j].y1 = coord[j].y2;
            coord[j].y2 = tmp;
        }
    }
}

int nb_bacteria_after_beam(coordinate coord[], int N, int xi, int xf)
{
    int nbacterias = 0;
    assert(xi < xf);

    for (int j = 0; j< N; j++){
        coordinate c = coord[j];
        assert(c.x1 <= c.x2);
        if (c.x1 < xi)
            nbacterias++;
        if (c.x2 > xf)
            nbacterias++;
    }
    return nbacterias;
}


int automatic_tests()
{
    int nb_tests = 10000000;
    coordinate coord[] = {{1, 0, 4, 0}};
    prepare_dataset(coord, 1);
    coordinate coord2[] = {{2, 0, 4, 0}, {2, 0, 4, 0}};
    prepare_dataset(coord2, 2);
    coordinate coord3[] = {{0, 0, 3, 5}, {3, 5, 0, 2}};
    prepare_dataset(coord3, 2);
    for (int i = 0; i < nb_tests; i++)
    {
        assert(nb_bacteria_after_beam(coord, 1, 0, 2) == 1);
        assert(nb_bacteria_after_beam(coord, 1, 3, 5) == 1);
        assert(nb_bacteria_after_beam(coord, 1, 2, 3) == 2);
        assert(nb_bacteria_after_beam(coord, 1, 0, 5) == 0);
        assert(nb_bacteria_after_beam(coord2, 2, 0, 1) == 2);
        assert(nb_bacteria_after_beam(coord2, 2, 1, 2) == 2);
        assert(nb_bacteria_after_beam(coord2, 2, 2, 3) == 2);
        assert(nb_bacteria_after_beam(coord2, 2, 3, 4) == 2);
        assert(nb_bacteria_after_beam(coord2, 2, 4, 5) == 2);
        assert(nb_bacteria_after_beam(coord2, 2, 5, 6) == 2);
        assert(nb_bacteria_after_beam(coord3, 2, 0, 3) == 0);
        assert(nb_bacteria_after_beam(coord3, 2, 1, 2) == 4);
        assert(nb_bacteria_after_beam(coord3, 2, 2, 7) == 2);
    }
    return 0;
}

More performance

This is pretty good but we haven't really changed the complexity of the algorithm. It used to be 0(N*C) and it still is. Only the constant factor has changed (basically, we still perform a huge number of operation considering all bacteria for all inputs, we just handle them in a more efficient way). What could be interesting (and is probably what is expected by the people who wrote the problems) would be to prepare the dataset in such a way that for a given input, you don't have to reconsider all bacteria again and again.

The point would be to be able to create some kind of summary of your dataset in such a way that you can easily determine the information you need. Basically, it boils down to determine how many items in a list are smaller or bigger than a value you'll be provided later. Indeed, the solution of the problem is the sum of the number of x1 such that x1 < xi and the number of x2 such that x2 > xf. An interesting idea could be to create a sorted array of the x1 values and a sorted array of the x2 values (don't forget that in order to have this trick to work, you first have to re-arrange x1,x2 in such a way that x1 < x2). Once this is done, the number of items smaller (or bigger) than a value can be determined with a binary search algorithm.

Unless I am mistaken, the complexity for such a strategy would be : 0( N*log(N) + C * log(N)) because sorting is 0(n*log(n)) and binary search is O(log(n)).

This should be much faster. I'll let you consider this :-)