Google Code Gem - round 1A

Первая задача первого раунда была повеселее...

Problem

You are given two vectors v1=(x1,x2,...,xn) and v2=(y1,y2,...,yn). The scalar product of these vectors is a single number, calculated as x1y1+x2y2+...+xnyn.

Suppose you are allowed to permute the coordinates of each vector as you wish. Choose two permutations such that the scalar product of your two new vectors is the smallest possible, and output that minimum scalar product.

Как решал я...
Ну во первых перебор это конечно хорошо для малых n...но поскольку в большем тестовом задании n==800 а 800! это "много" от перебора можно отказаться сразу.

Сначала делаем матрицу n*n, такую что m[i][j]=v1[i]*v2[j];
Обычное скалярное произведение это Cум(m[i][i]). У нас же эта будет такая сумма что i и j встречаются только один раз.

Рассмотрим следующую идею.
Возьмем какое-то скалярное произведение и будем его улучшать до тех пор пока улучшение возможно.
Как улучшать - ищем такие m[i][j] и m[l][k] что что m[i][j]+m[l][k]>m[i][k]+m[l][j]. Как только нашли меняем m[i][j] на m[i][k] и m[l][k] на m[l][j]. Если не смогли найти - ура.

Основной код, очищенный от ввода/вывода:

        vector<pair<int,int>> product;

        for(int i=0;i<a1.size();++i)

            product.push_back(std::make_pair(i,i));

 

        while(true)

        {

            bool improved = false;

            for(vector<pair<int,int>>::iterator v=product.begin();!improved && v!=product.end();++v)

            {

                for(vector<pair<int,int>>::iterator v1=v+1;!improved && v1!=product.end();++v1)

                {

                    int i=v->first;

                    int j=v->second;

                    int l=v1->first;

                    int k=v1->second;

                    if(m[i*a1.size()+j]+m[l*a1.size()+k]>m[i*a1.size()+k]+m[l*a1.size()+j])

                    {

                        v->second = k;

                        v1->second = j;

                        improved = true;

                    }

                }

            }

            if(!improved)

                break;

        }

Остально доказать что такой метод действительно приведет нас к лучшему результату а не просто к неплохому результату...Такие вещи я доказываю очень плохо..но кажется по индукции и это доказуемо.