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;

        }

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

Google Code Gem - Qualification

Так уж получилось что я его пропустил. Поэтому просто порешаю для себя.
Кволификация простая.
Я ее переформулирую чтобы было поинтереснее...

Пусть у нас есть последовательность состоящая из нолей и других различных N чисел.
Например - 0,0,1,0,2,2,0,0,1,3,0,0,0,0,3,0,2
Пусть у нас есть N тригеров. В начальный момент времени какой-то тригер i включен, остальные выключены. Мы сканируем последовательность. Когда встречается номер текущего включенного тригера мы должны этот триггер выключить и включить какой-то другой.
Например - пусть у нас включен в начале 1й триггер, тогда на 3м шаге мы должны выключить 1й и включить какой-то другой.
Задача - минимизировать количество переключений триггеров.

Решение которое пришло мне в голову достаточно простое. Пришлось только повозиться с доказательством его правильности). Решение в виде "жадного" алгоритма. Мы сканируем последовательность отмечая места в который i-й триггер нужно выключить. Когда все триггеры отмечены - последний отмеченный и будет пырвым триггером который мы должны выбрать для включения. Затем помечаем его как включенный и повторяем операцию для оставшейся части последовательность. Если последовательность закончилась - берем 1й попавшийся.

std::vector<int> google_code_gem_intro(std::vector<int>& in,int length)

{

    std::vector<int> res;

    std::vector<int> b;

    for(int i=0;i<length;++i)

        b.push_back(0);

 

    int total=length;

    for(std::vector<int>::iterator tV=in.begin();tV!=in.end();++tV)

    {

        if(!*tV)

            continue;

        if(    b[*tV]==0)

        {

            --total;

            if(!total)

            {

                res.push_back(*tV);

                total = 0;

                for(int i=0;i<length;++i)

                    b[i]=0;

                total=length-1;

            }

            b[*tV]=1;

        }

    }

    if(total)

    {

        for(int i=0;i<length;++i)

        {

            if(!b[i])

            {

                res.push_back(i);

                break;

            }

        }

    }

    return res;

}

Задачка на вероятность.

Задачки на расчет вероятности всегда вызывали у меня определенные трудности.
Но в этот раз вроде удалось обойтись без формул.
Итак

Есть самолет, есть 100 пассажиров. В самолет заходят в порядке очереди, т.е. человек сидящий на 1м месте заходит 1м и т.д. 1й пассажир - неадекват. Заходя в самолет он садится не на свое место а на случайное. Остальные пассажири действуют так - если их место свободно они содятся на свое место. Если занято - на любое.
Вопрос - какова вероятность того что последний 100й пассажир займет свое место.

Ну понятное дело...сначала я пытался формулы выписывать.
Потом в голову пришло решение попроще...
Заметим, что у 100го пассажира не так много вариантов. Он либо займет свое место. Либо он сядет на 1е место. Другой ситуации быть не может. Более того - для любого пассажира если его место занято вероятность занять 1е место (после этого порядок восстановлен) и 100е место одинакова. Для первого пассажира также вероятность занять 1е и 100е место одинаковы. Видно что 1е место и 100е место симметричны. Вывод - 1/2.

когда приходит время договориваться...

Рассмотрим некоторую игру:

Двое играют против казино. У них есть карточки с цифрами 1 и 0. В каждом раунде они выкладывают эти карточки и получают от казино деньги. Либо же платят их казино.



1. Если оба игрока выложили 0, то они платят казино по десять рублей.
2. Если один из игроков вложил 1, а другой 0, то выложивший 1 платит сто рублей, а выложивший 0 получает сто рублей.
3. Если оба игрока выложили 1, то оба получают от казино по пятьдесят рублей.


Оба игрока очень умные и рациональные эгоисты. Они быстро просчитывают ситуацию: выгодно выкладывать 0. Поскольку в этом случае либо выигрываешь сто рублей, либо проигрываешь десять. При выложенной же единице, либо выигрываешь пятьдесят, либо проигрываешь сто. Более того, каждый знает, что соперник не дурак, проигрывать сто рублей не согласится, поэтому обязательно выложит 0.

В результате на каждом раунде игроки проигрывают по десять рублей. Хотя есть способ обоим выигрывать пятьдесят.

Этот способ можно было бы реализовать договором, однако без него каждому из игроков выгодно, чтобы соперник выложил 1, а сам игрок 0.

Ситуация не разрешима в рамках даже самого рационального эгоизма. И вывод из неё: игрокам необходимо договориться.

Задачка на переход в двоичную систему исчисления.

Просто часто попадается

есть 1000 бутылок вина. одна отравлена. есть 10 кроликов. любой из них умирает через 15-20 дней после принятия яда. яд смертелен в любых кол-ах. после 21 дня нужно определить, в какая бутылка отравлена

решение - переводим номер бутылки в двоичную систему счисления. Если n-й бит == 1 поим n-го кролика из это бутылки. На 21й день получаем число (если n-й кролик умер на n-й позиции 1 иначе 0, переводим в десятичную).

Про старушек

Из города А в город Б и из города Б в город А на рассвете одновременно вышли две старушки. В 12 часов они встретились. Потом продолжили свой путь. Одна пришла в конечный пункт в 4 часа дня, а другая — в 9 вечера. Вопрос: в каком часу рассвело в этот день?

