Pull to refresh

Comments 44

В задаче №2 требуется случайно выбрать число из потока, размер которого неизвестен.
Судя по формулировке задачи, наш алгоритм не детерминирован, а может пользоваться генератором случайных чисел.
Тогда, можно предложить такое решение
Занумеруем числа из потока от 1.
У нас есть ячейка, в которой будем хранить кандидата на финальный результат.
При получении очередного n-го числа из потока с вероятностью 1/n заменим число в ячейке на число из потока.

То есть, первое число генератора всегда кладём в ячейку (вероятность замены = 1), второе — с вероятностью 1/2, следующее — с 1/3, и т.д…

Когда поток закончен, результат — число из ячейки.

Формально доказать корректность как-то лень, но на небольших примерах (размер потока 1,2, или 3) вроде получается равномерное распределение.
Теоретическое обоснование
Пусть метод работает для первых n чисел, то есть для каждого из этих чисел вероятность выпадения 1/n.
Добавим следующее (n+1) число по предложенной схеме. Вероятность его выпадения будет 1/(n+1). Вероятность того, что останется предыдущее число — n/(n+1), что по формуле условной вероятности даёт для каждого из предыдущих чисел вероятность (1/n)*(n/(n+1)) = 1/(n+1).
Таким образом индукция работает. Поскольку для первого числа предложенный метод даёт правильную вероятность (1), то и для каждого следующего он будет работать.
Не верно. Если перезаписывать число, то вероятность того, что в ячейке осталось первое число будет 1/(n!) короче, нулевое
Ответ
Вероятность выбора каждого элемента = 1 / (n — i)
Не знаю зачем вообще дополнительная память.

Пример:
10 элементов
Вероятность выбрать первый элемент 1\10 — нормальное распределение
Получаешь следующий элемент и его выбираешь уже с вероятностью 1\9, так как элементов осталось 9


То есть, в каждом выборе гарантируется нормальное разспределение
Откуда у вас взялся факториал?
Первый шаг: вероятность для первого числа 1.
Второй шаг: вероятность записи нового числа 1/2, оставить старое (1-1/2) = 1/2
Третий шаг: (1-1/3) = 2/3
Четвёртый шаг: (1-1/4) = 3/4

(n-1)-й шаг: (1-1/(n-1)) = (n-2)/(n-1)
n-й шаг: (1-1/n) = (n-1)/n
Комбинируя условные вероятности получаем
1 * 1/2 * 2/3 * 3/4… * (n-2)/(n-1) * (n-1)/n = 1/n
Третья задача.

Я буду пользоваться «жадным» алгоритмом, забирая числа от больших к меньшим (чтобы не беспокоиться о Ai+1 на момент рассмотрения Ai).

Пусть у нас есть последовательность: 1 (x5), 2 (x6), 3 (x2), 4.
Стоит ли мне брать четвёрку? Если я её возьму, получу 4, но потеряю две тройки.
Если я не возьму четвёрку, я должен брать 2 тройки (иначе какой смысл отказываться от четвёрки), но беря 2 тройки, я теряю 6 двоек, и т.д. Полный перебор затягивает меня к экспоненциальную яму.

Значит, нужно применить обычное динамическое программирование.

Обозначим S(N) — наибольшая сумма, которую можно взять из последовательности, рассматривая числа не более чем N. Обозначим K(N) — количество чисел «N» в последовательности.

Тогда, если я решил взять число N, то число N-1 мне не доступно, но это не затрагивает все числа меньше N-1: S1(N)=N*K(N) + S(N-2).
А если я решил отказаться от N, то к моей сумме ничего не прибавляется S2(N) = S(N-1).

Поскольку вариантов всего 2, то S(N) = max(S1(N), S2(N)).
Вычислим рекуррентно S(i) от 1 до макс. числа в последовательности, и запомним булевский признак T(N)=true, если S1 > S2 на шаге N (это обозначает, брать число N в ответ или нет).

