Problem z zadaniem algorytmicznym (OI)

0

Cześć,
Przygotowuję się do Olimpiady Informatycznej Licealistów. Obecnie próbuję rozwiązać to zadanie: https://oi.edu.pl/pl/archive/oi/14/tet
Mój pomysł na algorytm (wiem, że nie jest optymalny, ale chcę sprawdzić, ile można za niego dostac pkt):

  1. Szukam w wieży pary kolorów, które leżą najbliżej siebie.
  2. Zbliżam tą parę do siebie, aż się spotka i 2 klocki znikną.
    I tak aż cała wieża zniknie. W międzyczasie sprawdzam też, czy na wieży nie zachodzi taka sytuacja:
    x
    y
    x
    y
    Wtedy od razu wykonuję dwa ruchy tak, żeby ustawić klocki w pozycji
    x
    x
    y
    y
    i usuwam wszystkie 4 na raz. Pomysł działa dla wszystkich zestawów danych, dla których zdołałem go sprawdzić (czyli raczej niewielkich - sprawdzenie rozwiązania długiego zestawu na kartce zajęłoby zbyt dużo czasu). Poblem polega na tym, że rozwiązanie w systemie przechodzi 5/7 testów wstępnych (1 raz przekroczony czas, 1 raz błąd o którym napiszę zaraz), natomiast spośród testów właściwych przechodzi tylko 1. 9 testów wyrzuca błąd "Strategia nie usuwa wszystkich elementów". Długo szukałem genezy problemu, ale nie potrafię znaleźć. Może ktoś rzuci okiem i sprawdzi, co może być nie tak?

Oto kod:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    vector<int> tower;
    queue<int> moves;
    int input;

    int movesCount = 0;

    for(int i = 0; i < 2 * n; ++i)
    {
        cin >> input;
        tower.push_back(input);
    }

    int aSwap = -1;
    int bSwap = -1;
    while(tower.size() > 0)
    {
        int indexOf[n];
        int distances[n];
        int smallestDist = 2147483647;
        for(int i = 0; i < n; ++i)
            indexOf[i] = -1;

        /*cout << "_________________________________\n";
        for(int i = 0; i < tower.size(); ++i)
        {
            cout << tower[i] << endl;
        }
        cout << "\n_________________________________\n";*/
        bool calcDists = true;

        for(int i = 0; i < tower.size(); ++i)
        {
            if(tower[i] == tower[i+1])
            {
                tower.erase(tower.begin() + i, tower.begin() + i + 2);
                calcDists = false;
                break;
            }

            if(i > 2)
            {
                if(tower[i] == tower[i-2] && tower[i-1] == tower[i-3])
                {
                    //cout << "tower[i] = " << tower[i] <<  ", tower.size() = " << tower.size() << endl;
                    //cout << "Ruch inwersji: " << tower.size() - i << endl;
                    moves.push(tower.size() - i);
                    //cout << "_____________________\nInwersja:\n" << tower[i-3] << "\n" << tower[i-2] << "\n" << tower[i-1] << "\n" << tower[i] << "\n______________________\n";
                    tower.erase(tower.begin() + i-3, tower.begin() + i + 1);
                    calcDists = false;
                    movesCount++;
                    break;
                }
            }

            if(indexOf[tower[i] - 1] == -1)
            {
                indexOf[tower[i] - 1] = i;
            }
            else
            {
                distances[tower[i] - 1] = i - indexOf[tower[i] - 1];
                if(distances[tower[i] - 1] < smallestDist)
                {
                    smallestDist = distances[tower[i] - 1];
                    aSwap = indexOf[tower[i] - 1];
                    bSwap = i;
                }
            }
        }

        if(!calcDists)
            continue;

        //cout << "Swap " << aSwap << " z " << bSwap << endl;

        int value = tower[aSwap];
        movesCount += (bSwap - aSwap - 1);
        for(int i = 0; i < (bSwap - aSwap - 1); ++i)
        {
            moves.push(tower.size() - (aSwap + 1 + i));
            //cout << "Ruch swapa " << tower.size() - (aSwap + 1 + i) << endl;
        }
        tower.erase(tower.begin() + aSwap, tower.begin() + aSwap + 1);
        tower.insert(tower.begin() + bSwap - 1, value);
        aSwap = bSwap = -1;
    }

    //cout << "\n\n_____WYNIK____________\n";
    cout << movesCount << "\n";
    while(!moves.empty())
    {
        cout << moves.front() << "\n";
        moves.pop();
    }
}

