Tasma - MAIN2

Question

Znowu mam delikatny problem z zadankiem z MAIN2 (mowa o tym: https://main2.edu.pl/c/konkurs-wstepu-do-programowania/p/tas/ )

Samo zadanie ,,zrobiłem" to znaczy działa bez zarzutów ale algorytm jest niewydajny ( przekracza mi maksymalnie o trzy setne sekundy, no ale przekracza :D ).

Tutaj mój kod:
 

#include <iostream>

int main()
{
    int n;
    std::cin>>n;
    long int a[n];
    std::cin>>a[0];
    bool prawda=true,koniec=false;
    for(int i=1; i<n; i++)
    {
        std::cin>>a[i];
        if(a[i-1]!=a[i])
            prawda=false;
    }
    if(prawda)
        std::cout<<"BRAK";
    else
    {
        long  int wynik=0,odleglosc=0;
        for(int i=0; i<n-1 && wynik<n-i; i++)
        {
            for(int j=n-1; j>i && !koniec; j--)
            {

                if(a[i] != a[j])
                {
                    odleglosc=j-i;
                    koniec=true;
                }
            }
            koniec=false;
            if (wynik<odleglosc)
                wynik=odleglosc;

        }
        std::cout<<wynik;
    }

}

 

Answer 1

long int a[n];

To nie powinno zadziałać. Używaj dynamicznej alokacji, gdy chcesz zaalokować tablicę o rozmiarze nieznanym w czasie kompilacji.
 

for(int i=0; i<n-1 && wynik<n-i; i++)

Tutaj pierwszy warunek jest chyba zbędny i < n - wynik go pokrywa.

for(int j=n-1; j>i && !koniec; j--)

Zamiast flagi koniec używałbym break, może to minimalnie przyspieszyć program, a na pewno będzie on czytelniejszy. I to j>i. Ja bym dał  j - i > wynik. Czyli dopóki dalsze poszukiwania mogą coś zmienić. Możliwe, że wyjdzie na to samo, bo nie mogę wymyślić przypadku, ale jest bardziej logiczne.

Generalnie w tym rozwiązaniu nie musisz też porównywać czy wynik < odległość bo algorytm jest tak napisany, że wynik nigdy nie spadnie.

A co do optymalizacji to napisałem to sam i też mi wychodzi i to nawet 4 ms ponad czas, więc co do algorytmu ciężko mi coś dodać. Sprawdziłem jedynie, że w testowanych przypadkach wykonuje minimum porównań. A to sugeruje, że trzeba poszukać gdzieś indziej tych 3 ms. Obstawiałbym, że wczytywanie przy pomocy cina nie jest optymalne. Spróbuje poeksperymentować i dam znać czy coś się udało.

Moje rozwiązanie:

#include <iostream>
using namespace std;

unsigned longestNotEqualDistance(unsigned array[], const unsigned length) {
	unsigned longest = 0;
	for (size_t i = 0; i < length - longest; i++)
	{
		for (size_t j = length - 1;j-i>longest ; j--)
		{
			if (array[i] != array[j]) {
				longest = j-i;
				break;
			}
		}
	}
	return longest;
}

int main() {
	int N;
	cin >> N;
	unsigned * array = new unsigned[N];
	bool areDifferent = false;
	cin >> array[0];
	for (size_t i = 1; i < N; i++)
	{
		cin >> array[i];
		if (array[i] != array[i - 1])
			areDifferent = true;
	}
	if (areDifferent) {
		cout << longestNotEqualDistance(array, N);
	}
	else
		cout << "BRAK" << endl;
	delete[] array;
}

 

Comments

Kombinowałem coś z wczytywaniem całego inputu na raz, ale nic to nie dało. Podobnie przepisanie całości na czyste C.

---

Podbijam pytanie bo sam nie wiem jak to ulepszyć