Ilość podciągów różnowartościowych

Odpowiedz Nowy wątek
2018-12-31 14:06
0

Mam problem z tym zadaniem (wrzucam w załączniku, pochodzi z serwisu MAIN2), gdyż daje dobre odpowiedzi, niestety w niektórych testach przekracza minimalnie limity czasowe (w załączniku raport sprawdzania), sugeruje to, że rząd złożoności jest ok, wg mojego oszacowania to O(n^2), ale pewnie robię jakieś rzeczy niepotrzebnie, lub nie uwzględniam informacji o liczbie rodzajów smakołyków, co jest bardzo prawdopodobne, bo bez powodu jej nie podali. Algorytm to taka gąsienica, tylko nie do końca :D jeśli ciąg c[i] c[i+1] ... c[j] jest różnowartościowy to oczywiście ciągów zawierających c[j] jest j-i+1, więc o tyle zwiększamy licznik k, potem sprawdzamy indeks pierwszego wystąpienia c[j+1] w ciągu c[i] c[i+1] ... c[j+1], oczywiście poprzedni ciąg był różnowartościowy, więc w c[i]...c[j] może być co najwyżej jedno wystąpienie, jeśli otrzymamy j+1 oznacza to, że w ciągu c[i]...c[j] nie występuje c[j+1], więc do licznika dodajemy (j+1)-i+1, w przeciwnym razie dla wystąpienia p<j+1, wiemy że c[p+1] ... c[j+1] będzie różnowartościowym ciągiem i licznik zwiększamy o (j+1)-(p+1)+1, dalej będziemy rozpatrywać zakres p+1 do j+2, itd, aż dojdziemy do końca tablicy, mam nadzieje, że bardziej pomogłem w zrozumieniu mojego toku myślenia, niż przeszkodziłem :)

#include<stdio.h>

using namespace std;

int n,m;//n-ilość smakołyków m-ilość dostępnych rodzajów
int c[1000000];//rodzaje kolejnych smakołyków
void g_data(int &n1,int &m1,int tab[])//pobiera dane
{
    scanf("%i%i",&n1,&m1);
    for(int i=0;i<n1;i++)
    {
        scanf("%i",&tab[i]);
    }
}
int srch_f_same(int tab[],int p,int e)//dla tab[e] wyszukuje indeks pierwszego jego wystąpienia w zakresie tab[p]...tab[e]      
{
    int i=p;
    while(i<e+1)
    {
        if(tab[e]==tab[i])
            return i;
        i++;
    }
}
int ciag_max(int &n1,int &m1,int tab[])
{
    int i=0;//indeks początku zakresu
    int k=0;//licznik-odpowiedź na pytanie z zadania
    int i_p=0;
    for(int j=0;j<n1;j++)
    {
        i_p=srch_f_same(tab,i,j);
        if(i_p!=j)
            i=i_p+1;
        k+=(j-i+1);
    }
    return k;
}
int main()
{
    g_data(n,m,c);
    printf("%i",ciag_max(n,m,c));
    return 0;
}

Pozostało 580 znaków

2018-12-31 15:19

Z uzyciem dodatkowej struktury danych: set. Idea: dla n < 4 policzyc ręcznie, dla n > 3, policzyć ilośc podciągów dla trzech pierwszych wyrazów, dodać je do zbioru, a następnie: iterując od trzeciego, sprawdzać czy element jest równy aktualnemu, czy jest w zbiorze, itd..., te różne przypadki, dają odpowiednie "zinkrementowania n". Złożoność: O(n), pseudokod (Python):

def compute_3(xs):
    if xs[0] != xs[1] and xs[1] != xs[2] and xs[0] != xs[2]:
        return 6
    elif xs[0] == xs[1] and xs[1] != xs[2]: return 4
    elif xs[0] == xs[2] and xs[2] != xs[1]: return 4
    elif xs[1] == xs[2] and xs[2] != xs[0]: return 4
    else: return 3

def subseries(xs):
    limit = len(xs)

    # edge cases, n = 1, n = 2, n = 3
    if limit == 1: return 1
    if limit == 2:
        if xs[0] == xs[1]: return 2
        else: return 3
    if limit == 3:
        return compute_3(xs)

    # n > 3
    n = compute_3(xs) - 3
    s = set() # initialize set
    s.add(xs[0])
    s.add(xs[1])
    s.add(xs[2])
    for i in range(2, limit - 1): # i from 2 to limit - 1 (exclusive)
        if xs[i] != xs[i+1]:
            if xs[i + 1] in s:
                if xs[i + 1] == xs[i - 1] or xs[i] == xs[i - 1]:
                    n += 1
                else: 
                    n += 2
            else:
                n += 3
            s.add(xs[i + 1])    
    return n + limit

print(subseries([1, 3, 2, 2, 3])) # -> 9
print(subseries([1, 2, 3, 4])) # -> 10 (the all subseries)
print(subseries([1, 2, 2, 2, 2])) # -> 6

edytowany 1x, ostatnio: lion137, 2018-12-31 15:20
Dzięki ziomek! :) - pawel1216 2019-01-01 14:57
Teraz to nawet przypomina gąsienice (taką krótką, jeszcze nastolatkę) :D - pawel1216 2019-01-01 15:10

Pozostało 580 znaków

2019-01-02 03:26
1

Twoje limitu nie są przekroczone tylko troszkę, po prostu chwilę po przekroczeniu czasu Twój program jest zabijany. Skoro n < 1000000, to znaczy że oczekiwane złożoność to n*log(n).

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0