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

0

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łędnych odpowiedziach. 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

To jest jedno z tych zadań, gdzie jednym z wąskich gardeł są operacje io.
Napisałeś, że masz komunikat o błędach. JAKI? Zapewne ten błąd to stack overflow, bo na stosie tworzysz ogromne tablice przekraczając jego pojemność.
Skorzystaj wiec z vectora. Dynamiczny rozmiar tablic na stosie jest rozszerzeniem gcc niezgodnym ze standardem.
Dlatego popraw to tak:

#include <iostream>
#include <vector>

using namespace std;

unsigned long long int CountSeriesWithUniqueItems(const vector<int>& candies, int m)
{
	unsigned long long int result = 0;

	… … …

	return result;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> n >> m;
	vector<int> candies;
	candies.reserve(n);
	for (int i=0; i<n; ++i)
	{
		int c;
		cin >> c;
		candies.push_back(c-1);
	}

	cout << CountSeriesWithUniqueItems(candies, m) << endl;

	return 0;
}
1

Już rozwiązałem problem.
Oto kod rozwiązania:

#include <iostream>
#include <cstring>

using namespace std;
#include "treats.h"

void treats(){
    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 kind[m+1];
        memset(kind, -1, sizeof kind);
        long long s=n;
        int j;
        int i=0;
        int remember=0;
        int remember2=0;
        while(i+1<n){
            kind[tab[i]]=i;
            j=1;
            while(i+1<n && kind[tab[i+1]]==-1){
                ++i;
                kind[tab[i]]=i;
                ++j;
            }
            if(remember)
                s+=triangular_number(j)-triangular_number(remember2-remember+1);
            else
                s+=triangular_number(j);
            int k=i+1;
            if(k<n && tab[i]==tab[k]){
                i=k;
                memset(kind, -1, sizeof kind);
                kind[tab[i]]=i;
                remember=0;
            }
            else if(k<n && j>1){
                remember=kind[tab[k]]+1;
                remember2=i;
                i=remember;
                memset(kind, -1, sizeof kind);
                kind[tab[i]]=i;
            }
            else
                remember=0;
        }
        cout<<s;
    }
}

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

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