poniedziałek, 25 listopada 2013

17207. Konkatenacja liczb [AL_12_04]

Zadanie:
http://spoj.com/ALGOLIGA/problems/AL_12_04
http://pl.spoj.com/ALGOLIGA/problems/AL_12_04

Skrócony opis problemu:
Dla podanych n liczb znaleźć taką ich konkatenację, by jej wartość była największa.



Rozwiązanie nr 1:
Autorem tego rozwiązania jest Adam Bąk.
Pierwsza myśl to posortować te liczby leksykograficznie. Owe rozwiązanie nie jest jednak do końca poprawne, choć pomysł jest dobry. Np. dla liczb: 6, 64, 4 poprawna kolejność to: 6, 64, 4. Jednak dla liczb: 6, 69, 4 poprawna kolejność to: 69, 6, 4. Nie można zatem sortować leksykograficznie i brać wcześniej albo krótsze liczby, albo dłuższe. Przemyślmy więc dokładnie naszą funkcję porównującą. Na początku najłatwiejszy przypadek - 2 porównywane liczby są ten samej długości. W takiej sytuacji większa liczba idzie oczywiście wcześniej. Następnie rozpatrzmy sytuację, w której pierwsza liczba jest dłuższa od drugiej. Dla tej sytuacji sprawa również jest trywialna jeśli liczby różnią się prefiksem (czyli druga liczba nie rozpoczyna pierwszej, np. 1234 124). Zwracamy wtedy liczbę większą leksykograficznie. Został nam przypadek, gdy druga liczba jest prefiksem pierwszej (np. 69 6). Moglibyśmy porównać sufiks pierwszej liczby z drugą, jednak to nie zadziała z kolei dla przykładu: 553, 5, gdyż wzięlibyśmy 553 jako większą, podczas gdy prawidłowa sekwencja to: 5, 553. Możemy jednak wywołać naszą funkcję rekurencyjnie. Mamy 553, 5 i wywołujemy ją dla 53 oraz 5. Ją z kolei wywołujemy dla 3 oraz 5 i okazuje się, że 5 powinna iść wcześniej.
Złożoność: $O(n \log n)$ ze względu na sortowanie.

Algorytm:
bool cmp(const string &a, const string &b)
{
    int alen = a.length(), blen = b.length();
    if(alen == blen)
        return a > b;
    else if(alen < blen)
    {
        if(a == b.substr(0,alen))
            return cmp(a, b.substr(alen));
        else
            return a > b.substr(0,alen);
    }
    else if(alen > blen)
    {
        if(a.substr(0,blen) == b)
            return cmp(a.substr(blen), b);
        else
            return a.substr(0,blen) > b;
    }
    return 1;
}

Rozwiązanie nr 2:
Możemy ułatwić sobie naszą funkcję z pewnym spostrzeżeniem. Chcemy de facto by nasza funkcja dla dwóch stringów zwracała nam ich większą konkatenację. Nic nie szkodzi zatem na przeszkodzie by porównywać nie same stringi lecz ich konkatenacje i wybierać większą. Pozbywamy się dzięki temu wszystkich warunków, w których mogliśmy popełnić błąd.
Złożoność: $O(n \log n)$ ze względu na sortowanie.

Algorytm:
bool cmp(const string &a, const string &b)
{
    return a+b > b+a;
}

Rozwiązanie nr 3:
Autorem tego rozwiązania jest Artur Grochowski.
Możemy również uzupełnić obie porównywane liczby tak, by ich długości były odpowiednio duże konkatenując je wielokrotnie. Np. liczbę 1234 powtórzymy 3 razy: 12341234123, by miała więcej niż 10 znaków (gdyż liczby z wejścia mają maksymalnie 10 znaków). Robimy tak ze wszystkimi liczbami, a potem je po prostu porównujemy.
Złożoność: $O(n \log n)$ ze względu na sortowanie.

Algorytm:
bool comp(const string &a, const string &b)
{
    int len = a.length(), len2 = b.length();
    if(len == len2)
        return a > b;
    string x = a, y = b;
    int len3 = len;
    while(len3 < 11)
        x += a,
        len3 += len;
    len3 = len2;
    while(len3 < 11)
        y += b,
        len3 += len2;
    return x > y;
}

Zoptymalizowana wersja:
Nie musimy konkatenować liczb aż do osiągnięcia przynajmniej 11 znaków. Dla małych liczb jest to bowiem niewydajne. Wystarczy skonkatenować mniejszą liczbę tak, by była dłuższa niż większa, a większą dodatkowo raz skonkatenować, by można było porównać jej prefiks (początek) z środkiem mniejszej.
bool comp(const string &a, const string &b)
{
    int len = a.length(), len2 = b.length();
    if(len == len2)
        return a > b;
    else if(len < len2)
    {
        string a2 = a;
        int len3 = len;
        while(len3 < len2+2)
            a2 += a,
            len3 += len;
        return a2 > b+b;
    }
    string b2 = b;
    int len3 = len2;
    while(len3 < len+2)
        b2 += b,
        len3 += len2;
    return a+a > b2;
}

Brak komentarzy:

Prześlij komentarz