Печатаем ответ в обратном порядке: перебираем i от максимального N до 1, если T(i) = true, печатаем число i, если T(i) = false, не печатаем.
Понятно, что настоящее решение сложнее. Т.к. если в последовательности есть очень большие числа, то не нужно циклами бегать по не заполненным промежуткам между ними, а длинные последовательности нулей в S(N) не нужно хранить, заменив массив S(N) на словарь. Но это уже детали реализации.
Если бы задачу давали на соревнованиях типа TopCoder, чтобы завалить невнимательных, наверняка были бы тесты и с отрицательными числами (в условии же не сказано, что все числа положительны), которые не надо выбирать, чтобы не ухудшать себе результат :)
Вопрос 1
8 -> 5 (3, 5, 0)
5 -> 3 (3, 2, 3)
3 -> 8 (6, 2, 0)
5 -> 3 (6, 0, 2)
8 -> 5 (1, 5, 2)
5 -> 3 (1, 4, 3)
3 -> 8 (4, 4, 0)

Вопрос 2
Здесь неполное условие. Могут ли люди пересекать мост одновременно во встречном направлении? Если да, то можно уложиться в 15 минут:
A+D переходят в одну сторону (8 минут)
A+C переходят навстречу друг-другу (5 минут)
A+B переходят в одну сторону (2 минуты)

Задача 1
Считаем количество нулей, единиц и двоек, затем выводим нужное количество (сортировка подсчётом).

Задача 3
Начинаем выбирать с максимального значения, таким образом на каждом шаге будет удаляться только max(Ai) и max(Ai)-1, если такое существует.

В задаче 3 неверный перевод и форматирование. Удаляются не «все вхождения элементов на единицу меньше и на единицу больше (Ai-1) и (Ai+1) при их наличии и сам элемент», а по одному вхождению Ai-1 (если такое есть), Ai+1 (если такое есть) и сам элемент Ai.
Удаляются именно значения Ai-1 и Ai+1, а не Ai-1 и Ai+1.
Здесь неполное условие. Могут ли люди пересекать мост одновременно во встречном направлении?

Нет, во встречном направлении не могут, фонарь всего один.
Тогда так
A + B — 2 минуты
A обратно — 1 минута
C + D — 8 минут
B обратно — 2 минуты
A + B — 2 минуты
И как же так получается, что ушли

C + D — 8 минут

а потом

B обратно — 2 минуты

?
Откуда там взялся B, когда туда ушли с фонарём C + D?

Здесь никак не вложится, так как обратное время тоже учитывается, и даже, если всех будет переводить А (ведь обратно фонарь-то всё равно нужно нести и ему быстрее всего идти обратно), то получается так:

A+D=8
A=1 (обратно)
A+C=5
A=1 (обратно)
A+B=2

Итого 8+1+5+1+2=17.
0. Начало, звёздочкой обозначен фонарь
(A, B, C, D, *) == ()
1. Переходят A и B
(C, D) == (A, B, *)
2. A возвращается обратно
(A, C, D, *) == (B)
3. Переходят C и D
(A) == (B, C, D, *)
4. B возвращается обратно
(A, B, *) == (C, D)
5. Переходят A и B
() == (A, B, C, D, *)
Понял, спасибо. Действительно успеют за 15

С фонарем решается без встречного движения.

По задаче 3 — спасибо, замечания приняты.
Первая
8->5 (3, 5, 0)
5->3 (3, 2, 3)
3->8 (6, 2, 0)
5->3 (6, 0, 2)
8->5 (1, 5, 2)
5->3 (1, 4, 3)
3->8 (4, 4, 0)
первая: да, соортировка подсчётом, только считать можно n-1 элементов, то есть 0 и 1 тогда количество 2 знаем потому что знали изначальный размер массива.

вторая: генерируем число 1<=x<= n, если x == 1 то выбираем число из потока, вероятность этого 1/n
вторая: генерируем число 1<=x<= n, если x == 1 то выбираем число из потока, вероятность этого 1/n

