HiveBrain v1.2.0
Get Started
← Back to all entries
patterncMinor

"Laser treatment" SPOJ challenge

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
time-limit-exceededcodereviewcstackoverflowprogramming-challenge
treatmentlaserspojchallenge

Problem

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 

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 = xf && coord[j].x2 >= xf) || (coord[j].x2  coord[j].x1 && xi  coord[j].x2 && xi  coord[j].x2 && xi = coord[j].x1 && xf > coord[j].x2) || (xi>coord[j].x1 && xi = coord[j].x2 && xf > coord[j].x1))
                nbacterias++;
            else if ((coord[j].x1  xf) || (coord[j].x2  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.

Solution

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 = xf && c.x2 >= xf) || (c.x2  c.x1 && xi  c.x2 && xi  c.x2 && xi = c.x1 && xf > c.x2) || (xi>c.x1 && xi = c.x2 && xf > c.x1))
                nbacterias++;
            else if ((c.x1  xf) || (c.x2  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 
#include 

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= xf && c.x2 >= xf) || (c.x2  c.x1 && xi  c.x2 && xi  c.x2 && xi = c.x1 && xf > c.x2) || (xi>c.x1 && xi = c.x2 && xf > c.x1))
            nbacterias++;
        else if ((c.x1  xf) || (c.x2  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 (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);
asser

Code Snippets

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;
}
#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();
}
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;
}
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;
}
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;
}

Context

StackExchange Code Review Q#82947, answer score: 5

Revisions (0)

No revisions yet.