И снова задачки

А задачек поднакопилось. Не будем писать, с чьих собеседований, будем просто радоваться. Задачки хорошие, такие, по мне, можно смело спрашивать.
Сегодня у меня аж целых три, признайтесь, вы их ждали!


Есть лошади, которые бегают с разной скоростью и никогда не устают. Лошади могут учавствовать в забегах, в одном забеге может участвовать не более N лошадей. Результатом забега является очередность, в которой лошади дошли до финиша, то есть на выходе – список, на каком месте была какая лошадь в забеге.
Всего лошадей N^2.
Спрашивается – за какое минимальное количество забегов можно найти M лучших их них?

Есть односвязный список, у которого в каждом элементе есть еще один указатель на некоторый элемент этого списка. То есть, кроме next в ноде есть еще один мембер, который указывает на любой элемент списка. Может сам на себя, могут несколько таких указателей указывать на один элемент, как угодно. Хочется создать копию этого списка, разумеется, со скопированными ссылками в элементах. За линейное время и без дополнительной памяти, кроме как на саму копию. В процессе клонирования изначальный список изменять можно, но в конце, разумеется, вернуть в изначальном состоянии.

Даны три массива целых положительных чисел длиной N.
Нужно выбрать из каждого из них по одному числу так, чтобы сумма равнялась некоторому данному C. Изменять массивы – можно.
С константными затратами памяти и сложностью O(N^2).

