Pull to refresh

Comments 116

Я или неправильно понял вторую задачку, или мы проходим в цикле N элементов от 1 и смотрим, если следующим от N-ого элемента будет 1, то цикл есть, иначе цикла нет. Получаем O(N).
Веселая = глупая? Если бы было хотя бы O(NlogN) , вот это было бы весело, имхо.

На счет первой задачки, она уже интереснее, надо подумать. Как придумаю, скажу что-нибудь.
Не понимаю. Почему минусуют? В принципе и ит тематика маленько. И интересно) Наверно эт только я так считаю...
наверное потому что хотят решение :)
Не волнуйтесь, это очень типичная для Хабра ситуация - интересный топик сначала немного минусуют, затем плюсуют, постепенно выводя на первую страницу, а затем идет скачок оценки и количества комментариев.
Во второй задаче - может функция getNext возвратить тоже значение? Будет это считаться циклом?
Я чего то не понял? в первой задаче решение - поместить все станции в одну точку. И тогда действительно максимальное расстояние от города до ближайшей станции будет минимально.
А со второй просто - если через N шагов мы не дошли до конца списка или встретили хоть одну 1, то это цикл.
Внимательно перечитайте условия:
1) Контрпример: два города, две станции. Оптимальное расположение - в каждый город по станции;
2) N неизвестно.
Хорошо, тогда эту задачу можно подвести к задаче кластеризации.
В первой - непонятно. Города на прямой стоят? Если да, то почему не расставить станции равномерно по прямой от нуля до последнего города или до конца если есть.

Во второй задаче есть максимальная длинна цикла? Надо туда рекурсию :-) Надо посмотреть первые 2 максимальных порядка и проверить асе последующие на повторения, наверно.

А вообще я не программер, так что затыкаюсь и ухожу :-)
Мне интересно будет потом прочитать решения.
Решение задачи от Microsoft.
Я так понял условие, что если цикла нет, то getNext(last_element) возвращает что-то уникальное (я обозначил это нулем).

iterator p1 = begin ();
iterator p2 = begin ();
while (p1 != p2)
{
if (getnext (*p2) == 0)
break;
++p2;
if (getnext (*p2) == 0)
break;
++p2;
++p1;
}
if (getnext (*p2) == 0)
цикла нет
else
цикл есть