А если n заранее не известно?
тогда нельзя. сравни ситуации когда генератор выдаёт n и 2n. Ты получаешь первое число которое надо выбрать с вероятностью 1/n или 1/2n ты не знаешь с какой.
а не, я вру, оказывается можно.
вариант от qw1 работает для любых n.
нагляднее будет вариант от qw1 с деревом вероятностей
значение в ячейке сохраняем с вероятностью (n-1)/n то есть меняем с 1/n
пусть будет поток a,b,c,d
1) кладём a(100%)
2) с вероятностью 50% меняем на b: a (50%), b (50%)
3) с вероятностью 33% меняем значение на с: a (50%*66%), b (50%*66%), с(2 * 50% * 33%) -> a(33%) b
4) с вероятностью 25% меняем значение на d. а будет с веростностью 1/2*2/3*3/4 = 1/4 и т.д
при этом не надо считать дроби.
Изменить с вероятностью n значит что выпадает 1 при равномерном распределении [1..n]
но тогда надо считать n, и у нас, о ужас, будет две переменные заместо одной требуемой для O(1). В одну «ячейку памяти» два значения можно впихнуть написав одно число в 1/2 верхних битах, другое в нижних.
O(1) — это не одна ячейка памяти, это любое фиксированное количество памяти, не зависящее от n.
Ну что же, попробуем (устроится в Google/Microsoft/Etc):

1) Задача Ледяного Бака
Переливаем 5л из 8л бака в 5л бак
Переливаем 3л из 5л бака в 3л бак
Переливаем 3л из 3л бака в 8л бак
Переливаем 2л из 5л бака в 3л бак
Переливаем 5л из 8л бака в 5л бак
Переливаем 1л из 5л бака в 3л бак
Переливаем 3л воды из 3л бака в 8л бак
Собственно задача решена, 4 л в 8л баке и 4л в 5л баке.
А почему вода ледяная, какое отношение к задаче имеет температура жидкости? Риторика.

2) Задача Светильника и Моста
Ответ, да все указанные персоны могут пересечть мост менее чем за 15 минут.
Персоны «A» и «B» пересекают мост совместно за 2 минуты.
Затем, персоны «C» и «D» пересекают мост за 8 минут.
Итого 10 минут на пересечение моста при указанных идеальных условиях.

3) Сортировка массива состоящего из значений 0,1,2.
Возможно, неверно интерпретирована задача или есть более оптимальные методы ее решения, но в общем случае имеет быть следующее решение — выборочная сортировка на языке pascal
for i:= 0 to n-1 do
..for j:= i+1 to n-1 do
....if a[i]>a[j] then swap(a[i],a[j]);


4) Выбрать произвольное/случайное значение из потока используя ограниченное место хранения
Пропуск. Не смог определить искомый результат — «вероятность 1/n».

5) Максимизировать сумму выбранных чисел
Дано объяснение с примерами, но не указан искомый результат?! Либо пропущены данные.

Теперь можно и подсмотреть что у других…
Затем, персоны «C» и «D» пересекают мост за 8 минут.
Итого 10 минут на пересечение моста при указанных идеальных условиях.

C и D падают с моста, поскольку светильник остался на другой стороне.
Тогда ответ мой ответ — Нет.
+8 минут для «A» и «D»
+1 минута возвращение «A»
+5 минут для «A» и «C»
+1 минута возвращение «A»
+2 минуты для «A» и «B»
Итого 17 минут.
Ice Bucket Challenge — это отсылка к соответствующему флешмобу.

Задача с мостом и фонарём вполне решаема, и ответ в ней — «Да».

Сортировку пузырьком здесь не стоит использовать, лучше сортировку подсчётом, так как набор возможных значений заранее известен и ограничен.
Ice Bucket Challenge — это отсылка к соответствующему флешмобу.

