3адача 1

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

Дан еекст, состоящий из N слов, длина которых не превосходит некоторой небольшой константы. Предложите хотя бы два способа вывести частоты вхождения слов в текст за субквадратичноe время, объясните их преимущества и недостатки.
Задача 3

Даны числительные языка хауса:

đari bakwai da hamsin da shidda 756
sitta da đari bakwai da biyar 6705
saba’a da đari biyar da sittin 7560

A. Переведите с хауса: saba’in da biyar, đari shidda da sittin da shidda
B. Запишите на хауса: 67 и 5605
Задача 4

Есть генератор случайных чисел, который с равной вероятностью генерирует дискретные значения 1, 2, 3, 4 и 5. Как, имея этот генератор, получить генератор, который бы равновероятно выдавал дискретные значения 1, 2, 3, 4, 5, 6 и 7?

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

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

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

L>Задача 2
L>Дан текст, состоящий из N слов, длина которых не превосходит некоторой небольшой константы. Предложите хотя бы два способа вывести частоты вхождения слов в текст за субквадратичноe время, объясните их преимущества и недостатки.

Не, ну это предмет для собеседования. Предложите, объясните...

L>Задача 3
L>Даны числительные языка хауса:

Старое доброе датское "семь плюс полпятого двадцатижды" syvoghalvfems
Нужно покумекать, спасибо.

L>Задача 4
L>Есть генератор случайных чисел, который с равной вероятностью генерирует дискретные значения 1, 2, 3, 4 и 5. Как, имея этот генератор, получить генератор, который бы равновероятно выдавал дискретные значения 1, 2, 3, 4, 5, 6 и 7?

Легко! Чем будем жертвовать — гарантией остановки или автокорреляцией?

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


К>Легко! Чем будем жертвовать — гарантией остановки или автокорреляцией?
? По-моему тут вообще все задачи на "умеет ли человек не паниковать на собеседованиях", особенно последняя. 1..5 -> 0..4 -> base 5 -> base 25 -> отбрасываем все > 7. Для эстетов — все > 21 и отдаём остаток от деления на 7.

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

К>>Легко! Чем будем жертвовать — гарантией остановки или автокорреляцией?
S>? По-моему тут вообще все задачи на "умеет ли человек не паниковать на собеседованиях", особенно последняя. 1..5 -> 0..4 -> base 5 -> base 25 -> отбрасываем все > 7. Для эстетов — все > 21 и отдаём остаток от деления на 7.

То есть, пожертвовали остановкой. Мы ведь можем до морковкиного заговенья ждать, пока перестанет выпадать >21 из 25. Хотя вероятность этого невезения мала.
А настоящие эстеты не выкидывают >21, а используют.

m = 1 # верхняя граница случайного числа
r = 0 # само число
while True:
  m = m*5
  r = r*5 + rand5()
  s = m - m%7 # верхняя граница, при которой можно дать ответ сейчас (кратна 7)
  if r < s:
    return r%7
  m -= s
  r -= s

Получаем последовательность
0 из 5 — перенесли 5 — на этом шаге гарантированно ничего не смогли выдать
21 из 25 — перенесли 4
14 из 20 — перенесли 6
28 из 30 — перенесли 2
7 из 10 — перенесли 3
14 из 15 — перенесли 1
0 из 5 — перенесли 5, ну и так далее

По сути, это арифметическое кодирование...

А жертва автокорреляцией — это запустить генератор псевдослучайных чисел (пусть даже самый тупой) и смешать его с источником 5-ричных случайных чисел.

int dummy_pseudorand7() { static int seed = 0; return (seed += 1 %= 7); }
int smart_pseudorand7() { return rand() * 7 / RAND_MAX; }

int true_rand5();

int truly_rand7() { return (some_pseudorand7() + true_rand5()) % 7; }

dummy_pseudorand7 — даёт равномерные случайные числа, но с люто бешеной автокорреляцией.
Но если true_rand5 обеспечивает белый шум, то это будет не так заметно.
xkcd-генератор "return 4" не подойдёт, потому что он заведомо неравномерный.
А вот обычный сишный rand может сгодиться. (Конечно, он будет чуточку неравномерным, поэтому рожаем свой ГПСЧ по модулю 7).

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

К>А настоящие эстеты не выкидывают >21, а используют.

К>m = 1 # верхняя граница случайного числа
К>r = 0 # само число

К>По сути, это арифметическое кодирование...

Не знаю как там у "эстетов" принято делать, но в арифметическом кодировании ещё и энтропию между вызовами не теряют. Слишком это расточительно инициализировать старт каждый раз парой {1, 0}. Скажем, очевидно, что если нужно смоделировать честную монету, то имея генератор rand8, запускать последний можно лишь один раз на три ответа:

// s = 5, d = 7
template <ui s, ui d> 
ui gen() {
  static ui g = 1, v = 0;
  do {
    while (g < d) {
      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);
}

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

L>3адача 1

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


А на вход что дается?

Здравствуйте, Кодт, Вы писали:
К>То есть, пожертвовали остановкой. Мы ведь можем до морковкиного заговенья ждать, пока перестанет выпадать >21 из 25. Хотя вероятность этого невезения мала.
К>А настоящие эстеты не выкидывают >21, а используют.

А, так вопросы не прикладные, а на сферическую модель коня в вакууме (в хорошем смысле)? Тогда пас, мозги безнадёжно испорчены практикой

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

L>>3адача 1

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

N>А на вход что дается?

На входе массив целых чисел, на выходе m и k.

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

L>Задача 3

L>Даны числительные языка хауса:

L>đari bakwai da hamsin da shidda 756
L>sitta da đari bakwai da biyar 6705
L>saba’a da đari biyar da sittin 7560

L>A. Переведите с хауса: saba’in da biyar, đari shidda da sittin da shidda
L>B. Запишите на хауса: 67 и 5605

Что-то у меня с бакваем проблемы. đari bakwai это 700, но 7000 это почему-то saba’a. Остальное вроде сходится.

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

чтобы сумма a[m] + a[m + 1] + ... + a[k] была максимальна

Так получается мне можно брать всесь массив, что ли?

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

К>Легко! Чем будем жертвовать — гарантией остановки или автокорреляцией?
Чем плох наивный вариант бросить 7 раз по 5, и растащить 5 раз по 7?

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

N>Так получается мне можно брать всесь массив, что ли?

В задании говорится о целых числах, а о не натуральных. В терминах С/С++ это signed int числа, а не unsigned int

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

N>чтобы сумма a[m] + a[m + 1] + ... + a[k] была максимальна

N>Так получается мне можно брать всесь массив, что ли?

Можно, но числа могут быть отрицательными, поэтому это не обязательно правильный ответ.

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

Ясно, спасибо.

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

К>>Легко! Чем будем жертвовать — гарантией остановки или автокорреляцией?
B>Чем плох наивный вариант бросить 7 раз по 5, и растащить 5 раз по 7?

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

Они должны обязательно идти подряд?

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

N>Они должны обязательно идти подряд?

Да, иначе какой был бы смысл в этой задаче.

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

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

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

Количество проходов по массиву является спойлером.
Подсказка: какое именно количество я имел в виду?
Подсказка 2: нет, не NP-полная задача.

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

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

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