POLSKI SPOJ - wolne rozwiązanie zadania

Witam. Niedawno zacząłem rozwiązywać zadania na stronie POLSKI SPOJ. Rozwiązałem już kilka i postanowiłem rozwiązać zadanie z poziomu średniego. Wyniki są poprawne, ale sędzia oznajmia, że przekroczono limit czasu. W załączniku przesyłam zdjęcia jak rozpisałem te zadanie.

• Co można zrobić, aby przyspieszyć działanie algorytmu?
• Czy rozbicie na większą ilość własnych funkcji pomoże?
• A może mam zły sposób myślenia o tym zadaniu?

ZADANIE: SPEEDM - Pomiar Prędkości
http://pl.spoj.com/problems/SPEEDM/

#include <math.h>
#include <cstdio>
#include <vector>

using namespace std;

int t, n, max_v, min_v, _count1 = 0, _count2 = 1, licznik = 0, granica = 1;

vector <int> vector_tab;

int rec(int n)
{
    if(n==1)
        return 1;
    else
        return rec(n-1) + pow(2, n-1);
}


int dodaj(int n, int *tab)
{
    vector_tab.push_back( tab[0] );

        for(int j = 1; j < rec(n); j++)
        {
            if( j % 2 == 0)
            {
                vector_tab.push_back( vector_tab [_count1] + tab[_count2] );
                _count1++;
                licznik++;
            }
            else
                vector_tab.push_back( vector_tab [_count1] - tab[_count2] );

            if(licznik == granica){
                granica = 2*licznik;
                licznik=0;
                _count2++;
            }
        }

        min_v = vector_tab[0];
        max_v = vector_tab[0];

        for( int j = 1; j < rec(n); j++)
        {
            if( vector_tab[ j ] > max_v)
                 max_v = vector_tab[ j ];

            if( vector_tab[ j ] < min_v && vector_tab[j] >= 0)
                 min_v = vector_tab[ j ];
        }

        printf("%d %d \n",min_v, max_v);


        licznik = 0;
        granica = 1;
        _count1 = 0;
        _count2 = 1;
        delete [] tab;
        vector_tab.clear();
}


int main()
{
    scanf("%d", &t);

    for(int i = 0; i < t; i++)
    {
        scanf("%d", &n);
        int* tab = new int [n];

        for(int j = 0; j < n; j++)
            scanf("%d", &tab[j]);

        dodaj(n, tab);
    }


    return 0;
}

1. Popraw wcięcia: http://format.krzaq.cc/
2. Nie używaj zmiennych globalnych
3. Nazwij zmienne sensownie, a nie count1, count2
4. Po co używasz tablicy dynamicznej skoro znasz vector?

Masz za wolny algorytm. Algorytm wykładniczy prawie nigdy nie będzie dobry na spoju. Zauważ, że max można banalnie policzyć, natomiast min na oko trzeba policzyć używając programowania dynamicznego.

fooPrędkość maksymalną udało mi się znaleźć łatwiejszym sposobem. Wydaje mi się, że możliwa prędkość minimalna także jest wyszukiwana w poprawnych warunkach zapisanych poniżej. W konsoli wyniki są poprawne, lecz sędzia tym razem oznajmia, iż odpowiedź jest nie poprawna. Jakieś pomysły co mogę robić nie tak?

#include <iostream>
using namespace std;

int main()
{
	int t, n, minV=0, max=0, tmp, v1, v2;
	cin >> t;
	
	for(int i =0; i<t; i++)
	{
		cin>>n;
		int * deltaV = new int [n];
		
		for(int j = 0; j<n; j++)
		{	
			cin >> deltaV[j];
			max += deltaV[j];
		}
		
		minV = deltaV[0];
		
		for(int j = 1; j<n; j++)
		{
			tmp = minV;
			v1 = minV - deltaV[j];
			v2 = minV + deltaV[j];
			
			if(v1 >= 0)
				minV = min(v1, tmp);
			else if(v1 < 0 && j != 1)
			{	
				minV = min(v2,tmp);
				tmp = minV;
			}	
			else if(v1 < 0 && j ==1)
			{
				minV = v2;
				tmp = minV;
			}
			
			
		}
		cout<<minV<<" "<<max<<endl;
		max = minV = v1 = v2 = tmp = 0;
	}
	
	return 0;
}