Оценка очевидна.
конечно же, надо
do
{
...
}
while (p1 != p2);
Можете заново написать код пожалуйста. Внизу. Функция вернет false в случае окончания.
iterator p1 = begin ();
iterator p2 = begin ();
do
{
if (getnext (*p2) == 0) break;
++p2;
if (getnext (*p2) == 0) break;
++p2;
++p1;
}
while (p1 != p2);
if (getnext (*p2) == 0) цикла нет
else цикл есть
1)к как я понимаю ++p1 означает p1 = getNext(p1)?
2) условие последнее не верное. но сути не меняет ;)
1) По сути дела да. Просто я по хорошей привычке работаю с итераторами (указателями) и ++p1 означает перевести указатель на следующий элемент.
2) Условие будет верное, если цикла в списке нет.
Извиняюсь. Я туплю так сказать)
А какая возникает проблема?
После первой итерации p1 указывает на 2, p2 на 1
После второй (и последней) — p1 на 1, p2 на 1
Мы получили, что цикл есть.
сначала р1->1 p2->1, когда доходим до первой проверки while получаем p2->1 p1->2, после того, как заходим во вторую итерацию цикла вылетаем на проверке getnext(*p2) == 0. Или не так?
как я понимаю, когда мы доходим до конца списка getnext возвращает NULL? Если нет и цикл замкнутый, то как мы остановимся, если нет циклов и нет нулевого элемента?
По-моему, вы смешиваете порядок элементов, в котором они хранятся в списке и порядок, который задаёт функция getnext (итераторы в коде работают с функцией getnext). Для устранения этой двусмысленности нужно заменить в условии список на массив.
Это структура в которой заданы следующие элемент за ним, либо null. В принципе большинство я думаю поняли.
getNext возвращает элементы не в порядоке, в котором элементы идут в списке? Это мягко говоря очень не очевидно :) Кроме того что тогда вернет getNext(1) в списке 1->2->1->3 ?
В результате долгой переписки с ttim выяснили, что решение таки верное :) Просто непривычная запись. Я под 1->2->1 понимаю список из 3-х элементов со значениями 1, 2 и 1, а в условии понимается список из двух, где за первым идет второй, а за вторым первый. Спасибо за разъяснения.
> getNext(last_element) возвращает что-то уникальное (я обозначил это нулем).
Ээээ, а с чего бы то?
В условии это не сказано. В условии сказано только ограничение в N элементов. Что творится за пределами N, нам ни в коей форме неизвестно, поэтому условие останова может быть только таким: алгоритм должен за C*N итераций подтвердить существование цикла, но в случае, если за C*N итераций (где мы должны явно объявить C) цикла не найдено - это должно значить, что цикла нет.
Да, но getNext(last_element) должна же что-то вернуть (ну или хотя бы исключение бросить). Если бы мы всегда могли рассматривать результат как элемент списка, то случай без цикла был бы невозможен.
Я не совсем понял, при чём там итераторы :), но у меня мысль следующая:
наша задача - найти, есть ли цикл внутри цепочки из N элементов. N нам не дают, но при этом алгоритм обязан быть O(N). Это может значить только то, что у системы есть какой-то внешний останов. Типа, внешний таймер, который реальное значение N знает. Наподобие ограничения времени в олимпиадных системах. И ему мы можем сказать: "останови нас через 2*N итераций", допустим.
Если getNext (last_element) бросает какое-нибудь исключение или возвращает какой-нибудь ноль, то алгоритм "пробежать N итераций и посмотреть, не будет ли null-а; если null - цикла нет", вообще говоря, имеет сложность O(N) :)
Если я правильно понял твой алгоритм, я пришёл примерно к такому же решению. "Начать бегать по списку двумя курсорами; один курсор бежит в два раза быстрее второго, зато читает сразу по два элемента; если в какой-то момент медленный курсор прочитал значение, равное одному из двух прочитанных значений с быстрого курсора - значит, медленный курсор уже перешёл точку начала цикла, а быстрый курсор уже пробежался по циклу как минимум один раз и начал его заново, и догнал медленный курсор". Так?
Тогда такой алгоритм даже не требует конечного элемента списка. Если считать, что за пределами N getNext всё равно что-то возвращает (просто нам уже не важно, возникают ли ТАМ циклы, наша задача - проверить наличие циклов в первых N элементах), то где-то за 2N итераций мы либо гарантированно встретим цикл, либо не встретим. За
Я не программер)
Но думаю оптимально это посередине между городами устнавливать.)))) Но это если по прямой.а если города на плоскости? и на разных расстояниях друг от друга?
вобщем это наверно задача из рода про капусту,козла и волка =)
Там ведь городов N, а станций К. К может быть не равно N, поэтому одна станция может быть ближайшей для нескольких городов.
И у города есть координата х, поэтому считаем, что города находятся на прямой на разных расстояниях.
Козлы с капустой здесь точно не при чем.
В первой N дано естно.
Пример где равномерное распределение не проходит: N=3 K=2, координаты 1 3 10.

Перенес топик в Я умный.
как-то не совсем понял первую задачу, но она очень напоминает классическую задачу Комивояжора, и оптимальное её решение через нейросеть...
Через нейросеть? O_o
Ссылочку не дадите?
Странно. Никогда не знал. Ссылочку реально можно. Мало верится)
"Оптимальное" и "через нейросеть" почти взаимоисключающие понятия. Доказать сходимость, насколько я знаю, удается только для некоторых канонических структур НС.
Нет. Это классическая задача для генетических методов.
Аналогично, доказательство сходимости проблематично.
Под эту задачу вроде бы есть теорема для ГА.
Сильно сомневаюсь. Учиывая, что ГА построены на стохастических закономарностях, какое-то доказательство о сходимости может быть построено только на бесконечном времени.
Вы не путайте практическое применение и "спортивное программирование" ;) С точки зрения практики - да, генетические алгоритмы иногда отлично подходят. Но с точки зрения решения программистских задачек "на бумажке" - нет никакой гарантии, что ГА ее решит. Математически обосновать такое решение практически невозможно.
Похоже, здесь подвох в другом. Зная, что это задача для генетических алгоритмов, претендент должен понимать, что оптимизировать ее решение простыми методами не получится, а можно решить только "в лоб" прямым перебором. О чем и сказать на собеседовании.
Если это та задача Коммивояжера, о которой я слышал, так она является NP-полной, и оптимального алгоритма решения не существует!
Я рассматривал эту задачу в курсовой как пример гамильтонового цикла в графе. И к данной задачке я ее не могу прикрутить в голове.
Что Вы называете "оптимальным алгоритмом решения"? NP-полнота не означает отсутствия решения, и полиномиальной сложности в первой задаче никто не требовал ;)
во второй задаче можем ли мы ставить в какое-то поле списка метку, что мы там уже были?
можем ли мы завести один массив, в котором хранить номера, в которых были?

