Pomoc w zrozumieniu treści zadania z OI XVIII

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?

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.

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.

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