Re[6]: Зaдачи от компании АBBYY
От: Erop Россия  
Дата: 09.04.16 20:13
Оценка: +1 :)
Здравствуйте, Кодт, Вы писали:

К>Подсказка 2:

Почему не 1?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[7]: Зaдачи от компании АBBYY
От: andyp  
Дата: 09.04.16 20:27
Оценка:
Здравствуйте, Erop, Вы писали:

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


К>>Подсказка 2:

E>Почему не 1?

Согдасен. Сумма идущих подряд эл-тов массива получается добавлением нового эл-та и вычитанием самого старого.
Re[7]: Зaдачи от компании АBBYY
От: watchmaker  
Дата: 09.04.16 21:00
Оценка: :)
Здравствуйте, Erop, Вы писали:


К>>Подсказка 2:

E>Почему не 1?

Действительно. Это форум программистов или кого? Согласен, что должно быть 1 и что список нужно нумеровать с нуля! Вот так:

Подсказка 0: ...
Подсказка 1: ...

Re: Зaдачи от компании АBBYY
От: Iso12  
Дата: 09.04.16 21:47
Оценка:
Здравствуйте, Lepsik, Вы писали:

Задачи в основном на знание алгоритмов

L>3адача 1


L>Дан массив из целых чиcел. Найти такие m <= k, чтобы сумма a[m] + a[m + 1] + ... + a[k] была максимальна. Время работы должно быть порядка длины массива.


Здесь нужно знание sweep algorithms, конкретно Kadane's algorithm


L>Задача 3

L>A. Переведите с хауса: saba’in da biyar, đari shidda da sittin da shidda
saba’in da biyar: 76
đari shidda da sittin da shidda: 666

L>B. Запишите на хауса: 67 и 5605

67: sitin da bakwai
5605: hamsa da dari shidda da bigar

Над 2 и 4 надо подумать
Re[6]: Зaдачи от компании АBBYY
От: bazis1 Канада  
Дата: 09.04.16 23:20
Оценка: :)
Здравствуйте, Erop, Вы писали:

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


B>>если все числа неотрицательные, то можно. в общем случае это подозрительно начинает напоминать scheduling, который NP-полный. конкретно здесь лень проверять, но, ИХМО, это любимое занятие рекрутеров — подсунуть замаскированную NP-полную задачу и с невинными глазами просить найти оптимальное решение за полиноминальное время.


E>Задача очевидно линейная...

линейная, если над ней думать на первый взгляд видишь плавающий score с локальным максимумом, который не всегда равен глобальному и думаешь "опять scheduling?".
Re[6]: Зaдачи от компании АBBYY
От: bazis1 Канада  
Дата: 09.04.16 23:29
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Количество проходов по массиву является спойлером.

К>Подсказка: какое именно количество я имел в виду?
один на подсчет левых полусумм, один на подсчет правых?
К>Подсказка 2: нет, не NP-полная задача.
А, ну да. Ладно, хорошая задача.
Re[4]: Зaдачи от компании АBBYY
От: bazis1 Канада  
Дата: 09.04.16 23:33
Оценка:
Здравствуйте, vsb, Вы писали:

vsb>Я ничего не понял, подробней можно? Что значит растащить 5 раз по 7? Лучше конкретным кодом или на примере. Выпало 1 2 3 4 5 4 3, дальше что будете делать?

а, нет, меня проглючило. наивный вариант плох тем, что не будет работать .
Re[2]: Зaдачи от компании АBBYY
От: bazis1 Канада  
Дата: 10.04.16 01:31
Оценка:
Здравствуйте, Iso12, Вы писали:

L>>Дан массив из целых чиcел. Найти такие m <= k, чтобы сумма a[m] + a[m + 1] + ... + a[k] была максимальна. Время работы должно быть порядка длины массива.

I>Здесь нужно знание sweep algorithms, конкретно Kadane's algorithm
ну это выводится за пару часов в фоновом режиме при желании. я вот сначала подумал, что это NP, но потом задача засела в подсознании и постоянно выкидывала идеи, пока я вокруг горного озера с рюкзаком лазил. А что если начать с крупнейшего элемента? Нет, фигня. А что если предположить, что известен элемент, гарантированно включенный в результат? Ага, линейно сканируем влево и вправо. А можно ли как-то останавливать сканирование зараннее? Можно, если следующий элемент сумму уменьшит, и последующие за ним ее не вернут. А как это просто определить? Сканированием с другого конца и сбросом при получении отрицательной суммы. Бинго, проблема решена.

