Skip to main content
Code Review

Return to Question

Tweeted twitter.com/#!/StackCodeReview/status/572182671608193024
deleted 29 characters in body; edited tags; edited title
Source Link
Jamal
Jamal
  • 35.2k
  • 13
  • 134
  • 238

Code in C exceeding time limit on "Laser treatment" SPOJ challenge

I am trying to solve this problemthis problem on SPOJ Brazil, which is translated here:

https://translate.google.com.br/translate?sl=pt&tl=en&js=y&prev=_t&hl=pt-BR&ie=UTF-8&u=http%3A%2F%2Fwww.spoj.com%2Fproblems%2FLASER08%2F&edit-text=&act=url

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

As you can see, I created a coordinate structstruct 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

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. Anyway, thanks!

Code in C exceeding time limit on SPOJ

I am trying to solve this problem on SPOJ Brazil, which is translated here:

https://translate.google.com.br/translate?sl=pt&tl=en&js=y&prev=_t&hl=pt-BR&ie=UTF-8&u=http%3A%2F%2Fwww.spoj.com%2Fproblems%2FLASER08%2F&edit-text=&act=url

I'm trying to approach the problem with a series of logical conditions and my code looks like this and it works perfectly:

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. Anyway, thanks!

"Laser treatment" SPOJ challenge

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.

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.

Source Link
Lucas Sartori
Lucas Sartori
  • 53
  • 3

Code in C exceeding time limit on SPOJ

I am trying to solve this problem on SPOJ Brazil, which is translated here:

https://translate.google.com.br/translate?sl=pt&tl=en&js=y&prev=_t&hl=pt-BR&ie=UTF-8&u=http%3A%2F%2Fwww.spoj.com%2Fproblems%2FLASER08%2F&edit-text=&act=url

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. Anyway, thanks!