есть такая идея

x=0;
count=0;
do{
x= x xor getnext();
count++;
} while (count<n && x!=0);
if (x==0) есть циклы;
if (count==n) дошли до конца списка и циклов не нашли;
хабр скушал кусок кода :)
while (count!=0 and count<n)
1) Как осуществить проверку coun < n? N же не дано.
тогда можно наверно как-то так сделать:

x=0;
t=0;
do{
x= x xor t;
t=getnext();
} while (x != 0 and t != nul )
if (x==0) есть циклы; else нету.
Не правильно.
Смотри - 1->2->3->4->2. В 2 ты будешь иметь 1!
да.. действительно.. не учёл, что цикл может начинаться не с начала...
2 опечатки: "Mircosoft", "в списоке".

А в первом случае ответ: "надо погуглить".
исправил. Спасибо!
в первой задаче в том случае, если станций не хватает на все города, то я бы взял наибольшее расстояние между 2 городами поставил станцию между ними, затем следующее наибольшее и т.д.

т.е. у нас есть некий сортированный стэк расстояний. Если он кончился - значит станций все таки хватает на все города и нефиг ;)

про вторую задачу что-то в голову ничего умного не лезет. ну давайте помечать пройденные узлы или сохранять их в HashMap.
Добавил ограничение на память в 2 задаче.
ты это специально усложняешь? :) O(1) на память это от себя или от Microsoft ?
От Микрософт)
Без этого задача не интересна)
Складывается ощущение, что ты реально придумал задачки. :) И исправляешь теперь, дополняешь. ;)
Не в обиду! :)
Все проще. Я задачи на память писал, и до этого они были только в усном обиходе. Вот я их и переврал сначала. Так все правда)
Выше уже есть решение с O(1), так что требующее больше памяти не интересно :)
все. понял, что не так понял. пытался найти циклы в такой, например, цепочке 1 -> 2 -> 3 -> 2 -> 4 -> 5 ...
Про первую: 4 города (0,2,10,14), 2 станции. По вашему методу станции надо ставить в 7 и 8 (или 6 и 12, если имелось ввиду расстояние между соседними городами), хотя вариант 1 и 12 оптимальней
В первой задаче динамикой можно решить за O(N*K) и памяти порядка 2*N. Можно лучше?
Да можно. Причем решение дегче динамики :)
Ну есть вариант который имеет сложность O(N*log(Xn-X1)), где Xn координата последнего города, X1 - первого. Подходит если координаты целые числа или задана точность с которой нужно выдать ответ.

Решение - бинарный поиск с жадным алгоритмом(бинарным поиском перебираем длину наибольшего отрезка от какого-нибудь города до станции, а жадным алгоритмом пытаемся расставить станции так что бы влезть в это ограничение). Но есть подозрение что существет линейной решение. Так ли это?
Возможно конечно и существует, но я имел ввиду ваше решение)
Только не понимаю для чего координаты целые?
Скорее не сами координаты городов, но и длинна наибольшего отрезка. Если они не целые, то должна задаваться точность с которой нужно давать ответ. Иначе непонятно когда останавливать бинарный поиск.