Но какой великий смысл спрашивать это на интервью, мне неведомо. ИМХО, единственное, что можно таким способом выявить, это то, что человек перед собеседованием потратил неделю на кэширование в голове основных алгоритмов, которые еще через неделю забудет.
Re[7]: Зaдачи от компании АBBYY
От: Кодт Россия  
Дата: 10.04.16 08:43
Оценка:
Здравствуйте, Erop, Вы писали:

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


К>>Подсказка 2:

E>Почему не 1?

Подсказка номер два, потому что подсказка номер один была "задуматься о количестве проходов вообще".
А эта подсказка даёт ограничение сверху: "меньше expN/N проходов"
Впрочем, тут уже выкатили спойлер — статью в вике.
Перекуём баги на фичи!
Re[3]: Зaдачи от компании АBBYY
От: Iso12  
Дата: 10.04.16 08:43
Оценка:
Здравствуйте, bazis1, Вы писали:


B>Но какой великий смысл спрашивать это на интервью, мне неведомо. ИМХО, единственное, что можно таким способом выявить, это то, что человек перед собеседованием потратил неделю на кэширование в голове основных алгоритмов, которые еще через неделю забудет.


Мне тоже не совсем понятно зачем на интервью это спрашивать, может быть ишут человека для разработки в области ИИ. Чтобы понять может человек думать или нет есть и другие способы.
Отредактировано 10.04.2016 9:12 Iso12 . Предыдущая версия .
Re[8]: Зaдачи от компании АBBYY
От: andyp  
Дата: 10.04.16 09:50
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Подсказка номер два, потому что подсказка номер один была "задуматься о количестве проходов вообще".

К>А эта подсказка даёт ограничение сверху: "меньше expN/N проходов"
К>Впрочем, тут уже выкатили спойлер — статью в вике.

Тоже понял так, что проходов требуется 2, а не подсказка номер 2.
Re[3]: Зaдачи от компании АBBYY
От: Erop Россия  
Дата: 10.04.16 18:43
Оценка:
Здравствуйте, bazis1, Вы писали:

B>ну это выводится за пару часов в фоновом режиме при желании. я вот сначала подумал, что это NP, но потом задача засела в подсознании и постоянно выкидывала идеи, пока я вокруг горного озера с рюкзаком лазил. А что если начать с крупнейшего элемента? Нет, фигня. А что если предположить, что известен элемент, гарантированно включенный в результат? Ага, линейно сканируем влево и вправо. А можно ли как-то останавливать сканирование зараннее? Можно, если следующий элемент сумму уменьшит, и последующие за ним ее не вернут. А как это просто определить? Сканированием с другого конца и сбросом при получении отрицательной суммы. Бинго, проблема решена.


Ну можно проще, как бы...
Как бы очевидный подход в такого рода задачах -- динамическое программирование.
Ну типа заводим состояния { текущая позиция, откуда надо начать, что бы к текущей позиции иметь максимальную сумму, ну и сама сумма по идее пригодится.}
Ну, как бы в начале имеем {0, 0, 0}

Как сделать шаг? Ну, как бы из {pos, curPosStart, curSumm} переходим или в {pos+1, curPosStart, curSumm + v[pos]} или в {pos + 1, pos +1, 0 } в зависимости от знака curSumm + v[pos]}.

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

B>Но какой великий смысл спрашивать это на интервью, мне неведомо. ИМХО, единственное, что можно таким способом выявить, это то, что человек перед собеседованием потратил неделю на кэширование в голове основных алгоритмов, которые еще через неделю забудет.

Ну алгоритмистов ищут, видимо...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[4]: Зaдачи от компании АBBYY
От: Erop Россия  
Дата: 10.04.16 18:49
Оценка:
Здравствуйте, Iso12, Вы писали:

I>Мне тоже не совсем понятно зачем на интервью это спрашивать, может быть ишут человека для разработки в области ИИ. Чтобы понять может человек думать или нет есть и другие способы.


А это интервью или письменный тест?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[5]: Зaдачи от компании АBBYY
От: Iso12  
Дата: 10.04.16 20:53
Оценка: +1
Здравствуйте, Erop, Вы писали:

E>А это интервью или письменный тест?


Без понятия. Наверное Lepsik сможет ответить на этот вопрос.
Re[5]: Зaдачи от компании АBBYY
От: Кодт Россия  
Дата: 11.04.16 11:54
Оценка:
Здравствуйте, watchmaker, Вы писали:

W>Не знаю как там у "эстетов" принято делать, но в арифметическом кодировании ещё и энтропию между вызовами не теряют.


А ты мелочный скрупулёзный!
Перекуём баги на фичи!
Re[5]: Зaдачи от компании АBBYY
От: Кодт Россия  
Дата: 11.04.16 12:27
Оценка:
Здравствуйте, watchmaker, Вы писали:

<>
На питоне это выглядит так
def randgen(N,K,randK):
  ''' N - целевая граница, K - исходная, randK - исходная функция ГСЧ [0..K) '''
  r, m = 0, 1
  while True:
    while m < N or r >= m//N*N:
      r, m = r*K + randK(), m*K
    yield r%N
    r, m = r//N, m//N

def randgen(N,N,randKgen):
  ''' randKgen - исходная последовательность (генератор) ГСЧ '''
  r, m = 0, 1
  for rk in randKgen:
    r, m = r*k + rk, m*k
    while r < m//N*N:
      yield r%N
      r, m = r//N, m//N

Как это похоже на разложение k-ричного числа в n-ричную систему!
Перекуём баги на фичи!
Re[6]: Зaдачи от компании АBBYY
От: watchmaker  
Дата: 11.04.16 12:49
Оценка: 25 (2)
Здравствуйте, Кодт, Вы писали:

К>А ты мелочный


Можно лучше.

В предыдущем сообщении написано, конечно, не само арифметическое кодирование, а пример, как можно не терять энтропию в обоих ветках (в неудачной, когда нельзя дать ответ, и в удачной, когда ответ дать можно). Арифметическое же кодирование пишется сложно и, вообще говоря, требует арифметики всё более растущей точности. На практике так конечно никто не делает, а всякие компрессоры просто принимают решение периодически (в заранее оговорённых местах) округлять числа. Для сжатия это не критично — снижается лишь его качество, но не теряется возможность распаковки. Для конвертации вероятностей такой подход плох тем, что даёт неравномерное распределение (хотя понятно, что на практике даже без всякой хитрой длинной арифметики эту неравномерность можно легко сделать порядка 2-60 , то есть практически незаметной). Либо можно в случае обнаружения такой ситуации опять же перебрасывать и начинать всё с начала — равномерность будет, а ухудшится утилизация энтропии (будем делать больше вызовов rand чем необходимо).

Короче говоря, если нужно получить много чисел, то оказывается такой кодер написать очень легко, модифицировав в предыдущем исходнике буквально пару строчек:
using ui = uint64_t;

// s = 5, d = 7
template <ui s, ui d> 
ui gen() {
  static ui g = 1, v = 0;
  constexpr ui max = std::numeric_limits<ui>::max() / s; 
  do {
    while (g <= max) {
      g *= s;
      v = v * s + random<s>();
    };
    ui f = g / d * d;
    if (v < f) {
      ui r = v % d;
      g /= d;
      v /= d;
      return r;
    }
    g -= f;
    v -= f;
  } while (1);
}

В качестве расплаты же будет выступать появление лага или задержки: настоящее арифметическое кодирование (как и все остальные идеи в этой ветке) будет стремится дать ответ как можно раньше, то есть как только можно отличить один ответ от другого. Этот же исходник сначала всегда делает несколько "холостых" вызовов random и лишь потом начинает выдавать ответ. Такое накопление энтропии и позволяет сделать ситуацию, когда нужно запускать цикл сначала, очень маловероятной.
При этом эта энтропия не теряется, при желании её можно достать обратно, ценой усложнения кода. То есть если нужно сконвертировать миллион случайных чисел по схеме 5 → 7, то сначала произойдёт 24 вызова random, потом для следующего почти миллиона чисел будет тратится в среднем log57 вызовов random на число, а для последних нескольких чисел вызовов random вообще не будет, так как можно обойтись уже накопленной энтропией в счётчиках, то есть можно не делать как раз посление 24 вызова random, которые уже были сделаны в начале.

