Здравствуйте, Vintik_69, Вы писали:

Листаю список NPC с идеей добавить супер-шустриков с нуль-переходом и решить, скажем BIN PACKING.

А как в твоей динамике доказать, что тормоза гарантированные невозвращенцы?
т.е. ага нам нужно послать назад кого-то с лампочкой. Этот кто-то ещё вернётся.

Он перенесёт лампу и затратит своё время. На возвращение ему понадобится как-минимум своё время.
Итог — пусть назад бежит всегда самый шустрый с правой стороны. Один факториал ушел!

Здравствуйте, sugarde, Вы писали:

S>Он перенесёт лампу и затратит своё время. На возвращение ему понадобится как-минимум своё время.

Это достаточно очевидный факт. То есть всегда существует i такое что все aj (j<=i) возвращаются, а aj (j>i) нет. Вопрос заключается в том, зависит ли это i от N или нет. Если не зависит, то решаем динамикой за O(N*2^i), а если зависит, то надо думать.

Здравствуйте, ghost92, Вы писали:

G>А как разбивать на пары???
G>Может быть более грамотное разбиение(чем банальные пары соседей в отсортированном массиве) приведет к другому выбору.
G>Вообще 2ой случай t1 + t3 можно рассмотреть как отдельный перевод 2 независимых тихоней самым шустрым чуваком.
G>И после этого может быть снова стоит задуматься о новом разбиении на пары.

Маленькая эврика. Динамическое программирование и линейная сложность.

Сперва примем лемму, что общее направление работ — всё-таки в порядке убывания, а не вперемешку.
Действительно, если есть операция "туда t[N-k], t[N]", то предпочтительнее выбрать k=1 — это приведёт как минимум к не худшему состоянию.
Но сейчас я её доказывать не буду, чтоб не закопаться.

Итак.
Имеем операции:
— одноходовку "туда t[1],t[N]; обратно t[1]"
— двухходовку "туда t[1],t[2]; обратно t[1]" + "туда t[N-1],t[N]; обратно t[2]"
— завершающий ход "туда t[1],t[2]" либо "туда t[1],t[3]"
Обозначим их кодами 'mov', 'push'+'pop', 'ret0', 'ret1'.

Программа действий — это строка из команд, вот в такой автоматной грамматике

outside, 'mov'  -> outside
outside, 'push' -> inside
inside,  'mov'  -> inside
inside,  'pop'  -> outside
outside, 'ret0' -> finish
inside,  'ret1' -> finish

Применяя программу к нашему набору t[N],t[N-1],..., в момент, когда на левом берегу остались t[K] и младше, наша программа
— потратила какое-то суммарное время
— находится в одном из двух состояний: либо "вне двухходовки", либо "внутри двухходовки".

Таким образом, для каждого значения K и обоих состояний мы можем найти наилучшее время и соответсвующую наилучшую головную часть программы.
Дальнейшее очевидно
Держим вектор наилучших результатов для текущего K и из него получаем вектор наилучших результатов для K-1.
Начинаем с вектора для N (outside -> T=0,P=''; inside -> T=+oo,P='')
Приходим к вектору для 2 (outside,inside)
И из него приходим к точке (1,finish)

---

Поскольку двухходовки делать вложенными (на нулевом уровне бегают t[1],t[2]; на первом — t[1],t[3]; и т.д.)
то автомат у нас уже получается стековый, а число состояний — до N-2.

А это уже квадратичная сложность.
Но всяко не экспонента.

Здравствуйте, Vintik_69, Вы писали:

V_>Ну, если можно доказать, что туда-сюда ходит все время конечное число человек...

А что тут доказывать? Туда-сюда имеет смысл ходить только двум самым шустрым — любое возвращение более медленного приведёт к увеличению общего времени перехода. Если же есть ещё столь же шустрые как и второй, то они не улучшат результат — поэтому можно считать что возвращаются не более 2 человек.

Здравствуйте, wallaby, Вы писали:

Ясно. Угу. Интуитивно, дошли.