И лучше на ты :)
согласен, красивое решение
И еще. Зачем так много памяти. Ты хотел сказать N*K?
Не 2 в степени N, а 2 умноженное на N :)
По первой задаче: во первых удобней говорить не о станциях а разбиении городов на отрезки так чтобы максимальный диаметр был как можно меньше.

Решается так: берем какое-нибудь решение и его максимальный диаметр d.

Если это решение не оптимальное то его можно улучшить.

Пусть длина самого первого отрезка d_1<d, отнимем часть точек(городов) второго отрезка и передадим первому так чтобы d_1 был максимальным но оставался меньше d.
Повторим ту же процедуру со вторым и третьим отрезком и там до тех пор пока не дойдем до отрезка с максимальной длиной.
Если мы отняли у него хоть одну точку - значит максимум уменьшился.

Процедуру можно гонять справа и слева.
Если вообще ничего не шевелится, значит решение оптимальное. Писать доказательство лень, но оно простое.

делается заведомо за O (N x K)


Вторую задачу не понял если f(1)=1 то вроде сразу получается цикл.
Если имеется в виду что x_н = f(x_c)+1
то видимо прокатывает стандартное решение:
гоним две цепочки в одной идем по одному шагу в другой по два.
Если в какой-то момент значения совпали - значит зациклились.
Если вышли за границу диапазона - значит не зациклились.

Собственно можно просто шагать и если за N шагов не вышли за границу диапазона - значит зациклились.

Это решение про цикл начинающийся с 1.
Может нужно выяснить есть ли цикл вообще начиная с произвольного номера?
Можешь пояснить?
Во-первых: про первую задачу:
Пусть длина самого первого отрезка d_1
>Повторим ту же процедуру со вторым и третьим отрезком
Какую процедуру? В чем она заключается? Ч то за операция «отнять точку?»


Про вторую задачу:
Допустим есть цикл 1-2-3-1-4
Если идти твоим алгоритмом, то
Первая цепочка дает: 1-2-3-1-4
Вторая цепочка дает 1-3-4-2-1
Кроме первого элементы попарно не совпали нигде. Я не точно понял алгоритм?
процедеру передачи точки от одного отрезка другому.
Подробнее лень. Итак много написал. Надо было как tasman:
http://www.habrahabr.ru/blog/i_am_clever…

Думаю решение можно найти в интернете вполне обычная школьно-олимпиадная задачка.


по второй задаче - дальше надо идти совпадение будет.

цикла 12314 кстати быть не может мы из 1 либо в 2 либо в 4 попадаем.

Еще если все переходы остаются внутри диапазона 1..N то цикл есть всегда. Это тривиальный факт.
Я просто пытался дать возможность подумать другим, не рассказывая решения, хотя особо народ не увлекся. По твоей оценке получается O (N x K)? Динамика тоже дает такую сложность, но ttim говорит что можно лучше...
Именно, можно быстрее!
Задачкам точно пора в Спортивное программирование! :)
следует понимать, что в задаче 1 такое разбиение не единственно. пример города в точках 0, 10, 1000, 1500 и две станции. одну станцию, очевидно, ставим в точке 1250, вторая - в любой точке отрезка 0-250.

Единственность решения возможна, но это тоже надо бы доказать, если требовать минимизацию суммы расстояний от каждого города до ближейшей станции. И, конечно, никто не говорит, что решение этой задачи является решением исходной.

Решение я бы искал с конца - как мы докажем, что найденное нами решение - и есть наилучшее.
Я бы даже сказал вторая в любой точке отрезка [-240; 250].
Первую задачу лучше решать в пошаговом режиме. Сначала ставим одну станцию, потом вторую, третью и т.д. Кстати, непонятно, можно ли ставить станции вне городов:).

Предположим, что нельзя: ставим первую станцию в городе, ближайшем к центру населенного отрезка. В случае с 1-3-10 - возле 3. Таким образом мы уже минимизируем расстояние. Далее определяем получившиеся в результате отрезки, без учета накрытых городов, и накрываем каждый раз центр (по отрезку между имеющимися станциями, если таковые есть, или крайним городом и станцией, если это крайний отрезок) того отрезка, где расположен самый удаленный город. При этом страдает скорость: нужно просчитывать xi-sj для всех i=1..N; а также решение может быть не самым оптимальным.