Точные значения считать лень (они просто считаются только для первых двух алгоритмов), поэтому просто запустил несколько экспериментов по генерации 108 случайных чисел:
трансформация алгоритм → переброс
Автор: Sinix
Дата: 08.04.16
запоминание неудачи
Автор: Кодт
Дата: 09.04.16
запоминание успеха
Автор: watchmaker
Дата: 09.04.16
накопление энтропии (это сообщение) арифметическое кодирование (теоритический минимум)
8 → 2 вызовов на ответ 1.00000 1.00000 0.33333 0.33333 0.33333
лишние вызовы +200.000% +200.000% +0.000% +0.000% +0.000%
задержка 0 0 0 20
5 → 7 вызовов на ответ 2.38086 2.21235 1.54579 1.20906 1.20906
лишние вызовы +96.918% +82.981% +27.850% +0.000% +0.000%
задержка 0 0 0 24
7 → 5 вызовов на ответ 1.39989 1.37666 1.15922 0.82709 0.82709
лишние вызовы +69.255% +66.446% +40.157% +0.000% +0.000%
задержка 0 0 1 21
3 → 14 вызовов на ответ 5.78528 3.64286 3.23388 2.40217 2.40217
лишние вызовы +140.835% +51.648% +34.623% +0.000% +0.000%
задержка 0 0 3 33
14 → 3 вызовов на ответ 1.16664 1.14884 0.59734 0.41629 0.41629
лишние вызовы +180.247% +175.970% +43.490% +0.000% +0.000%
задержка 0 0 0 15
3 → 2 вызовов на ответ 1.50010 1.49976 1.50003 0.63093 0.63093
лишние вызовы +137.759% +137.706% +137.749% +0.000% +0.000%
задержка 0 0 0 39
2 → 3 вызовов на ответ 2.66673 2.66664 2.66658 1.58496 1.58496
лишние вызовы +68.252% +68.246% +68.242% +0.000% +0.000%
задержка 0 0 0 59
14 → 15 вызовов на ответ 2.01024 2.01026 1.14870 1.02614 1.02614
лишние вызовы +95.903% +95.904% +11.943% +0.000% +0.000%
задержка 0 0 0 13
15 → 14 вызовов на ответ 1.07142 1.07142 1.07140 0.97452 0.97452
лишние вызовы +9.944% +9.943% +9.941% +0.000% +0.000%
задержка 1 0 0 14
В общем видно, что при преобразовании 5 → 7, если следовать стратегии "бросить 2 раза, если получилось больше 21, то перебросить", получается 97% лишних вызовов по сравнению с оптимальной стратегией, где вызовов требутеся log57. Если добавить оптимизацию Кодта, то число лишних вызовов снизится до 83%. Если запоминать ещё и значение переменных между вызовами, то уже получается 28% потерь. Если же предварительно накопить энтропию, то лишних вызовов не будет вовсе — цикл do while ни разу не выполнился дважды, а потери на округлении перед return также ни разу не проявили себя — так бывает не всегда, с сумме там получается не ноль. Но, если я верно прикинул, то вероятность, что нам потребуется больше вызовов random чем арифметическому кодированию, для 108 вызовов составит примерно 7*10-11.
Re[6]: Зaдачи от компании АBBYY
От: watchmaker  
Дата: 11.04.16 13:28
Оценка:
Здравствуйте, Кодт, Вы писали:

К>На питоне это выглядит так

К>def randgen(N,K,randK):
К>  ''' N - целевая граница, K - исходная, randK - исходная функция ГСЧ [0..K) '''
К>  r, m = 0, 1
К>  while True:
К>    while m < N or r >= m//N*N:
К>      r, m = r*K + randK(), m*K
К>    yield r%N
К>    r, m = r//N, m//N

Меня в этом коде смущает две вещи:
При N=7, K=5 и 105 итераций значение 6 выпадает в 3.7 раза чаще чем значение 0.
Значение r неограниченно растёт и начиная с некоторого момента начинает не хватать производительности при оперировании числами длиной в тысячи цифр.
Re[7]: Зaдачи от компании АBBYY
От: Кодт Россия  
Дата: 11.04.16 15:21
Оценка:
Здравствуйте, watchmaker, Вы писали:

W>Меня в этом коде смущает две вещи:

W>При N=7, K=5 и 105 итераций значение 6 выпадает в 3.7 раза чаще чем значение 0.

Упс!

Забыл вычитать делящуюся нацело часть
import random

def randKgen(K):
  assert K > 0
  while True:
    yield random.randint(0,K-1)

def randNKgen(N, K, gen = None):
  assert N > 0
  assert K > 0
  if gen is None:
    gen = randKgen(K)
  r, m = 0, 1
  for q in gen:
    while m >= N:
      s = m//N*N
      if r < s:
        yield r%N
        r, m = r//N, m//N
      else:
        r, m = r-s, m-s  # вот это забыл сделать
    r, m = r*K + q, m*K


В таком исполнении — получилось равномерно.
Перекуём баги на фичи!
Отредактировано 11.04.2016 15:39 Кодт . Предыдущая версия .
Re[7]: Зaдачи от компании АBBYY
От: Кодт Россия  
Дата: 11.04.16 15:27
Оценка: +1
Здравствуйте, watchmaker, Вы писали:

К>>А ты мелочный

W>Можно лучше.

Так и представляется картина: учёные мужи начинают расковыривать энтропию, вычислять теоретические оценки, рядом вьётся безутешный рекрутер, а ему (тем более, ей) машут рукой и говорят "уйди не мешай мальчик (девочка)".
Перекуём баги на фичи!
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.