P(max(a, b) < x) = P( a < x && b < x) = P(a < x) * P(b < x) = x^2

у нас 3 варианта - 2 слева, 2 справа и по одному там и там. по Гауссу хотел бы рассчитать вероятности этих событий и кинуть монетку

Отмасштабировав правильно такое распределение на целые числа легко выбрать сначала максимум, а потом второе число от нуля до первого

Теперь представим, что k - нечётное?

а какая разница?

Тогда мат-ожидание середины равномерно

не вижу чем это поможет. нам не матожидание нужно а генерировать испытания каждый раз с неравномерным исходом

Выбираем середину, потом выбираем рекурсивно k/2 чисел справа, k/ 2 слева

и получаем равномерную сетку - ок )

ее я могу и проще через шаг получить )

не вижу чем это поможет. нам не матожидание нужно а генерировать испытания каждый раз с неравномерным исходом

Не понял, какой случай вам не понятен.

нечетность к чем так выделяется?

не вижу чем это поможет. нам не матожидание нужно а генерировать испытания каждый раз с неравномерным исходом

Как выбрать k = 2?

кинуть монетку и выбрать - что выпадет

кинуть монетку и выбрать - что выпадет

Тогда придётся запоминать все предыдущие

И делать специальный мэппинг с пропусками

Если k - очень большое

ещё есть странный вариант, просто вызывать random shuffle на вершинах

К с правильным алгоритмом можно помнить только логарифм и никаких пропусков учитывать не нужно

при любом к не придется ничего запоминать - алгоритм волшебен, только Гаусса прикрутить

шаффл интересная идея...

ещё есть странный вариант, просто вызывать random shuffle на вершинах

А что даст?

не знаю, думаю пока что

Придумал отличный рекурсивный алгоритм. Нам надо придумать набор N рёбер из K возможных. Они у нас как-то занумерованы и задача сводится к генерации битвектора дл ины K с N единицами У нас равнораспределение, потому первый элемент 1 с вероятностью K/N. 1. Выбираем его случайно 2. Если он 1 задача сводится к (K-1,N-1), иначе (K,N-1)

Нужно сгенерировать N случайных чисел, где N —число рёбер

щас скопипасчу пока не уехало и почитаю вдумчиво…

А алгоритм @IIvana я так и не понял

Как выбрать миллион гарантированно разных целых чисел в диапазоне от 0 до C(5000,2500), не запоминая ничего на каждом шаге

ну с этого начинается все

:(

Увидел "если будет много офытопа -- отправлю в блах" и 150 непрочитанных сообщений

ну или запоминая минимум

тут почти спец олимпиадка!

я так понял идея такая - разбиваем отрезок на 2, выбираем сколько элементов попало в первую половину

рекурсивно продолжаем

тогда нам нужно помнить log(N*M/2) чисел (сколько точек в соотв отрезке)

А. Я неправильно понял алгоритм

ну или побить на большее число отрезков, тогда вообще помнить 1 число придётся

Тогда да - ок

я так понял решение @IIvana

т.е. вопрос в том как эффективно выбирать это самое число только

я так понял идея такая - разбиваем отрезок на 2, выбираем сколько элементов попало в первую половину

Так понял, но это как-то неэкономично. И считать надо всякие сложные вещи. В моем алгоритме надо понить два числа

т.е. вопрос в том как эффективно выбирать это самое число только

Просто пополам

и держать битвектор

я вроде это сначала предлагал

правда по глупости предложил перебросить кубик если попали на выбранное

но это не обязательно

Битвектор материализовывать необязательно.

ну список выбранных ответов помнить надо?

ну список выбранных ответов помнить надо?

Нет

или фунцию преобразования

а как тогда?

Придумал отличный рекурсивный алгоритм. Нам надо придумать набор N рёбер из K возможных. Они у нас как-то занумерованы и задача сводится к генерации битвектора дл ины K с N единицами У нас равнораспределение, потому первый элемент 1 с вероятностью K/N. 1. Выбираем его случайно 2. Если он 1 задача сводится к (K-1,N-1), иначе (K,N-1)

я про ^

у меня ничего помнить не надо! у меня патологическая рекурсивная сортировка сама все помнит на стеке

стек == помнить

Можно сразу употреблять. Но есть граф сильно разряженный, то алгоритм будет неэкномичный. Он O(число возможных ребёр)

я правильно понял твое решение, кстати?

посчитай глубину стека для числа ребер 1000000 - мизер ) да, решение понял правильно

вся соль - разбить число не пополам а отрезок пополам

а понял

все мой комментарий снят

ну список выбранных ответов помнить надо?

Есть есть хорошее упорядочивание, то необязательно

проходим по всем и выбираем его с вероятностью k/n

k/n меняется с каждым шагом

потом меняем вероятность в зависимости от результата

угу

а как тогда?

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

а вот это я уже не понимаю (

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

мы кажется разные вещи обсуждали

не прямо выше а до этого -0 алгоритм Александра и Алексея

просто Алексея, я не решился предлагать этот алгоритм, хотя и думал о нём

смотри

берёшь первый элемент

какая вероятность того, что он в списке?

0

это конкретное ребро

в списке выбранных?

какая вероятность, что ребро (1,2) у тебя выбрано если всего у тебя N вершин, и из них выбрано K?

к/n

вот

бросаешь кубик, и узнаешь входит ли оно

или нет? )

верно

Спокой ночи

после этого у тебя 2 варианта

бросаешь кубик, и узнаешь входит ли оно

Тогда нужно запоминать выбранные графы

неа

Алексей - пасиб за биномиальное и Гаусса

у тебя 2 варианта: 1. выбрали, тогда решаешь задачу с (n-1) ребром и нужно выбрать (k-1) 2. не выбрали тогда n'=n-1, k'=k

и идешь по списку дальше

после этого у тебя 2 варианта

Тогда вероятность выбора ребра может отличаться от k/n

да, она изменяется после каждого выбора

но тогда я могу набросать кубик так, что к концу не наберу мое К

да, она изменяется после каждого выбора

Как её посчитать?

не можешь

или я туплю

Я сделал 1000 графов

если я правильно понимаю то или (k-1)/(n-1). или k/(n-1)

Как мне посчитать вероятность выбора первого ребра для 1001 графа?