OI - rozwiązania

Z racji, że OI się już skończyło to można by się już podzielić swoimi rozwiązaniami :) (nikt już pocztą też raczej nie wyśle, chyba, że ma lewe układy z Panią Z Okienka i mu wbije wczorajszą datę :P Może ja się pochwalę jedynym, na które miałem pomysł (zrobione w 2 dni bo miałem kompa w serwisie [sic!] i na więcej nie starczyło czasu), a mianowicie Litery:

/**
 * @file lit.cpp
 *
 *     @date   12-11-2011
 *     @author Łukasz Niemier
 */

#include <cstdio>
#include <list>
#include <vector>

#define ord(c) ((c) - 'A')

const unsigned int DICT_SIZE = 'Z' - 'A' + 1;
const unsigned int MAX_SIZE = 1000002;

char jas[MAX_SIZE];
char malgosia[MAX_SIZE];
unsigned int strLen, i;
unsigned long long int swaps;
std::list<int> Q[DICT_SIZE];
std::vector<int> positions;

void gen_positions() {
	for (i = 0; i < strLen; i++)
		Q[ord(malgosia[i])].push_back(i);
	for (i = 0; i < strLen; i++) {
		positions[i] = Q[ord(jas[i])].front();
		Q[ord(jas[i])].pop_front();
	}
}

int merge(std::vector<int>& arr, std::vector<int>& temp, int left, int mid,
		int right) {
	int i, j, k;

	i = left; //< left subarray index
	j = mid;  //< right subarray index
	k = left; //< merged subarray index
	while ((i <= mid - 1) && (j <= right)) {
		if (arr[i] <= arr[j]) {
			temp[k++] = arr[i++];
		} else {
			temp[k++] = arr[j++];
			swaps = swaps + (mid - i);
		}
	}
	while (i <= mid - 1)
		temp[k++] = arr[i++];

	while (j <= right)
		temp[k++] = arr[j++];

	for (i = left; i <= right; i++)
		arr[i] = temp[i];

	return swaps;
}

int merge_sort(std::vector<int>& arr, std::vector<int>& temp, int left,
		int right) {
	int mid;
	if (right > left) {
		mid = (right + left) / 2; //< divide array to two parts

		merge_sort(arr, temp, left, mid);
		merge_sort(arr, temp, mid + 1, right);

		merge(arr, temp, left, mid + 1, right);
	}
	return swaps;
}

int inv_count(std::vector<int>& arr) {
	std::vector<int> temp(arr.size());
	return merge_sort(arr, temp, 0, arr.size() - 1);
}

int main(int argc, char **argv) {
	scanf("%u", &strLen);
	scanf("%s", jas);
	scanf("%s", malgosia);
	positions.resize(strLen);

	gen_positions();
	inv_count(positions);

	printf("%llu", swaps);

	return 0;
}

Zrobione częściowo na wektorach bo z nimi było mniej babrania się.

Ja zrobiłem raczej wzorcówkę do Liter, bruta do Randki i bruta do Odległości. Myślę, że starczy żeby przejść. Mam jeszcze 3 lata na starty w OIu także w następnych latach będzie lepiej. Mój kod do Liter:

//Autor: Piotr Nosek

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int n;
queue <int> literki[26];
int gdzie[1000009];
long long load[1000009];

void add(int x, int v = 0)
{
    while(x <= n)
    {
        load[x]+=v;
        x += x & (-x);
    }
}

int query(int x)
{
    int res = 0;
    while(x > 0)
    {
        res += load[x];
        x -= x & (-x);
    }
    return res;
}

int main()
{
    ios_base::sync_with_stdio(0);
    string jas, gosia;
    cin >> n;
    cin >> jas >> gosia;
    for(int i=0; i<n; i++)
        literki[static_cast<int>(jas[i] - 'A')].push(i+1);
    for(int i=1; i<=n; i++)
    {
        int pom = literki[static_cast<int>(gosia[i-1] - 'A')].front();
        literki[static_cast<int>(gosia[i-1] - 'A')].pop();
        gdzie[pom] = i;
    }
    unsigned long long wynik = 0;
    for(int i=1; i<=n; i++)
        add(gdzie[i]);
    for(int i=1; i<=n; i++)
    {
        long long tmp = query(gdzie[i]);
        add(gdzie[i], 1);
        wynik+=gdzie[i] - 1 - tmp;
    }
    cout << wynik;
    return 0;
}

Myślę, że to dużo prostsze rozwiązanie niż twoje. Jakby ktoś chciał mogę wrzucić moje bruty do Randki i Odległości, ale brut do Randki ma ponad 200 linii, także nie chce tu spamować forum.

@Edit
Zarys mojego rozwiązania:
Kod działa na drzewach potęgowych. Idea polega na tym, że łączę w 'pary' każdą literkę z drugiego stringa(Gosi) z pierwszym(Jasia). W ten sposób np. dla testu
3 ABC BCA
Numeruję sobie kolejne literki w pierwszym stringu od jedynki do n. Każdą literę w drugim stringu łączę z pierwszą woloną w pierwszym stringu (mam to na jakiejś kolejce). Powstają mi dwa ciągi:
123 231.
Teraz lecę po drugim stringu, ale w takiej kolejności jakbym je posortował, czyli najpierw 1 potem 2 potem 3. Czyli najpierw będę w elemecie nr 3, bo tam jest 1, potem w elemencie nr 1 bo tam jest 2 itd. No i teraz lecąc tak zliczam sobie ile już wcześniej 'odwiedziłem' liter na lewo, czyli ile jest od tego elementu mniejszych elementów na lewo. Jak odwiedzam dany element to sobie takie coś odnotowuję i wrzucam na drzewko potęgowe, a takie drzewo w czasie log n zwraca mi sumę elementów z danego przedziału.
Co do sum bitowych - szczerze to nie mam pojecia jak to działa, ale znajduje to największą potęgę dwójki dzielącą x. Jest to związane z zapisem w pamięci komputera liczb ujemnych, zasłyszałem o tym i używam.
@edit2
A to może walnę tu krótki opis rozwiązania brute-force do Odległości. Złożoność: O(n^2 + max), albo jakoś tak, gdzie max - największa liczba w ciągu (max. 1 000 000).
Moje rozwiązanie polegało na wygenerowaniu liczb pierwszych do maxa z liczb na wejściu i rozłożeniu każdej liczby na wejściu na czynniki pierwsze. Potem porównywałem ile co najmniej operacji trzeba wykonać by z jednej liczby zrobić drugą, czyli tak na prawdę sprawdzić jaka jest różnica ilości poszczególnych liczb pierwszych w rozkładzie na czynniki pierwsze. Potem szukałem minimalnej odległości. Kod:

//Autor: Piotr Nosek
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int tab[1007];
int najw[1007];
int numTab[1000007];
vector<int> roz[1007];
int n, maxx;
vector <int> pierwsze;

int abs(int a) {return a > 0 ? a : -a;}

void sito()
{
    for(int i=2; i*i<=maxx; i++)
    {
        if(numTab[i])
            continue;
        for(int j=2*i; j<=maxx; j+=i)
            numTab[j] = 1;
    }
    for(int i=2; i<=maxx; i++)
        if(!numTab[i])
            pierwsze.push_back(i);
}

int odl(int a, int b)
{
    int wynik = 0;
    if(tab[a] == 1)
    {
        for(int i=2; i<=najw[tab[b]]; i++)
            wynik+=roz[b][i];
        return wynik;
    }
    if(tab[b] == 1)
    {
        for(int i=2; i<=najw[tab[a]]; i++)
            wynik+=roz[a][i];
        return wynik;
    }
    for(int i=2; i<=max(najw[tab[a]], najw[tab[b]]); i++)
    {
       wynik+=abs(roz[a][i] - roz[b][i]);
    }
    return wynik;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i=0; i<n; i++)
        cin >> tab[i];
    int *tmp = max_element(tab, tab+n);
    maxx = tab[tmp - tab];
    sito();
    for(int i=0; i<n; i++)
        for(int j=0; j<maxx; j++)
            roz[i].push_back(0);
    for(int i=0; i<n; i++)
    {
        int liczba = tab[i], j = 0;
        while(liczba > 1)
        {
            if(liczba % pierwsze[j] == 0)
            {
                roz[i][pierwsze[j]]++;
                liczba /=pierwsze[j];
                najw[tab[i]] = pierwsze[j];
            }
            else j++;
        }
    }
    for(int i=0; i<n; i++)
    {
        int maks = 1000000, ix = 0;
        for(int j=0; j<n; j++)
        {
            if(j == i)
                continue;
            int danaOdl = odl(i, j);
            if(danaOdl < maks)
            {
                maks = danaOdl;
                ix = j;
            }
        }
        cout << ix+1 << "\n";
    }
    return 0;
}

