• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zadanie smakołyki - c++ - ilość różnoelementowych niezerowych podciągów w danym ciągu.

VPS Starter Arubacloud
0 głosów
713 wizyt
pytanie zadane 27 stycznia 2017 w C i C++ przez Bartimaeus Nowicjusz (150 p.)
otagowane ponownie 27 stycznia 2017 przez Bartimaeus

Witam.

Mam problem z podlinkowanym zadaniem - Smakołyki .

Od kilku dni usiłuję go zrobić na różne sposoby, ale za każdym razem wysyłając program do sprawdzenie na testach dostaję komunikat o błędach. Co najgorsze moje rozwiązania działają na małych ciągach, ale na takich liczących już kilkadziesiąt tysięcy już nie więc trudno mi sprawdzić co powoduje niewłaściwe działanie programu.

#include <iostream>

using namespace std;
long long triangular_number(int n);

int main(){
    int n,m;
    cin>>n>>m;
    int tab[n];
    for(int i=0; i<n; ++i){
        cin>>tab[i];
    }
    if(m==1) cout<<n;
    else{
        int i=0;
        int j=1;
        while(i+1<n && tab[i]==tab[i+1]){
            ++i;
        }
        j=i+1;
        int kind[m+1];
        fill(kind,kind+m+1,1);
        --kind[tab[i]];
        --kind[tab[j]];
        bool p=false;
        int oldj=0;
        long long s=n;
        while(j+1<n && i<n){
            while(j+1<n && kind[tab[j+1]]){
                ++j;
                kind[tab[j]]=0;
            }
            if(p)
                s+=j-i+(j>oldj ? triangular_number(j-oldj) : 0);
            else
                s+=triangular_number(j-i+1);
            if(j+1<n){
                if(tab[j]==tab[j+1]){
                    ++j;
                    i=j;
                    for(int p=0; p<i; ++p)
                        kind[tab[p]]=1;
                    kind[tab[j]]=0;
                    p=false;
                }
                else{
                    while(i<n && !kind[tab[j+1]]){
                        kind[tab[i]]=1;
                        ++i;
                    }
                    kind[tab[i]]=0;
                }
                if(i>=j){
                    j=i;
                    p=false;
                }
                else{
                    p=true;
                    oldj=j+1;
                }
            }
        }
        cout<<s;
    }
    return 0;
}

long long triangular_number(int n){
    return (static_cast<long long>(n)*(n-1))/2;
}

Wyżej jedno z moich rozwiązań - funkcja triangular_number() wylicza liczbę możliwości w zależności od długości podciągu nie zliczając jednocześnie podciągów jednoelementowych - są to tak zwane liczby trójkątne, stąd więc nazwa. W tabeli kind[] przechowywane są liczby aktualnie rozpatrywanego ciągu 0 oznacza że liczba już wystąpiła więc kolejne wystąpienie kończy ciąg, a 1 odwrotnie.

Pewną trudnością jest cofanie się, ponieważ gdy na przykład w ciągu 1 2 3 4 5 1 6 7 8 zaczniemy od liczby 1 i skończymy na 5, to potem musimy rozpatrzyć także ciąg zaczynający się od 2 i kończący na 8 jednocześnie uważając żeby nie zliczyć drugi raz możliwości od 2 do 5. 

Nie do końca  wiem jak rozwiązać to w prostszy sposób unikając tego zamieszania z cofaniem i odejmowaniem. Zresztą zamieszczony kod nie działa w odpowiedni sposób - dla większych ciągów odpowiedzi są nieprawidłowe.

Proszę o pomoc.

 

1 odpowiedź

+1 głos
odpowiedź 28 stycznia 2017 przez vector Dyskutant (9,200 p.)
wybrane 28 stycznia 2017 przez Bartimaeus
 
Najlepsza

Można elegancko rozwiązać to zadanie za pomocą programowania dynamicznego. Oznaczmy sobie przez R(n) wynik dla ciągu (a(1), a(2), ..., a(n)). Rozważmy jak wyliczyć R(n) w zależności od R(n-1).

Skoro mamy wynik dla ciągu o jeden krótszego wystarczy tylko zaktualizować nasz wynik o liczbę możliwości wybrania smakołyków przy użyciu elementu a(n). Aby to zrobić wystarczy znaleźć najmniejszą możliwą liczbe x(n) należącą do {1, 2, ..., n} taką że dla każdy i, j różnych od siebie należących do {x(n), x(n)+1, ..., n} takich że a(i) != a(j). Zauważmy że wszystkie możliwości wybrania smakołyków zawierających a(n) to {a(n)}, {a(n), a(n-1)}, ..., {a(n), a(n-1), ..., a(x(n))}. Liczba tych wyborów jest równa n-x+1. Stąd otrzymujemy równość R(n) = R(n-1) + n-x(n)+1. W przypadku gdy n=1 oczywisty jest fakt R(1) = 1.

Jest możliwe zaimplementowanie tego rozwiązania w czasie O(n) i pamięci O(n). Zostawiam to jako ćwiczenie.

komentarz 28 stycznia 2017 przez Bartimaeus Nowicjusz (150 p.)
Rozwiązałem już to zadanie, ale w czasie O(n^2), więc pozostawiam twoją wypowiedź jako najlepszą. Dodam tylko że problemem był algorytm, nie program.
komentarz 28 czerwca 2018 przez koniak20 Początkujący (390 p.)

@vector,  a jak znaleźć to najmniejsze x(n) spełniające te warunki?

 

Podobne pytania

+2 głosów
1 odpowiedź 454 wizyt
pytanie zadane 7 sierpnia 2019 w Algorytmy przez piotrsz109 Stary wyjadacz (13,730 p.)
+1 głos
2 odpowiedzi 872 wizyt
pytanie zadane 22 kwietnia 2017 w Matematyka, fizyka, logika przez niezalogowany
0 głosów
1 odpowiedź 649 wizyt

92,451 zapytań

141,261 odpowiedzi

319,073 komentarzy

61,853 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...