Pomoc w zrozumieniu treści zadania z OI XVIII

0

Nie bardzo rozumiem o co chodzi w zadaniu 'Rotacje na drzewie' z zeszłorocznej OI: [url]http://main.edu.pl/pl/archive/oi/18/rot[/url]
Próbowałem liczyć na różne sposoby i zawsze wychodzi inny wynik niż powinien. Czym w końcu są te inwersję? Z treści wynika, że jedna inwersja to para pozycji w koronie, na których liczba z lewej jest większa od tej z prawej. Ułożyłem do tego algorytm i wychodzą liczby parę razy większe niż w odp. Nawet ręcznie licząc można do tego dojść. Co źle rozumiem?

0

W zadaniu chodzi o utworzenie możliwie najlepszego drzewa za pomocą zadaniowych rotacji i określenie liczby inwersji.
W przykładzie mamy np. ((3, 1), 2), które ma dwie inwersje: 3>1, 3>2. Najlepsze drzewo (być może jedno z najlepszych) to drzewo ((1, 3), 2), które zawiera już tylko jedną inwersję, tj. 3>2.

0

OK, rozumiem. Myślałem, że rotacje można wykonywać tylko na rozgałęzieniach zakończonych liśćmi. Teraz jest znacznie trudniej. Może mi ktoś podsunąć jakiś pomysł? Można by próbować układać wszystko po kolei, ale to będzie bardzo czasochłonne.

0

Oto co udało mi się zrobić. Miałem nadzieję, że zadziała, ale niestety :/

#include <stdio.h>

unsigned n, p, inversions;
unsigned values[200000], ptr;

// Struktura drzewa //
struct STree {
    unsigned value, count, sum;
    STree *left;
    STree *right;
    STree() : value(0), count(0), sum(0), left(NULL), right(NULL) {}
} *root; // pierwszy element (korzeń

// DEKLARACJE FUNKCJI //
bool IsBigger(STree *whare, unsigned what);
void SwapPlaces(STree *what);
void FillTable(STree *point);

// Funkcja pobierająca dane do drzewa //
unsigned FillTree(STree *current) {
    scanf("%d", &p);
    if(p == 0) {
        current->left = new STree;
        current->right = new STree;
        current->sum = FillTree(current->left) + FillTree(current->right);
        current->count = current->left->count + current->right->count;
        if(current->left->sum / current->left->count > current->right->sum / current->right->count) 
            SwapPlaces(current);
        return current->sum;
    } else {
        current->value = p;
        current->sum = p;
        current->count = 1;
        return p;
    }
}

// Funkcja zliczająca inwersje //
void Inversions() {
    FillTable(root);
    for(unsigned i = 0; i < n; i++) {
        for(unsigned j = i; j < n; j++) {
            if(values[i] > values[j]) inversions++;
        }
    }
}

// MAIN //
int main() {
    root = new STree;
    scanf("%d", &n);
    FillTree(root);
    Inversions();
    printf("%d", inversions);
    return 0;
}

// Funkcja sprawdzająca czy w danym węźle znjaduje się liczba większa od podanej //
bool IsBigger(STree *where, unsigned what) {
    if(where->left->value == 0) {
        if(IsBigger(where->left, what)) return true;
    } else if(where->left->value > what) return true;
    if(where->right->value == 0) {
        if(IsBigger(where->right, what)) return true;
    } else if(where->right->value > what) return true;
    return false;
}

// Funkcja zamieniająca miejscami dzieci węzłą //
void SwapPlaces(STree *what) {
    STree *Tmp = what->left;
    what->left = what->right;
    what->right = Tmp;
}

// Funkcja spisująca koronę drzewa do tablicy - od lewej //
void FillTable(STree *point) {
    if(point->left->value == 0)
        FillTable(point->left);
    else {
        values[ptr] = point->left->value;
        ptr++;
    }
    if(point->right->value == 0)
        FillTable(point->right);
    else {
        values[ptr] = point->right->value;
        ptr++;
    }
}

Nie potrafię wymyślić dobrego algorytmu. Ten w kodzie polega na rotacjach liczby(po kolei od 1 do n) tak, żeby znajdowała się ona przed większymi od niej. Niestety tak nie rozwiązuje nawet przykładowego zadania.

EDIT: Pomyliłem się, zadanie z przykładu oraz 6 innych z testów rozwiązuje. Teraz będę debugować na podstawie drugiego testu, może gdzieś wkradł się drobny błąd. Ale i tak przy połowie wywłaszcza :/

EDIT 2:
Zaktualizował kod i teraz przechodzi 14 testów, ale nie mam pojęcia jaki powinien być prawidłowy algorytm

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