Итого O(n*logn) на сортировку да динамическое программирование:
T[n] = min(t[1] + t[0] + t[n-1] + t[1] + T[n-2], t[n-1] + t[0] + T[n-1])
Как-то так.

Здравствуйте, Cider, Вы писали:

C>Здравствуйте, sugarde, Вы писали:

S>>1. Четыре человека разных лет подошли ночью с лампочкой к мосту.
S>>Мост узкий, т.е. пройти по нему могут не более двух человек с лампой.

C>Опять гора Фудзи

Ага.

ha-кол ha-олам куло гешер зар м'од
ве ha-икар ло ливташед к'лал

Здравствуйте, Кодт, Вы писали:

Интуитивно это понятно, а вот как доказать?
Вообще не понятно может быть иногда выгодно вернуться нескольким шустрикам обратно.
Но похоже жадный алгоритм будет не хуже.
Предлагаю рассмотреть 2 частных случая.
1) 2 мегашустрика со скоростью 0 (ну если необходимо >0, то можно сделать скорость 1/(4N) этого точно хватит на то чтоб покрыть все лишние проходы)
жадный алгоритм доказывается тривиально.
2) 1 мегашустрик со скоростью 0.
тут надо думать.
3) общий случай.
вычитаем из каждого времени прохода время первого.
говорим что проходов по мосту как минимум 2*N — 1. (в жадном алгоритме ровно столько)
мы свели задачу ко 2ому пункту.




К>Здравствуйте, ghost92, Вы писали:

G>>А как разбивать на пары???
G>>Может быть более грамотное разбиение(чем банальные пары соседей в отсортированном массиве) приведет к другому выбору.
G>>Вообще 2ой случай t1 + t3 можно рассмотреть как отдельный перевод 2 независимых тихоней самым шустрым чуваком.
G>>И после этого может быть снова стоит задуматься о новом разбиении на пары.

К>Маленькая эврика. Динамическое программирование и линейная сложность.

К>Сперва примем лемму, что общее направление работ — всё-таки в порядке убывания, а не вперемешку.
К>Действительно, если есть операция "туда t[N-k], t[N]", то предпочтительнее выбрать k=1 — это приведёт как минимум к не худшему состоянию.
К>Но сейчас я её доказывать не буду, чтоб не закопаться.

К>Итак.
К>Имеем операции:
К>- одноходовку "туда t[1],t[N]; обратно t[1]"
К>- двухходовку "туда t[1],t[2]; обратно t[1]" + "туда t[N-1],t[N]; обратно t[2]"
К>- завершающий ход "туда t[1],t[2]" либо "туда t[1],t[3]"
К>Обозначим их кодами 'mov', 'push'+'pop', 'ret0', 'ret1'.

К>Программа действий — это строка из команд, вот в такой автоматной грамматике
К>

К>outside, 'mov'  -> outside
К>outside, 'push' -> inside
К>inside,  'mov'  -> inside
К>inside,  'pop'  -> outside
К>outside, 'ret0' -> finish
К>inside,  'ret1' -> finish
К>

К>Применяя программу к нашему набору t[N],t[N-1],..., в момент, когда на левом берегу остались t[K] и младше, наша программа
К>- потратила какое-то суммарное время
К>- находится в одном из двух состояний: либо "вне двухходовки", либо "внутри двухходовки".

К>Таким образом, для каждого значения K и обоих состояний мы можем найти наилучшее время и соответсвующую наилучшую головную часть программы.
К>Дальнейшее очевидно
К>Держим вектор наилучших результатов для текущего K и из него получаем вектор наилучших результатов для K-1.
К>Начинаем с вектора для N (outside -> T=0,P=''; inside -> T=+oo,P='')
К>Приходим к вектору для 2 (outside,inside)
К>И из него приходим к точке (1,finish)

К>

---

К>Поскольку двухходовки делать вложенными (на нулевом уровне бегают t[1],t[2]; на первом — t[1],t[3]; и т.д.)
К>то автомат у нас уже получается стековый, а число состояний — до N-2.

