Имеет ли решение задача?

Примерно так: (C#, не проверялось):

double Min(double[]a,double[]b){
  int len=a.Length;
  int[] c=new int[len];
  for(int i=0;i<len;i++) c[i]=i;
  Array.Sort(c,(p,q)=>(b[p]*a[q]).CompareTo(a[p]*b[q]));

  double s=0;
  foreach(double p in a) s-=p;
  foreach(int ind in c){
    s+=2*a[ind];
    if(s>=0) return b[ind]/a[ind];
  }
  return 0;
}

Имеет ли решение задача?

Во-первых, именно bi/ai — это те точки, в которых k*ai-bi обращается в 0. Во вторых, да — производная на каждом интервале (а не отрезке!) — константа, и эта функция (кусочно-постоянная) не убывает. И при поиске минимума нам нужно просто найти пару соседних интервалов, на левом из которых производная отрицательна, а на правом — положительна. Производная на интервале (ck,ck+1), где ck=bk/ak, равна -sum(i=1..n, ai)+2*sum(i=1..k,ai) — это нетрудно проверить (предполагается, что ck уже отсортированы), так что эту сумму для всех интервалов можно найти за один просмотр. И сумму модулей разностей в этом алгоритме мы вообще никогда не считаем.

Имеет ли решение задача?

Сумма модулей? Конечно, выпуклая (хотя и не строго). Производная неубывает.

Имеет ли решение задача?

DankoUAДаже раскрывать необязательно. Отсортируем пары (bi/ai,ai), возьмем s=-sum(ai), а потом на каждом шаге вычислять s+=2*ak. Как только перейдем через 0 — нашли минимум.

Имеет ли решение задача?

metar, а как Вы собирались справиться за O(log(N)), даже если данные уже подгружены в память. Вам же надо их хотя бы один раз просмотреть? Или нет?

Имеет ли решение задача?

TheHorse, если хотите, можно искать минимум выпуклой функции бинарным поиском. Делается элементарно.

Имеет ли решение задача?

Отсортировали мы bi/ai. А что потом собираетесь делать? ;)

Имеет ли решение задача?

В бинарном поиске минимума сложность будет n*log(1/eps) — для каждой точки нам придется найти сумму n чисел. При переборе точек ai/bi придется потратить n*log(n) на сортировку — и дальше мы справимся за линейное время.

Если n=10^11, то будет сложно их нормально отсортировать. Но, конечно, возможно (например, раскидать в 1000 отсортированных файлов по 10^8 записей, а потом сортировать слиянием).

Интересная задача на логику?

Да. А первое действие — «1. Ставим на ячейку 1.». Вот 0 и превратился в 1.

Интересная задача на логику?

А доказать, что неразрешима, можете? ;)

Интересная задача на логику?

[+]+>[+]<[>+>+[+>+]+[+<+]<]
Интересно…

Интересная задача на логику?

Первое действие забыли :)
1) _11111
A=2
4) 10_011
5) _10011
A=4
4) 1000_1
5) _10000
A=8
4) 000_00
5) _00000
7) _10000 N=5

Интересная задача на логику?

У Вас _ стоит перед ячейкой, на которой находится каретка? Тогда
4. 10_01
— у меня написано "после каждого шага записываем в ячейку 0."

Есть ли что-то быстрее BK-Tree?

Удачи! Она очень пригодится :)

Есть ли что-то быстрее BK-Tree?

Соптимизировал вычисление расстояния между масками — скорость возросла до 0.057 сек/поиск (при D=15).
Программа здесь: astr73.narod.ru/Files/testham.cpp. Правда, она без комментариев. Там функция FillBase как-то заполняет базу (параметры — число масок и расстояние между соседними масками), PrepareTree готовит базу к поиску, а Find — ищет соседей данной маски (результат скапливается в массиве Res, nres — число найденных соседей). В примере маски для поиска берутся из самой базы, но это не обязательно.

Есть ли что-то быстрее BK-Tree?

Когда расстояние между соседними масками увеличилось до 10, то на поиск при D=15 стало тратиться 0.7 сек (и среднее число ответов — 3: сама маска и две соседних).

Есть ли что-то быстрее BK-Tree?

Попробовал реализовать на массивах на C. Получилось примерно 0.25 сек на поиск для D=15 (среднее число ответов — около 60000, поскольку множество масок было линейно связным в Z2^256)

Есть ли что-то быстрее BK-Tree?

Питона я, к сожалению, не знаю. На псевдо-C++ основной класс и функция поиска могли бы выглядеть так (пример упрощенный, для 32-битных масок. И не проверялся):

struct tree{
  int mbit,cmask,cbits;
  tree *z0,*z1;

  void find(int targ,int dist,ResAcc &res){
      if(dist<0) return;
      int d=hamdist(targ&cmask,cbits&cmask);
      if(d>dist) return;
      if(cmask==-1){ res.Add(cbits); return; }
      int h=(targ&mbit) ? 1 : 0;
      z0->find(targ&~mbit,dist-h,res);
      z1->find(targ|mbit,dist-1+h,res);
  }
}

Здесь mbit — маска бита, по которому происходит ветвление в данном узле дерева, cmask — маска битов, которые в данный момент одинаковы во всем поддереве, начинающемся с этого узла, а cbits — значения этих одинаковых битов. z0 — поддерево, для всех элементов которого бит mbit равен 0, а z1 — поддерево элементов, для которых он равен 1. Листья характеризуются тем, что в них cmask=-1, а z0=z1=NULL (в остальных узлах обе ссылки z0,z1 ненулевые). Значение, лежащее в листе — cbits.
К сожалению, эта структура тратит в 4-6 раз больше памяти, чем просто список масок. И понятно, что для длинных масок ее можно улучшить: хранить бит как индекс в массиве+маску в элементе массива, а расстояние считать тоже с учетом маски, не выполняя предварительно «and».
Как-то так. Дальше надо уже экспериментировать.

Есть ли что-то быстрее BK-Tree?

еще в узле можно хранить маску битов, которая в данный момент общая для всех данных в этом поддереве. Позволит быстро отсекать совсем неправильные пути.

Эффективная передача кодов Хаффмана?

Чтобы глубина равнялась N-1, нужно, чтобы частота одного из символов была не больше phi^(-N), т.е. 1 символ на 10^200000. Я верю, что когда-нибудь мы будем работать с такими объемами информации — но когда?
И «Нужно передавать именно Хаффмановские коды» — это ответ не на тот вопрос. Вопрос был: если заданный код — {0,10,11}, а алгоритм будет выдавать {1,00,01}, это будет недопустимо, или можно как-нибудь договориться с генератором кода?