Litery, działa niby dla dowolnych znaków, ale nie jest dobrze przetestowane.

#include <stdio.h>

int d[2123456], h[256], n[1123456];
char a[1123456], b[1123456];

int main(int argc, char** argv) {
    int z, i = scanf("%d %s %s", &z, a, b);
    long long int t = 0;
    for (i = z - 1; i >= 0; i--) {
        d[i * 2] = d[i * 2 + 1] = 0;
        n[i] = h[a[i]];
        h[a[i]] = i;
    }
    for (i = 0; i < z; i++) {
        int j, r = 0, p = h[b[i]];
        h[b[i]] = n[p];
        t += p;
        for (j = 0; (z >> j); j++) {
            t -= (p % 2) * (d[r + p / 2] += 1 - p % 2);
            r += (z + (2 << j) - 1) >> (j + 1);
            p /= 2;
        }
    }
    printf("%lld\n", t);
    return 0;
}

To jest oczywiście przykład jak nie należy pisać kodu.

Edit:
Mam pewne intuicje dotyczącą zadania Odległość:

• z warunku na metrykę wynika macierz odległości jest symetryczna oraz przekątna jest wypełniona zerami, więc odpada nam połowa obliczeń.
• jeśli f(a) = d(a, 1) to:
  -- d(a, b) = f(a) + f(b) - 2 * f(gcd(a, b))
  -- f(a) można spamiętywać (nie tablicować na początku tylko przy okazji) w zwykłej tablicy,
• dzielenia można zastąpić mnożeniem - http://agner.org/optimize/optimizing_assembly.pdf , rozdział: Repeated integer division by the same value (all processors), otrzymane stałe stablicować - a_i jest ograniczone przez milion, a więc obliczanie tych stałych powinno trwać ułamek sekundy,
• należy skanować i wypełniać tablice w taki sposób, aby maksymalnie wykorzystać pamięć podręczną procesora,
• jeśli na wejściu pojawiają się duplikaty, np (a_i1, a_i2, ... ) to dla a_ix wystarczy wybrać indeks dowolnego innego elementu z tego ciągu,