К>А это уже квадратичная сложность.
К>Но всяко не экспонента.

Здравствуйте, sugarde, Вы писали:

S>1. Четыре человека разных лет подошли ночью с лампочкой к мосту.
S>Мост узкий, т.е. пройти по нему могут не более двух человек с лампой.

S>На прохождение моста каждому из путешественников нужно соотв. 1, 2, 5 и 10 мин. Пара двигается со скоростью более медленного.
S>Как пересечь мост по-быстрее?

Один из вариантов ответов:

http://thedailywtf.com/Articles/Classic-WTF-Job-Interview-20-Now-With-Riddles!.aspx

Здравствуйте, vnp, Вы писали:

vnp>ha-кол ha-олам куло гешер зар м'од
vnp>ве ha-икар ло ливташед к'лал

Я прочел Ваше сообщение три раза, и мой хомячок сломал клетку, отрастил кожистые крылья и сейчас демонически попискивая носится вокруг люстры. Это нормально?

Здравствуйте, ghost92, Вы писали:

G>Предлагаю рассмотреть 2 частных случая.
G>1) 2 мегашустрика со скоростью 0 (ну если необходимо >0, то можно сделать скорость 1/(4N) этого точно хватит на то чтоб покрыть все лишние проходы)
G> жадный алгоритм доказывается тривиально.
G>2) 1 мегашустрик со скоростью 0.
G> тут надо думать.
Угу. Возникают невозможные переходы. Типа, мегашустрик один сбегал на другой берег лампу принес.
В случае с конечным мегашустриком в таких переходах нет смысла.

G>3) общий случай.
G> вычитаем из каждого времени прохода время первого.
G> говорим что проходов по мосту как минимум 2*N — 1. (в жадном алгоритме ровно столько)
G> мы свели задачу ко 2ому пункту.

Кажется, не свели. 1-й не обязан участвовать в каждом переходе.

Здравствуйте, Кодт, Вы писали:

К>Поскольку двухходовки делать вложенными (на нулевом уровне бегают t[1],t[2]; на первом — t[1],t[3]; и т.д.)
К>то автомат у нас уже получается стековый, а число состояний — до N-2.

А вот это уже лишнее.
Действительно,

1,2-> 1<- 1,3-> 1<- Y,Z-> 3<- W,X-> 2<-
можно переставить
1,2-> 1<- Y,Z-> 2<- 1,2-> 1<- W,X-> 2<-
и это будет дешевле.

Здравствуйте, sugarde, Вы писали:

S>Здравствуйте, ghost92, Вы писали:

G>>Предлагаю рассмотреть 2 частных случая.
G>>1) 2 мегашустрика со скоростью 0 (ну если необходимо >0, то можно сделать скорость 1/(4N) этого точно хватит на то чтоб покрыть все лишние проходы)
G>> жадный алгоритм доказывается тривиально.
G>>2) 1 мегашустрик со скоростью 0.
G>> тут надо думать.
S>Угу. Возникают невозможные переходы. Типа, мегашустрик один сбегал на другой берег лампу принес.
S>В случае с конечным мегашустриком в таких переходах нет смысла.
Данный переход и правда невозможен. без лампы за лампой не побежишь
А вообще почему бы ему не побегать туда-сюда несколько раз? Может так быстрее будет.

G>>3) общий случай.
G>> вычитаем из каждого времени прохода время первого.
G>> говорим что проходов по мосту как минимум 2*N — 1. (в жадном алгоритме ровно столько)
G>> мы свели задачу ко 2ому пункту.

S>Кажется, не свели. 1-й не обязан участвовать в каждом переходе.
А вот этого нигде не утверждается. До сих пор остается схема когда 1ый переводит 2ого чтоб затем отправить 2х тормозов, а 2ой вернет лампу.

Общая идея упрощения в том что показать что жадный алгоритм в данных условиях минимален. При таких условиях проще делать какие-либо утверждения а так же модифицировать алгоритм перевода всех на другой берег.

>Здравствуйте, sugarde, Вы писали:

BridgeCrossing