Have fun.

  • http://netxms.org alkk

    #2 – можно ли заложиться на то, что список будет одним блоком памяти?

  • http://blog.fxposter.org/ FX Poster

    По первой задаче вроде как (N+M). Проводим N забегов, выбираем N первых лошадей, проводим N+1-й забег, кто был первый – того отбираем. Далее вместо отобранного подставляем лошадь, которая была второй в забеге, в котором участвовала отобранная лошадь с самого начала. Вот так по одной отбираем M лошадей.

    Это первое, что пришло в голову. Сейчас еще подумаю.

    Вторую вроде как можно сделать за 2 * N, но с использованием hashmap’а, который будет map’ить адреса элементов старого списка в адреса элементов нового. Т.е. сначала копируем список, не заполняя random-поля, и занося в хеш адреса – старые и новые, а потом что-то типа такого:

    Node* oldList;
    Node* newList;
    HashMap map;

    while(oldList) {
    newList->random = map.get(oldlist->random);
    newList = newList->next();
    oldList = oldList->next();
    }

    Над третьей пока не думал.

  • http://blog.fxposter.org/ FX Poster

    > без дополнительной памяти, кроме как на саму копию.
    Блин, не дочитал…

  • fuxx

    Для второй задачи:
    Правильный выбор структуры данных поможет. Если хранить список в виде массива, а вместо указателей использовать индексы, то для создания копии будет достаточно вызвать memcpy. Время линейное, дополнительная память не нужна.

  • Pumba

    Во второй получилось 3*N.

    Node *list = ;
    Node *newlist = NULL;
    Node *listit = list;

    // Copy
    while (listit)
    {
    Node *newnode = new Node();

    newnode->link = listit->link;
    listit->link = newnode;

    listit = listit->next;
    }

    // Update pointers
    newlist = list->link;
    listit = list;
    while (listit)
    {
    listit->link->next = listit->link->link->link;
    listit = listit->next;
    }

    listit = list;
    while (listit)
    {
    Node *copy = listit->link;

    listit->link = listit->link->link;
    copy->link = copy->next;

    if (listit->next)
    copy->next = listit->next->link;

    listit = listit->next;
    }

    Перекидываем линк указатель из старого листа в новый. А за место него помещаем указатель на новый элемент в новом списке. Отсюда имеем свободный next указатель в новом списке, который используется как место для вычислений. Далее все просто.

  • CEMEH

    fuxx, aklk:
    Ни на что закладываться нельзя, это честный список со случайно разбросанными по памяти нодами. Структуру данных менять нельзя, это условие задачи.

    Pumba:
    Мне кажется, третий шаг свалится.
    listit->link = listit->link->link; полагается на то, что link у ноды в новом списке еще не изменен, а вот здесь: copy->link = copy->next; он изменяется. Если в результате перехода в первом выражении мы попадем на ноду втрого списка, где link уже исправлен, то будет опаньки.
    Настойчиво предлагаю рисовать картинки и писать тесты :)

  • Pumba

    CEMEH:

    Нет, не свалится. Третий шаг делает только переброску указателей. Дело в том что линк старого списка это просто указатель на прямую позицию в новом. То есть например link 5 елемента старого списка ето указатель на 5 элемент нового. Пэтому copy->link = copy->next; ничего не портит, так как этот елемент больше не будет использоваться.

  • CEMEH

    Pumba:
    Ну вот после этого окажется, что элемент 17 содержит ссылку на 5, пойдет туда, а у него link уже выправлен.

  • Pumba

    CEMEH:
    Он не может туда пойти так как 17 всегда указывает на 17.

  • sander

    2 Pumba
    Вы высказали основную идею и привели почти правильное решение, но все-таки оно свалится :D

    Node* copy_list(Node *source)
    {
    for(Node* plist=source,plist;)

    ]

  • sander

    Node* copy_list(Node* source)
    {
    for(Node* plist=source;plist;)
    {
    Node* newnode=new Node(*plist);
    plist.next=newnode;
    plist=newnode->next;
    }

    for(Node* plist=source;plist;)
    {
    plist->next->random=plist->random->next;
    plist=plist->next->next;
    }

    Node* result=source->next;
    for(Node* plist1=result,plist2=source;plist1;)
    {
    plist1->next=plist1->next->next;
    plist2->next=plist2->next->next;
    }
    return result;
    }

  • Pumba

    sander:
    Можно узнать почему?

  • sander

    2 Pumba
    Во-первых, я не вижу каким образом, в поле next нового списка может попасть NULL – конец списка. ИМХО, строчка if (listit->next) явно лишняя. И как-то странно смешиваются поля next и link – но пример буду думать на свежую голову. Может все и нормально.

    В своем коде я тоже накосячил – последний цикл разделения списков следует читать как
    for(Node* plist1=result,plist2=source;plist1;)
    {
    plist1->next=plist1->next->next;
    plist2->next=plist2->next->next;
    plist1=plist1->next;
    plist2=plist2->next;
    }

  • Pumba

    sander:
    Ну да, забыл затерминайтить список, так же будут проблемы если link равно NULL. Но код был скорее показать алгоритм. Накидал по быстрому в редакторе.

  • pINGVA

    большое спасибо за отличные задачки!

  • CEMEH

    Pumba
    Посмотрел внимательней. Ага, похоже будет работать.

  • http://max630.net/ max630

    > По первой задаче вроде как (N+M)

    по-моему, можно сделать немножко быстрее.
    чтобы найти второго, нам надо выбрать всего из 2-х – того кто проиграл лидеру в отборочном, и в финальном.

    чтобы третьего – добавляются ещё 3

    таким образом, N+2′м забегом можно найти не только второго, но несколько первых. Навскихку – число их пропорционально корню из N.

    что там дальше – не сообразил ещё.

  • deemetrius

    Про первую задачу. Если время забега каждой лошади — константа, и не зависит от присутствия конкурентов, то за N забегов можно выбрать M лидеров. Просто тупо хранить время забега каждой лошади, упорядочить по возрастанию и взять первые M.

  • deemetrius

    Забыл сказать, что каждая лошадь должна учавствовать в забеге один раз.

  • deemetrius

    Третья задача: Проходим каждый массив и просматриваем одновременно наличие C и 0. Дальше пока не думал ;))

  • tabernacle

    Третья задача:

    сортируем списки по возрастанию(n*log(n) – ерунда:)).

    Потом идём по первому списку, по второму, а в третьем только перемещаем указатель вперед. Вот и получается n*n.

  • CEMEH

    deemetrius, все неправильно, но жжошь, сцуко!

    tabernacle, подробнее!

  • tabernacle

    CEMEH:

    int index = 0;

    for(int i = 0; i C)
    {
    index = index == 0 ? index : index – 1;
    continue;
    }
    }
    }

    Console.WriteLine(“Oooops.”);

  • tabernacle

    int index = 0;
    for(int i = 0; i C)
    {
    index = index == 0 ? index : index – 1;
    continue;
    }
    }
    }

    Console.WriteLine(“Oooops.”);

  • tabernacle

    Форум жрёт символы как теги, похоже. Ппопрбуем так :) :

    int index = 0;
    for(int i = 0; i smaller capacity; ++i)
    {
    index = 0;
    for(int j = 0; j smaller capacity; ++j)
    {
    if(a[i] + b[j] + c[index] smaller C)
    {
    if(index == capacity – 1)
    break;

    ++index;
    –j;
    continue;
    }

    if(a[i] + b[j] + c[index] == C)
    {
    Console.WriteLine(“{0} {1} {2}”, a[i], b[j], c[index]);
    return;
    }

    if(a[i] + b[j] + c[index] greater C)
    {
    index = index == 0 ? index : index – 1;
    continue;
    }
    }
    }

    Console.WriteLine(“Oooops.”);