Оптимизировать задачу при высоких K можно, разбив ее на "дебют", "миттельшпиль" и "эндшпиль". Вначале упор делается на сегментацию, мы просто механически разбиваем область на 2^a элементов, где a примерно равно sqrt(k). Далее, в средней фазе, нужно сократить объем вычислений, минимизировав лишние проверки (которые все равно будут фикситься на последнем этапе). Тут целесообразно будет объединить имеющиеся неохваченные города в неперекрывающиеся кластеры, для каждого из которых достаточно указать координаты начала и конца - и брать в расчет только крайние города кластеров. Кластеризацию для большого множества можно выполнять несколько раз (путем дробления), в конце вместо кластеров можно учитывать уже отдельные города. Наконец, после достижения момента, когда станций осталось меньше чем на 2 шага, но больше чем на 1, возможна ситуация, когда ход в центр отрезка будет неоптимальным, т.к. отрезок наилучшим образом разбивается на 3 части двумя станциями. Тут распределение по отрезкам уже будет неравномерным: некоторые пополам, некоторые натрое (или некоторые натрое, некоторые начетверо). Задача теперь определить приоритеты, куда эффективнее поставить 2 (3) станции, а где хватит 1 (2). Отсеваем возможные пустые отрезки, учитываем только с городами. Пробуем расставить вначале меньшее число станций (гарантированное), проверяя на максимум только внутри отрезка, затем каждый раз при наличии лишней станции берем отрезок с максимальным расстоянием от проектной(ых) станции(й), и расставляем увеличенное на 1 их число, уже без кластеров - обычным механическим перебором. Разумеется, если в отрезке только 1 станция, а разбить его надо на 3-4, никто две станции в одну точку ставить не будет (такие отрезки, как и пустые, вообще надо учесть еще перед началом эндшпиля). Когда лишние станции закончатся, все незатронутые проектные так и останутся на своих местах.

Схема, в принципе, может быть неоптимальной в абсолютном смысле, но она является оптимальной экономически, т.е. при таком раскладе не будет упущенных супервозможностей, возможное отклонение от оптимума будет минимальным.
Можно ставить не в города
непонятно(не объяснено и не доказано) почему полученное разбиение будет получено и почему оно будет наилучшим в смысле поставленной задачи
Пояснение. Во второй задаче элемент это не число пример: "1"->"333"->"ya ne chislo"->"ya tozh)"->"333"
Цикл есть.
По второй задаче (обратите внимание что первое число в цепочке 1 - кого навело на размышление о простых числах?), алгоритм для решения задачи 2 (правда его характеристики значений по памяти и сложности можно уточнить дополнительно):

P = 1 (будем умножаться)
i = 1
N > 1 (если N = 1 - то цикл есть)

a0: Для каждого N_{i+1}

a1: Если N_{i+1} = 1 то цикл есть

a2: Иначе Если N_{i+1} = простое то
a3: Если P/ делится без остатка - то цикл есть
a4: Иначе - цикла нет
a5: Конец если
a6: Конец если (a2)

a6: Если N_{i+1} = не простое то
a7: раскалдываем на простые N_{i+1} = K_{1}*K_{2}*..K_{M}
и проверяемся на "вхождение" в P

a8: Для каждого простого вхождения K_{j}
a9: Если P/ K_{j} без остатка для всех j - то цикл есть
a10: Иначе цикла нет
a11: Конец для (a8)
a11: Конец если (a6)

a12: P = P*N_{i+1}; умножаемся

a13: Конец для каждого (a0)

