Time Limit Exceeded c++ algorithm

Question

I'm currently doing an algorithm that given a sequence, checks if there is a subsequence which sum equals a given value. If I have:

where 3 8 and 7 5 are the (sequence size, value) and 0 0 tells us we reached the end. In this case it would print :

SUBSEQUENCE NOT FOUND
SUBSEQUENCE FOUND AT POSITION 2

My question is, why am I getting a Time Limit Exceeded when I submit it to Mooshak? Here goes the code:

#include <iostream>
#include <stdio.h>
#include <stdlib.h>

int main(){

    int tamanho;
    int valor;
    int soma, numero;
    int sequencia[100];



    while(1){ 

        scanf("%d %d", &tamanho, &valor);

        if(tamanho != 0 && valor != 0){

            for(int i = 1; i <= tamanho; i++){
                scanf("%d", &numero);
                printf("%d\n", i);
                sequencia[i] = numero;
                printf("%d\n", i);
            }

            for(int i = 1; i < tamanho; i++){
                printf("i");
                for(int j = i; j < tamanho; j++){
                    soma = 0;
                    printf("j");
                    for (int z = i; z < j; z++){
                        printf("z");
                        soma = soma + sequencia[z];
                    }
                    if(soma == valor){
                        printf("SUBSEQUENCIA NA POSICAO %d \n", i);
                        exit(0);
                    }
                }
            }
            printf("SUBSEQUENCIA NAO ENCONTRADA\n");    
        }   
    }

    return 0;

}

Please, post the link to the problem, or paste here the input limits. — Juan Lopes, Feb 10 '16 at 18:00
Are the values in the sequences guaranteed to be positive (or at least non-negative)? — Ted Hopp, Feb 10 '16 at 18:01
You only exit the `while (1)` loop when the subsequence was found (in fact, you exit the program); if no subsequence is ever found, your program busy waits forever, which will eventually cause a timeout. — Max Lybbert, Feb 10 '16 at 18:01
Input goes from 0 to 1000, Core size 0 Kb Data of execute 32 Mb Execution output 500 Kb Stack of execute 1 Mb Program code 100 Kb Real time timeout 60 sec Compilation timeout 60 sec Execution timeout * 5 sec — Pedro Caseiro, Feb 10 '16 at 18:02
@MaxLybbert - I think you found the problem. You should post a fix as the answer. — Ted Hopp, Feb 10 '16 at 18:03
Mooshak is a system for managing programming contests on the Web — Pedro Caseiro, Feb 10 '16 at 18:04
@PedroCaseiro `for(int i = 1; i <= tamanho; i++)` Arrays start from 0, not 1. If you input 100 values in `tamanho`, you have a memory overwrite. — PaulMcKenzie, Feb 10 '16 at 18:18
@PedroCaseiro WTH is a _Time limit exceeded_?? New kind of exception I didn't heard of yet? (I hate OJ questions) — πάντα ῥεῖ, Feb 10 '16 at 18:24
@πάντα - It seems like it's an error message from the Mooshak contest system. — Ted Hopp, Feb 10 '16 at 18:43
Already solved the time limit exceeded. It was what @maxLybbert said :) Thanks. — Pedro Caseiro, Feb 10 '16 at 18:46
BTW, with cumulative sum, solution can be reduced to `O(n²)` instead of `O(n^3)` — Jarod42, Feb 10 '16 at 18:49
@jarod42 this is the first exercise and we're supposed to use this algorithm. Exercise number 2 uses cumulative sum. Thanks for the tip anyway :) — Pedro Caseiro, Feb 10 '16 at 18:52

score 1 · Accepted Answer · edited May 23 '17 at 10:28

You have an infinite loop. Inside your top-level while loop, replace this:

if(tamanho != 0 && valor != 0){
    // logic for one sequence
}

with:

if(tamanho == 0 && valor == 0){
    return 0;
}

// logic for one sequence

(This is based on the comment by @MaxLybbert).

P.S. As a general rule (there are some rare exceptions), you should use return 0; from main() instead of calling exit(0);. See the accepted answer in this thread for why. For your particular code, however, it doesn't make any difference.

Time Limit Exceeded c++ algorithm

1 Answers1