Задача несложная...но одно но...
По легенде эта задача была задана математику В.Арнольду когда он учился в 5м классе. Соответственно решение должно быть на уровне 5го класса...

Мое решение пятикласника:

Первая старушка двигается за 4 часа прошла столько же сколько вторая от рассвета до обеда. Вторая за 9 часов прошла столько же сколько первыя от рассвета до обеда. тогда t*v1=9*v2 и t*v2=4*v1. Дальше просто но возникает квадратный корень... Не похоже на пятикласника. Проще я придумать не смог, все равно возникает квадратный корень.

Быстрее быстрой сортировки...

Задача (подсмотрел у avva)

Отсортировать 5 элементов за максимум 7 операций, используя только операции сравнения. Т.е. только ">" или "<".

Поиск решения для меня занял около часа...ибо пошел неправильным путем.

Подсказки к решению:
Лучшее сравнение это такое которое независимо от результата убирает половину возможных вариантов. Если наши сравнения именно такие то за 7 сравнений мы можем найти нужную комбинацию из 2^7=128 возможных комбинаций.

У нас 5 элементов, значит существует 5!=120 возможных комбинаций их взаимного расположения. Значит...

Project Euler, problem 191

Давно не заходил на Project Euler, успел опуститься до 3й сотни.
Проблема оказалась простой. Как обычно просмотр решений был гораздо интереснее.
Больше всего понравилось одно из решений на С++. Это было самое быстрое решение. Понравилось настолько что приведу его...

int euler_191()

{

    int O,Oa,Oaa,L,La,Laa,SO,SL,Result;

    O=1;

    Oa=1;

    L=1;

    SO=2;

    SL=1;

    for (i=2, i<=30,i++)

    {

       Oaa=Oa;

       Oa=O;

       O=SO;

       Laa=La;

       La=L;

       L=SL+SO;

       SO=O+Oa+Oaa;

       SL=L+La+Laa;

    }

    return SO+SL;

}

Думаю оно не очень понятно...поэтому обьяснение.

here are only 6 states in which strings can exist, divided into two groups. Three of those states are those where the strings don't contain any LATE occurence. The other three are those where the strings already contain one LATE occurence. Within each group, one state is when the string does not end with an absence, another when the string ends with only one absence, and the third when the string ends with two absences. Let's denote them as O, Oa, Oaa, L, La and Laa. Let's denote the sums of these two groups as SO and SL.

The initial states after the first day would be O=1, Oa=1 and L=1(all other states =0). The initial sums would be SO=2 and SL=1.
a) If absent on the following day, all strings in state Oa would become Oaa strings and all strings in state O would become Oa strings. Similarly, all strings in state La would become Laa strings and all strings in state L would become La strings.
b) If late on the following day, all strings in group O would become L strings.
c) If neither late nor absent on the following day, all strings in group O would become O strings (O=SO), and all strings in group L would become L strings in addition to (b) above such that L=SL+SO.

The following algo should produce the answer within 1 ms with most (if not all) programming languages. zeycus and logopetria have already posted similar algos in their own programming language.

Также понравилось рекурсивное решение.

int blah(int d, int a, bool l)

{

    return d == 0 ? 1 : (blah(d - 1, 0, l) + (a >= 2 ? 0 : blah(d - 1, a + 1, l)) + (l ? 0 : blah(d - 1, 0, true)));

}

Первые шесть месяцев продаж неплохого приложения...

A Look Back at HelpSpot’s First 6 Months of Sales

October - $3,277.96
November - $626.50
December - $4,163.00
January - $1,253.00
February - $3,967.46
March - $8,703.03

C++ интересный трюк с приведением типов

Нагло сперто с RSDN.

Возьмём простенький пример:

enum colors {red, green, blue};

 

struct proxy

{

    operator colors () const

    {

        return red;

    }

};

 

proxy f()

{

    return proxy();

}

 

int main()

{

    colors c = f(); // хорошо

    int i = f(); // спорно, но компилируется

    std::cout << f(); // спорно, но компилируется

    unsigned u = f() + 1; // совсем спорно, но компилируется

    if (f()) // совсем спорно, но компилируется

        std::cout << "if\n";

}

Теперь немного допилим напильником:

struct proxy

{

    operator colors () const

    {

        return red;

    }

 

    private: template<typename T> operator T () const;

};

 

int main()

{

    colors c = f(); // хорошо

    int i = f(); // не компилируется

    std::cout << f(); // не компилируется

    unsigned u = f() + 1; // не компилируется

    if (f()) // не компилируется

        std::cout << "if\n";

}

Получается что-то типа explicit conversion operator. Автоматически приводится только, если тип полность совпадает, в противном случае надо писать явный каст:

int main()

{

    std::cout << (colors)f(); // ок

}

Таким же образом можно определить несколько типов, для которых должен быть неявное приведение:

class proxy

{

    public: operator char const* () const

    {

        return "hello from proxy";

    }

 

    public: operator wchar_t const* () const

    {

        return L"hello from proxy";

    }

 

    private: template<typename T> operator T () const;

};

красота...