Насчет памяти проблем здесь быть недолжно - храним произведение (только влезть бы в разрядность представления чисел), сложность алгоритма определяется сложностью операции разложения на простые и опеределения простоты числа ? O(sqrt(M)*sqrt(N)) - тут надо прикинуть...
Другой вариант.
Разбиваем вообще всю населенную область на K сегментов и в центр каждого ставим точку. При неравномерном распределении окажется, что где-то между точками нет городов, а где-то даже есть лишние точки. В таких случаях лишние точки (если есть) временно изымаем, а между оставшимися двумя проводим рассечение области на кластеры. Это значит, что кластеры являются изолированными и друг на друга влиять станциями не могут. Оставшиеся точки распределяем по кластерам. Далее для каждого кластера разбиваем населенную область имеющимися точками, если нужно - опять часть изымаем, проходим все кластеры заново до тех пор, пока такое изъятие станет невозможным. Теперь можно работать с каждым кластером по отдельности. Можно порезать его на субкластеры k-1 раз по самым длинным отрезкам. Это еще не оптимальное разбиение, т.к. субкластер может представлять собой агломерацию с небольшими внутренними расстояниями общим размером раза в 3 больше, чем до ближайшего одинокого города, и если станций всего 2, то последний неоптимально захавает одну из них. Можно опять же порезать механически, выставить станции в ближайших городах и пробовать оптимизировать этот базовый план, добавляя лишнюю точку (каждый раз она добавляется в самый неоптимизированный кластер, где после этого выполняется перераспределение субкластером). Наконец, когда все станции выставлены, можно попробовать их сдвинуть и посмотреть, продолжится ли цепная реакция, т.е. окажет ли сдвиг следующей станции какой-нибудь эффект, если нет - сдвиг является локальным (так можно выделить кластеры нестабильности, обычно - при k чуть меньше n и примерно одинаковых расстояниях).
совсем непонятно почему то, что мы получим - является оптимальным решением. как из "предположим, что есть более оптимальное решение" вывести противоречие ?
Скоро продолжение. Но там еще дальше от программирования)
со второй задачей, по-моему, можно проще. Алгоритм такой:
S=1
Цикл
пока (S div getNext(element) != 1) выполнять:
element = getNext(element)
S = S * element
возврат в цикл

div - в данном случае = операция целочисленного деления, возвращающая частное (а не остаток)

Цикл будет крутиться пока в массиве не встретится элемент, присутствующий в S

Кажется, так

с первой задачкой, простыми методами как-то не придумывается
Да с задачей от MS все просто:
Заводим 2 переменные - максимальный найденный элемент и количество шагов.
Премся по дереву вперед, на каждом шаге обновляя первую переменную и инкрементируя вторую. Как только вторая становится больше первой - поздравляю, мы в цикле :)
Единственное ограничение, не указанное в задаче - элементы есть положительные целые числа.
красивое решение, только по условию задачи, я так понял, можно использовать только одну переменную
ЕМНИП, O(1) означает, что требуемые затраты памяти могут быть любыми, но не должны увеличиваться с увеличением N, а не то, что можно использовать только одну переменную.
Решение красиво, но есть только небольшой нюанс: согласно http://www.habrahabr.ru/blog/sport_programming/18769.html#comment242813, элементами могут быть даже не числа вовсе.
А даже если и числа, то, т.к. размерность элементов явно тоже не указана, сложность алгоритма с N не связана (а связана со значением максимального числа), и может даже быть много больше O(N).
1) числа могут быть больше N. И ооочень большими. 2) они могут быть не числами)
Вы не учитываете одну вещь. размерность S будет очень большой. И будет около N) И еще такой случай: 1->5->2->3->2. Не понимаю как он работает.
По поводу гугловой задачи, есть забавная идейка. Решить в духе "задачи N тел". Что-то типа извращённого "закона гравитации" - город притягивает станцию тем сильнее, чем дальше эта станция от него; F = С*r. Но с каждой стороны - слева и справа - город притягивает только по одной, самой ближней станции; на остальные города "гравитационный эффект" не действует. После чего получившаяся физическая модель "сама себя решает".
Правда, не совсем понятно, брать только максимальный в каждом направлении вектор "гравитации", или брать все и складывать... надо поставить эксперимент :)
про вторую задачку:
идем по списку
1. берем три элемента относительно текущего
2. если 1й+3й == 2ой+2ой - цикл есть
если цикл не найден делаем ++ итератору и начинаем сначала
не асиливаю что такое O(1) по памяти, зато итераций будет +-N
Можно продемонстрировать, как это решение работает на примерах из условия?
еще раз. там не обязательно числа!
Гугловская со слов)) а Микрософт где-то в technet блогах была
А есть решения? А то пока что-то не вижу чего-то убедительного.
Sign up to leave a comment.

Articles