Пожалуй. Хорошо, что в форме задачи.
Таких легких задач еще не было.
Вопрос 1. Такие вопросы мы решали в 5 классе.
Вопрос 2. Такой вопрос был мне задан в ЕПАМе. Самые тормознутые должны идти вместе.
Задача 1. Если не применять «избыточную» оптимизацию, то легко решается в 2 прохода, считаем кол-во 0,1,2 и за второй проход расставляем по местам. Но можно решать за 1 проход, но сильно это ничего не ускорит, а вот код окажется намного сложней.
Задача 2. Такая задача была в одной из книг Шилдта. Я её сам не решил. Но ответ знаю.
Задача 3. Если я все правильно понял, то при выборе 3-ки во втором примере мы потеряем всего одну двойку и 1 четверку, а не все двойки. Т.е. удаляются не все элементы равные значению, а только один из них. Если так, что решение — каждый раз выбирать наибольший из оставшихся элементов.
Т.е. удаляются не все элементы равные значению, а только один из них
Удаляются все элементы с соседним значением. В условие задачи внесено изменение:
Нужно удалять элементы со значением (Ai)+1 и (Ai)-1, а не на позиции А(i-1) и А(i+1)
К сожалению, автор поправил русскую часть (которую никто не читает), но не поправил английскую.

Но это можно было сразу понять, разбирая второй пример, в котором есть 3 двойки, и все три ушли в результат.
В английской части как раз и было:
delete one occurrence of Ai-1 (if exists), Ai+1 (if exists) and Ai each from the array.

