Płytkie nawiasowania

Na XXX Olimpiadzie Informatycznej zawodnicy mierzyli się z zadaniem “Płytkie nawiasowanie”. Pełną treść zadania można znaleźć na oficjalnej stronie Olimpiady. Opiszę tu pokrótce o co w zadaniu chodziło, ale zanim to nastąpi to wytłumaczę czym jest poprawne nawiasowanie. Poprawne nawiasowanie to taki napis złożony z symboli ( oraz ) w którym każdy nawias otwierający ma swój nawias zamykający i odwrotnie. Dla przykładu: (())() jest poprawnym nawiasowaniem, ale ()) już nie (po bardziej formalną definicję poprawnego nawiasowania, odsyłam do treści zadania). Poniższa funkcja sprawdza czy dane nawiasowanie jest poprawne:

bool poprawne_nawiasowanie(string nawiasowanie)
{
    int glebokosc = 0;

    for (char nawias: nawiasowanie)
    {
        if (nawias == '(')
            glebokosc++;
        else
            glebokosc--;

        if (glebokosc < 0)
            return false;
    }

    return (glebokosc == 0);
}

W zmiennej głębokość zapamiętujemy różnicę między otwierającymi nawiasami a zamykającymi nawiasami. Aby nawiasowanie było poprawne, muszą zachodzić następujące warunki:

• Podczas działania algorytmu, głębokość musi być zawsze nieujemna
• Po zakończeniu algorytmu, głębokość musi być równa zeru

Jeśli te dwa warunki są spełnione, to funkcja poprawne_nawiasowanie zwraca true. W przeciwnym przypadku zwraca false.

W zadaniu płytkie nawiasowania mieliśmy dane poprawne nawiasowanie oraz wartość H. Należało obliczyć jaka jest najmniejsza liczba nawiasów, które trzeba zamienić w tym nawiasowaniu, aby otrzymać poprawne nawiasowanie w którym głębokość nigdy nie przekracza wartości H. Takie nawiasowanie nazywamy płytkim.

Bardzo prosto jest zmodyfikować nasz algorytm tak, aby sprawdzał czy nawiasowanie jest płytkie:

bool plytkie_nawiasowanie(string nawiasowanie, int H)
{
    int glebokosc = 0;

    for (char nawias: nawiasowanie)
    {
        if (nawias == '(')
            glebokosc++;
        else
            glebokosc--;

        if (glebokosc < 0 or glebokosc > H)
            return false;
    }

    return (glebokosc == 0);
}

Okazuje się, że zadanie można rozwiązać w następujący sposób. Przechodzimy przez nawiasowanie i zamieniamy wszystkie nawiasy, które psują głębokość: jeśli napotkamy na nawias otwierający, który spowodowałby, że głębokość byłaby większa od H, to zamieniamy go na nawias zamykający. Jeśli z kolei napotkamy na nawias zamykający, który spowodowałby, że głębokość byłaby ujemna, to zamieniamy go na nawias otwierający. Tą ideę implementuje poniższy kod:

    int glebokosc = 0;
    int liczba_zmian = 0;

    for (int i = 0; i < n; i++)
    {
        if (nawiasowanie[i] == '(' and glebokosc == H)
        {
            nawiasowanie[i] = ')';
            liczba_zmian++;
        }
        else if (nawiasowanie[i] == ')' and glebokosc == 0)
        {
            nawiasowanie[i] = '(';
            liczba_zmian++;
        }

        if (nawiasowanie[i] == '(')
            glebokosc++;
        else
            glebokosc--;
    }

Kod ten również znajduje to płytkie nawiasowanie, chociaż zadanie tego nie wymagało.

Pełny kod rozwiązania można znaleźć na moim githubie.