Bajtocka Flaga - zadanko algorytmiczne

Question

Witajcie!

Rozwiązuję zadania z książki "Zaprzyjaźnij się z algorytmami" Jacka Tomasiewicza. Nie potrafię napisać wzorcówki do jednego z nich. W raporcie sprawdzania sprawdzarki pojawia się kilka komunikatów "Zła odpowiedź"

Zadanko "Bajtocka Flaga" z VIII Obozu Informatycznego ILOCAMP
Z książki "Zaprzyjaźnij się z algorytmami" pana Jacka Tomasiewicza
(strona 42.)

"Obecnie bajtocka flaga składa się z n różnokolorowych, poziomych pasów. Bajtocja zdecydowała się na zmianę flagi. Król chciałby, ale flaga składała się z n pasów w dwóch kolorach, A i B, ułożonych naprzemiennie. Wybór kolorów nie jest istotny dla króla. Istotne natomiast jest to, aby przemalowanie flagi było możliwie proste. Pomalowanie jest tym prostsze, im mniej pasów należy przemalować.

Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą n (2<=n<=500000) oznaczającą liczbę pasów flagi. W kolejnym wierszu wejścia jest n liczb całkowitych k0, k1, ..., kn-1, (1<=ki<=n), gdzie ki oznacza kolor i-tego pasa flagi.

Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą równą minimalnej liczbie pasów, które należy przemalować, aby flaga składała się tylko z dwóch kolorów i żadne sąsiednie pasy nie były tego samego koloru.

Przykład
Dla danych wejściowych:
6
1 2 3 1 4 2
Poprawną odpowiedzią jest:
3

Oto mój kod:

#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;

int main() {
    int n, k, zgodne{0};
    pair<int, int> a1{0, 0}, a2{0, 0}, b1{0, 0}, b2{0, 0};
    scanf("%d", &n);
    int ** kolory = new int * [2];
    kolory[0] = new int[n];
    kolory[1] = new int[n];
    for(int i=0; i<n; i++)
        kolory[0][i]=kolory[1][i]=0;
    for(int i=0; i<n; i++)
    {
        scanf("%d", &k);
        kolory[i%2][k-1]++;
    }
    for(int i=0; i<n; i++)
    {
        if(kolory[0][i]>=a1.first)
        {
            a2=a1;
            a1.first=kolory[0][i];
            a1.second=i;
        }
        if(kolory[1][i]>=b1.first)
        {
            b2=b1;
            b1.first=kolory[1][i];
            b1.second=i;
        }
    }
    if(a1.second!=b1.second)
        zgodne=max(zgodne, a1.first+b1.first);
    if(a2.second!=b1.second)
        zgodne=max(zgodne, a2.first+b1.first);
    if(a1.second!=b2.second)
        zgodne=max(zgodne, a1.first+b2.first);
    printf("%d", n-zgodne);
    delete [] kolory[0];
    delete [] kolory[1];
    delete [] kolory;
    return 0;
}

Rozwiązanie działa w czasie O(n). Najpierw zliczam występowanie każdego koloru na pozycjach parzystych i nieparzystych. Wybieram po dwa kolory, które występują maksymalną liczbę razy na pozycjach parzystych i nieparzystych. Następnie sprawdzam 3 kombinacje, wybierając optymalną o różnych kolorach.

Z góry dziękuję za pomoc w znalezieniu błędu

 

Contest na main'ie nazywa się "Zaprzyjaźnij się z algorytmami".

Comments

 if(a1.second!=b1.second)

        zgodne=max(zgodne, a1.first+b1.first);

    if(a2.second!=b1.second)

        zgodne=max(zgodne, a2.first+b1.first);

    if(a1.second!=b2.second)

        zgodne=max(zgodne, a1.first+b2.first);

Nie bardzo rozumiem co to robi? Nie wystarczy dodac i odjac sumy od wszystkich liczb>

---

Nie. Wtedy na fladze mógłby zostać tylko jeden kolor. Należy sprawdzać te 3 kombinacje

---

A racja

---

No to chyba zapomniales o porownaniu z suma a1 i a2

// edit co ja pisze xd

---

Czemu miałoby służyć takie porównanie? Nie rozumiem

---

Sam nie wiem o co mi chodzilo xd Gralem w lola i za bardzo nie myslalem sry.