Nie wiem czemu przestałeś używać vector na rzecz dynamicznej tablicy, szczególnie że masz wyciek pamięci bo nie jej nie zwalniasz.

Liczysz min zachłannie, a to nie wystarcza. Prosty przykład

100 20 120

Twój algorytm powie, że min to 80, a w rzeczywistości to 0.

Teraz algorytm dobrze oblicza wartość. Sposób krótszy niż pierwszy, ale dalej nie mam pomysłu na szybsze wyszukanie najmniejszej liczby.

 
#include <vector>
#include <iostream>
#include <cmath>

using namespace std;

vector <int> velocity;
vector <int> delta;


//------------------------------------------------------------
int rec(int n)
{
    if(n==0)
        return 0;

    else if(n==1)
        return 1;

    else
        return  rec(n-1)*2 + 1;
}


//------------------------------------------------------------
int dodaj(int n)
{
    int i, min = velocity[0];

    for(i = 1; i < n; i++)
    {
        for(int j = rec(i-1) ; j < rec(i); j++)
        {
            velocity.push_back( velocity[j] - delta[i] );
            velocity.push_back( velocity[j] + delta[i] );
        }
    }

    for(int j = 1; j < rec(i); j++)
        if( abs(min) > abs(velocity[j]) )
            min = abs( velocity[j] );

    cout<<min;
    min = 0;
}


//-----------------------------------------------------------
int main()
{
    int t, k, n, max = 0;
    cin >> t;

    for(int i = 0; i < t; i++)
    {
        cin >> n;

        for(int j = 0; j < n; j++)
        {
            cin >> k;
            delta.push_back( k );
            max += k;
        }

        velocity.push_back( delta[0] );
        dodaj(n);


        cout<<" "<<max<<endl;

        max = 0;
        velocity.clear();
        delta.clear();
    }

    return 0;
}

Przekraczasz czas nie dlatego, że źle używasz języka, ale dlatego, że masz algorytm o kosmicznej złożoności czasowej. To zadanie nie bez powodu znajduje się w kategorii "średnie" :-)

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int main() {
	vector<int> dane;
	int N, D, v1 = 0, nazwa, min_s, min,k,a;
	cin >> N;
	do {
		v1 = 0;
		dane.clear();
		cin >> D;
		for (int i = 0; i < D; i++) {
			cin >> nazwa;
			dane.push_back(nazwa);
			v1 += dane.at(i);
		}
		min = v1;
		for (int l = 0; l <= dane.size() - 1; l++) {
			dane.at(0) = dane.at(l);
			a = 1 << (dane.size() - 1);
			for (int i = 0; i <= pow(2, dane.size() - 1); i++) {
				k = a;
				min_s = dane.at(0);
				for (int c = 1; c < dane.size(); c++) {
					if (k % 2 == 0) {
						min_s -= dane.at(c);
					}
					else min_s += dane.at(c);
					k /=2;
				}
				if (min_s > -1 && min_s < min) min = min_s;
				++a;
			}
		}
		cout << min << " " << v1 << endl;
		--N;
	} while (N);
}

Ktoś coś? wyniki dobre, ale z czasem się nie wyrabia, może jakaś mini porada co można byłoby tu zmienić :D

Nie do końca rozumiem ideę twojego algorytmu. Poza tym liczba iteracji 2 ^ rozmiar danych budzi moje wątpliwości. Może zacznij od zastanowienia się, jakie dane otrzymujesz w każdym kroku iteracji, i czy wszystkie z nich są ważne?

Dobra rada. Spoj ma swoje forum i tam pytaj większa szansa że wyjadacze pomogą.