Optimizing a program C++

Question

I have to create a program, which counts bursted baloons, like from ZUMA. If I have a line with 3 or more baloons with the same color this sequence will burst. So in input, I have number of ballons (3 <= N <= 10^5) , and line with numbers (line with baloons color (1 <= сi <= 100) ), with 1 sequence for sure. I have to output number of bursted baloons. I have a programm, but it is working longer than 4000msv sometimes. How can I make it working faster?

  #include <iostream>
#include <string>
#include <vector>
using namespace std;


int Fmax(int n, const string& f){
int  max;
vector<int> k(n);

int i, j, p = 0;
for (i = 0; i <= n; i++)
{
    k[i] = 0;
}

for (i = 0; i <= n; i++)
{
    for (j = i; j <= n; j++)
    {

        if (f[i] == f[j])
        {
            k[p]++;

        }
        else break;
    }
    p++;
}

max = k[0];
for (i = 0; i <= p; i++){ if (max <= k[i]){ max = k[i]; } }
return max;
}
string pog(int n){
int d;
string doa;
for (int i = 1; i <= n; i++){
    cin >> d;
    doa += (char)d;
}

return doa;
}
void main(){
int i, sc = 1, bf = 1;
string f;
int len;
cin >> i;
f = pog(i);
len = i;

while (Fmax(f.length(), f) >= 3){

    for (int c = 1; c <= f.length(); c++){

        if (f[c] == f[c - 1]){
            if (sc == 1){ bf = c - 1; }
            sc++;
        }
        else{
            if (sc >= 3){ f.erase(bf, sc);  sc = 1; break; }
            sc = 1;
        }



    }
}
cout << len - f.length() << endl;


}

Any help is warmly welcome.

Read [getchar_unlocked( ) VS scanf() VS cin](http://stackoverflow.com/questions/9052757/getchar-unlocked-vs-scanf-vs-cin) — Arun A S, Mar 24 '15 at 13:50
`void main` isn't valid C++. Why are you mixing int and char so much? — Neil Kirk, Mar 24 '15 at 13:50
**Very important: Profile.** Use a profile tool or use clock and run for 1E06 iterations; take average. — Thomas Matthews, Mar 24 '15 at 14:27

score 2 · Answer 1 · answered Mar 24 '15 at 13:50

2

You are leaking memory. Use vectors to avoid that.

Why do you need to create array? Why not use the string directly?

Pass strings which aren't modified by const reference to avoid copies.

answered Mar 24 '15 at 13:50

Neil Kirk

21,327
9
53
91

How can i do it? (Pass strings which aren't modified by const reference to avoid copies.) – Yuriy Gavrilin Mar 24 '15 at 15:34
@ЮрийГаврилин `int Fmax(int n, const string& f)` – Neil Kirk Mar 24 '15 at 15:41
Kirlk Ok, thanks. And about vectors, i have to use them instead of dynamic arrays? – Yuriy Gavrilin Mar 24 '15 at 16:05
@ЮрийГаврилин It is recommended as they are less error prone. Note that their values are set to 0 automatically. – Neil Kirk Mar 24 '15 at 16:05
I changed arrays to vector, and passing strings, and deleted this strange array in Fmax before/. What else can i do? – Yuriy Gavrilin Mar 24 '15 at 16:18
The only remaining thing is to see if you can use a more efficient algorithm, but I don't know the answer to that. – Neil Kirk Mar 24 '15 at 16:23

score 0 · Answer 2 · answered Mar 24 '15 at 14:25

0

Use constant variables for the lengths:

const unsigned int f_length = f.length();
while (Fmax(f_length, f) >= 3){

  for (int c = 1; c <= f_length ; c++){

This helps the compiler reduce the number of calls to the length method.

answered Mar 24 '15 at 14:25

Thomas Matthews

56,849
17
98
154

I guess i cant Use constant variables for the lengths:, cause length is changing sometimes – Yuriy Gavrilin Mar 24 '15 at 15:31
I really doubt this will make any observable difference. – Neil Kirk Mar 24 '15 at 15:42

Optimizing a program C++

2 Answers2