Mam książkę o konkursie ("25 lat Olimpiady Informatycznej") i w niej jest wzorcowe rozwiązanie, ale zależy mi na tym, żeby dowiedzieć się, co jest nie tak z tym kodem.

2 
        for(int i = 0; i < tower.size(); ++i)
        {
            if(tower[i] == tower[i+1])

To jest offbyone i w ogóle spowoduje że cały ten program nie będzie działał poprawnie. Dla ostaniego elementu wychodzisz poza tablicę i porównujesz z jakimiś losowymi danymi

  1. Ten cały krok z usuwaniem dwóch par na raz nie ma sensu. Niczego to nie przyspieszy specjalnie a tylko komplikuje ci kod.
0

Dziękuję, wprowadziłem poprawki. Nie wiem dlaczego przeoczyłem to wyjście poza indeks w pętli. Niestety wynik w systemie nie zmienił się. Te same testy wciąż pokazują "Strategia nie usuwa wszystkich elementów". Kod po poprawkach:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    vector<int> tower;
    queue<int> moves;
    int input;

    int movesCount = 0;

    for(int i = 0; i < 2 * n; ++i)
    {
        cin >> input;
        tower.push_back(input);
    }

    int aSwap = -1;
    int bSwap = -1;
    while(tower.size() > 0)
    {
        int indexOf[n];
        int distances[n];
        int smallestDist = 2147483647;
        for(int i = 0; i < n; ++i)
            indexOf[i] = -1;

        /*cout << "_________________________________\n";
        for(int i = 0; i < tower.size(); ++i)
        {
            cout << tower[i] << endl;
        }
        cout << "\n_________________________________\n";*/
        bool calcDists = true;

        indexOf[tower[0] - 1] = 0;

        for(int i = 1; i < tower.size(); ++i)
        {
            if(tower[i] == tower[i-1])
            {
                tower.erase(tower.begin() + (i-1), tower.begin() + i + 1);
                calcDists = false;
                break;
            }

            if(indexOf[tower[i] - 1] == -1)
            {
                indexOf[tower[i] - 1] = i;
            }
            else
            {
                distances[tower[i] - 1] = i - indexOf[tower[i] - 1];
                if(distances[tower[i] - 1] < smallestDist)
                {
                    smallestDist = distances[tower[i] - 1];
                    aSwap = indexOf[tower[i] - 1];
                    bSwap = i;
                }
            }
        }

        if(!calcDists)
            continue;

        //cout << "Swap " << aSwap << " z " << bSwap << endl;

        int value = tower[aSwap];
        movesCount += (bSwap - aSwap - 1);
        for(int i = 0; i < (bSwap - aSwap - 1); ++i)
        {
            moves.push(tower.size() - (aSwap + 1 + i));
            //cout << "Ruch swapa " << tower.size() - (aSwap + 1 + i) << endl;
        }
        tower.erase(tower.begin() + aSwap, tower.begin() + aSwap + 1);
        tower.insert(tower.begin() + bSwap - 1, value);
        aSwap = bSwap = -1;
    }

    //cout << "\n\n_____WYNIK____________\n";
    cout << movesCount << "\n";
    while(!moves.empty())
    {
        cout << moves.front() << "\n";
        moves.pop();
    }
}
0

Moja rada: napisz sobie "symulator" :) Taki który rysuje stan po tych twoich operacjach.

0

Symulator mam i wszystko działa jak należy. Przepisałem pseudokod rozwiązania wzorcowego na cpp i też pokazuje że źle. Skontaktuję się z OI, może to ich testy są błędne.

0

@licealista: moves.push(tower.size() - (aSwap + 1 + i)); - ta linijka wygląda podejrzanie. Dlaczego podajesz ruchy względem sczytu stosu?

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