Хотя вариант с удалением всех вхождений сложнее и интереснее.
Уже поправлено. На sohabr можно посмотреть снепшоты версий этой статьи ))
Да, «one occurrence». У меня неверное решение выше ((
Но можно решать за 1 проход, но сильно это ничего не ускорит, а вот код окажется намного сложней.
Как это, в один проход? Одним циклом, пока читаем вход, сразу выводим результат?
Прошу прощения, что долго не отвечал. Не было времени.
Там конечно получается не чистый 1 проход, скорее полтора прохода.
Чистый 1 проход получился бы если в задаче были только 0 и 1.
public static void sort01(int[] _array){
        int leftIndex =0;
        int rightIndex = _array.length-1;
        while(true){
            while(_array[leftIndex]==0){
                leftIndex++;
            }
            while(_array[rightIndex]==1){
                rightIndex--;
            }
            if(leftIndex>=rightIndex){
                return;
            }
            _array[leftIndex]=0;
            _array[rightIndex]=1;
            leftIndex++;
            rightIndex--;
        }
    }

Правда у такого варианта есть косяк: если массив нулевой длинный, или же если там одни 0 или 1, то выход за пределы массивы. Но это можно пофиксить либо добавив по 1 проверке в цикле, либо добавить (и запомнить) единицу и ноль в массив, а после уже вернуть в начальное значение.
А так 1 проход: каждое значение (индекс) читается не больше 1 раза, и записывается не более 1 раза, за исключение чтения элементов «при встрече» индексов.
Задача с 0,1,2 немного сложнее, но думаю вам самим будет интересно решить её по аналогии.
Задача с 0,1,2 немного сложнее, но думаю вам самим будет интересно решить её по аналогии.
Не вижу аналогии. Здесь есть 2 фиксированные точки — начало массива и конец, откуда растут непрерывные блоки 0 и 1. От какой точки будет расти третий блок, мы не знаем, пока не проведём подсчёт.
Мы имеем 3 указателя. index1 -движение слева направо, index2 -движение справа налево (самый правый элемент, который !=2), index0- самый левый элемент, который не равен 0.
Пример. 0001102122 (жирным выделены указатели)
Смотрим на что указывает указатель index1, в примере это 0.
Если это ноль, то меняем значение index0 и index1 местами, и сдвигаем оба индекса на 1. Резальтат: 0000112122
Если же index1 указывает на 1, то просто сдвигаем его влево на 1, если указывает на 2, то меняем местами значения в ячейках index1 и index2, и уменьшаем index2 на 1.
Вот рабочий код, немного запутанный, после каждого обновления индекса приходится делать проверку, чтобы не выйти за приделы массива.
public static void sort012(int[] _array){
        int index0 = 0;
        int index1 = 0;
        int index2 = _array.length-1;
        int val1 = _array[index1];
        int val2 = _array[index2];
        
        while((val1==0)&&(index1<index2)){
            index1++;
            val1 = _array[index1];
        }
        while((val2==2)&&(index1<index2)){
            index2--;
            val2 = _array[index2];
        }
        index0 = index1;
        if(index1>=index2){
            return;
        }
        // 
        while(true){
            if(val1==0){
                if(index1!=index0){
                    _array[index0] = 0;
                    _array[index1] = 1;
                }
                index0++;
                index1++;
                if(index1>index2){
                    return;
                }
                val1 = _array[index1];
                continue;
            }
            if(val1==2){
                _array[index2] = val1;// =2
                _array[index1] = val2;
                val1 = val2;
                index2--;
                if(index1>index2){
                    return;
                }
                val2 = _array[index2];
                while(val2==2){
                    index2--;
                    if(index1>index2){
                        return;
                    }
                    val2 = _array[index2];
                }
                continue;
            }
            while(val1==1){
                index1++;
                if(index1>index2){
                    return;
                }
                val1 = _array[index1];
            }
        }
    }
    
    public static void main(String[] _a){
        //int[] ar = {0,1,2,0,1,2,0,0,2,2,1,2,0,1,1,0,2,2};
        int[] ar = {2,1,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0};
        sort012(ar);
        for(int i:ar){
            System.out.println(i);
        }
    }

Здесь каждый элемент массива читается 1 раз. Правда каждый элемент массива может быть изменён 2 раза. Поэтому это скорее полтора прохода.
Интересное решение. Если массив уже отсортирован, то алгоритм вообще не делает запись.
А в первой задаче не про принцип «если мы знаем элементы массива, то сортировка нам не нужна»? То есть за один проход мы с помощью трех переменных можем создать сортированный массив, а не сортировать существующий?
Мы можем сортировать его по ходу, двигаясь слева и справа, и проводить сортировку тех элементов, которые были пройдены.
Поэтому сортировать именно существующий массив.
Объясните плиз, про генератор случайных. То ли лыжи не едут, то ли я не понимаю в чём сложность.
буфер?
Есть реальный поток данных. Если он бесконечен, то вероятность выбрать любое из чисел должна быть нулевой. Если он конечен, то у него есть длина n. Если она меньше нашего объёма буфера, то возвращаем из генератора число от 1 до n с равной вероятностью. Если больше — то возвращаем случайный момент времени из диапазона когда велась трансляция, и ровно в этот момент хватаем последнее попавшее в буфер число. Если скорость передачи не фиксирована, то просто знаем сколько раз наполнится буфер, и считаем два числа random%N и N%databuffer. Так как каждое из них независимое, то и вероятность равна для всех.
Всё просто, есть генератор случайных чисел. Длина последовательности (n) заранее неизвестна. Необходимо получить одно случайно выбранное с вероятностью (1/n) число из этой последовательности. При этом можно использовать только фиксированное количество памяти, довыделять память в дальнейшем нельзя. Поскольку генератор случайный, то повторить последовательность тоже нельзя.
Спасибо, понял. Но случай вопиющий (система с ограничениями на память — скорее всего контроллер, и на них я бы ожидал задокументированную длину пакетов со всех сторон...).

Более реальный случай под ту же математическую логику — нужно делать наложенное изображение из нескольких слайдов-слоёв. Слайды загружаются поочерёдно, и неисвестно, сколько их будет всего. Как обеспечить равномерное наложение слоёв?
Only those users with full accounts are able to leave comments. Log in, please.