---

 if(kolory[0][i]>a1.first)
        {
            a2=a1;
            a1.first=kolory[0][i];
            a1.second=i;
            
        }
         else if(kolory[0][i]>a2.first)
        {
            a2.first=kolory[0][i];
            a2.second=i;
        }
        if(kolory[1][i]>b1.first)
        {
            b2=b1;
            b1.first=kolory[1][i];
            b1.second=i;
            
        }
        else if(kolory[1][i]>b2.first)
        {
            b2.first=kolory[1][i];
            b2.second=i;
        }

 

---

Dzięki

Answer 1

Dzięki przespaniu się z problemem i dyskusji z użytkownikiem Sinoviesta, udało mi się znaleźć jeden z błędów w moim rozwiązaniu. Nie rozważałem przypadku, w którym liczba wystąpień nie jest większa od a1 lub b1, a jest większa od a2 lub b2. Tak wygląda kod po poprawkach:

#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;

int main() {
    int n, k, zgodne{0};
    pair<int, int> a1{0, 0}, a2{0, 0}, b1{0, 0}, b2{0, 0};
    scanf("%d", &n);
    int ** kolory = new int * [2];
    kolory[0] = new int[n];
    kolory[1] = new int[n];
    for(int i=0; i<n; i++)
        kolory[0][i]=kolory[1][i]=0;
    for(int i=0; i<n; i++)
    {
        scanf("%d", &k);
        kolory[i%2][k-1]++;
    }
    for(int i=0; i<n; i++)
    {
        if(kolory[0][i]>=a1.first)
        {
            a2=a1;
            a1.first=kolory[0][i];
            a1.second=i;
        }
        else if(kolory[0][i]>a2.first)
        {
            a2.first=kolory[0][i];
            a2.second=i;
        }
        if(kolory[1][i]>=b1.first)
        {
            b2=b1;
            b1.first=kolory[1][i];
            b1.second=i;
        }
        else if(kolory[1][i]>b2.first)
        {
            b2.first=kolory[1][i];
            b2.second=i;
        }
    }
    if(a1.second!=b1.second)
        zgodne=max(zgodne, a1.first+b1.first);
    if(a2.second!=b1.second)
        zgodne=max(zgodne, a2.first+b1.first);
    if(a1.second!=b2.second)
        zgodne=max(zgodne, a1.first+b2.first);
    printf("%d", n-zgodne);
    delete [] kolory[0];
    delete [] kolory[1];
    delete [] kolory;
    return 0;
}

Mój problem nie został jednak do końca rozwiązany, gdyż jeden z testów zwraca błędny wynik.

Proszę o pomoc w znalezieniu i zrozumieniu błędu.

Dziękuję za pomoc użytkownikowi Sinoviesta.

 

EDIT

Udało mi się znaleźć błąd. Możliwy jest przypadek, w którym maksymalną liczbę razy występują kolory 0. Możliwa jest również sytuacja, w której nie aktualizujemy wartości a2 lub b2. Z domyślną wartością koloru równą 0, program nie działa dla takich przypadków. Pomogła inicjalizacja zmiennych a1, a2, b1, b2 z wartością -1.

Oto działający kod:

#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;

int main() {
    int n, k, zgodne{0};
    pair<int, int> a1{-1, -1}, a2{-1, -1}, b1{-1, -1}, b2{-1, -1};
    scanf("%d", &n);
    int ** kolory = new int * [2];
    kolory[0] = new int[n];
    kolory[1] = new int[n];
    for(int i=0; i<n; i++)
        kolory[0][i]=kolory[1][i]=0;
    for(int i=0; i<n; i++)
    {
        scanf("%d", &k);
        kolory[i%2][k-1]++;
    }
    for(int i=0; i<n; i++)
    {
        if(kolory[0][i]>=a1.first)
        {
            a2=a1;
            a1.first=kolory[0][i];
            a1.second=i;
        }
        else if(kolory[0][i]>a2.first)
        {
            a2.first=kolory[0][i];
            a2.second=i;
        }
        if(kolory[1][i]>=b1.first)
        {
            b2=b1;
            b1.first=kolory[1][i];
            b1.second=i;
        }
        else if(kolory[1][i]>b2.first)
        {
            b2.first=kolory[1][i];
            b2.second=i;
        }
    }
    if(a1.second!=b1.second)
        zgodne=max(zgodne, a1.first+b1.first);
    if(a2.second!=b1.second)
        zgodne=max(zgodne, a2.first+b1.first);
    if(a1.second!=b2.second)
        zgodne=max(zgodne, a1.first+b2.first);
    printf("%d", n-zgodne);
    delete [] kolory[0];
    delete [] kolory[1];
    delete [] kolory;
    return 0;
}

Mam wzorcówke. Dziękuję za pomoc