Комментарии 72
понравились задачки)
мой вариант
58 s
7
найти самую длинную совпдающую подпоследовательность второго слова в первом и
приписать недостающие буквы с обоих сторон от крайних символов подпоследовавтельности
домножить все числа до самого старшего разряда в наборе. Запомнить кого на сколько помножили. Отсортировать по значению. Делить на запомненные ранее множители
вычесть B\A — по одному выкидывая элементы. Искать совпадения перебором от последнего выкинутого элемента, к примеру. Даст максимально быстрый результат если оба входных массива отсортированы (ну мало ли)
7
найти самую длинную совпдающую подпоследовательность второго слова в первом и
приписать недостающие буквы с обоих сторон от крайних символов подпоследовавтельности
домножить все числа до самого старшего разряда в наборе. Запомнить кого на сколько помножили. Отсортировать по значению. Делить на запомненные ранее множители
вычесть B\A — по одному выкидывая элементы. Искать совпадения перебором от последнего выкинутого элемента, к примеру. Даст максимально быстрый результат если оба входных массива отсортированы (ну мало ли)
Ваше решение 1-задачи вызывает больше вопросов, чем дает ответы. Во-первых, поиск максимальной подпоследовательности — это не тривиальная задача. Даже найдя её, нужно ещё правильно расставить значения по бокам. В -третьих, что будет, если одна и та же максимальная подпоследовательность будет встречаться во втором слове несколько раз?
По описанному вами невозможно определить даже алгоритмическую сложность.
Ваше решение как минимум неполное, как максимум неверное. Неполнота не дают мне возможность построить контрпример.
Пусть есть слово1, слово2. Ищем первую букву слова2 в слове1, после неё — вторую, и так далее. Если доходим до конца — выводим первое слово, оно содержит в себе первое. Нет — ищем второй символ слова2 в слове1, затем все последующие. По ходу держим в памяти номер символа с которого начали, номер символа где нашли его, длину текущего отрезка в символах. Если она становится больше предыдущей — подменяем всю запись условного «рекордсмена». После того как длина слова2 — длина рекорда — номер первого символа рекорда < 0, либо закончились символы в слове2 выполняем процедуру слияния. Все символы до того с которого начата запись рекорда вписываем прямо перед словом1, а всё после (номер+длина) приписываем спереди слова1. Если вдруг встречается несколько раз, то значит всё равно какую выбрать — длина конечного суперслова не изменится. А так как определить заранее что там дальше в слове содерится мы не можем, то всё равно придётся идти до последней самой длинной последовательности. По ней и будем резать слово2 в таком алгоритме. В худшем случае будет так: кошка + мегера = мегеркошка, отработка за m*n*(n-1)/2, где m и n длины слов. В таком случае лучше всего изначально поменять порядок, так чтобы слово1 было длиннее слова2.
Могу я попросить вас разобрать обработку 2-х слов?
Пожалуйста, распишите, что будет после каждого этапа вашего алгоритма при обработке слов ABCE и ACDE, получится ли в итоге слово ABCDE?
Пожалуйста, распишите, что будет после каждого этапа вашего алгоритма при обработке слов ABCE и ACDE, получится ли в итоге слово ABCDE?
Нет. Я не поумал про случай, когда в середине лишняя буква. Тогда надо ещё метки ставить не только где начало подпоследовательности, но и на каждом разрыве.
тогда будет такое: A нашлось, ищет совпадения дальше, до C, потом D не находит и оставляет метку конца, находит E, и вставляет метку начала, потом доходит до конца строки и видит что совпадений 3. Дальше даже не пытается начать поиск с B, поскольку это третий символ с конца слова1, больше чем 3 символа уже никак не получится, значит мы пришли к максимуму. Вызывается слово1, в нём метки указывают что между найденными соответсвующими C и E надо вставить кусок слова2 между метками слова2 (а там D). В итоге будет такое слово. Только надо метки писать — куда какой номер подошёл. Для небольших слов можно использовать для этого не массив меток вида (номер, конец или начало, соответствующий номер в другом слове), а маску где порядковый номер символа в одном слове записывается в порядковый номер, под которым он же находится в другом слове.
тогда будет такое: A нашлось, ищет совпадения дальше, до C, потом D не находит и оставляет метку конца, находит E, и вставляет метку начала, потом доходит до конца строки и видит что совпадений 3. Дальше даже не пытается начать поиск с B, поскольку это третий символ с конца слова1, больше чем 3 символа уже никак не получится, значит мы пришли к максимуму. Вызывается слово1, в нём метки указывают что между найденными соответсвующими C и E надо вставить кусок слова2 между метками слова2 (а там D). В итоге будет такое слово. Только надо метки писать — куда какой номер подошёл. Для небольших слов можно использовать для этого не массив меток вида (номер, конец или начало, соответствующий номер в другом слове), а маску где порядковый номер символа в одном слове записывается в порядковый номер, под которым он же находится в другом слове.
Чего-то я как не кручу, не получается 7 (если брать худший случай, когда топ5 лошадей набивается в одну пятёрку), выходит 8 по любому.
Заголовок спойлера
Первый пять забегов, понятно, все лошади по разу.
(6) — первая из каждой пятерки.
Получаем самую быструю + 2 кандидата (6.1 + 6.2) + выпадают все лошади из пятёрок тех, кто на 3, 4 и 5 местах.
Итого остаётся получить 2х самых быстрых из 6 лошадей (2 кандидата + места 2/3 из пятерок победителя и второго места), из которых нам только известно только про двух лошадей что одна быстрее другой (безотносительно остальных 4х). Еще 2 забега потому, имхо…
(6) — первая из каждой пятерки.
Получаем самую быструю + 2 кандидата (6.1 + 6.2) + выпадают все лошади из пятёрок тех, кто на 3, 4 и 5 местах.
Итого остаётся получить 2х самых быстрых из 6 лошадей (2 кандидата + места 2/3 из пятерок победителя и второго места), из которых нам только известно только про двух лошадей что одна быстрее другой (безотносительно остальных 4х). Еще 2 забега потому, имхо…
Вопрос 1 — 58 сек?
Во второй задаче перевод неправильный, там нужно определить минимальное кол-во забегов.
apple pear => applear
мне одному кажется что в applear нет подстроки pear?
мне одному кажется что в applear нет подстроки pear?
applear
Подмножеством не обязательно является цельная подстрока.
Подмножеством не обязательно является цельная подстрока.
И опять неточный перевод.
{a,p,l,e} — подмножество {a,e,l,p}? Да, ведь множество — набор без какого-либо порядка.
Тогда, задача тривиальна — выбираем все различные буквы из первого слова и из второго, объединяем эти множества, вот и ответ.
В оригинале речь шла о подпоследовательности.
{a,p,l,e} — подмножество {a,e,l,p}? Да, ведь множество — набор без какого-либо порядка.
Тогда, задача тривиальна — выбираем все различные буквы из первого слова и из второго, объединяем эти множества, вот и ответ.
В оригинале речь шла о подпоследовательности.
Верно, subsequences = подпоследовательности. Но тогда пример должен быть вроде: apple, pear => applepear, что тоже тривиально.
Я счёл, что пример, взятый из оригинала, более корректно иллюстрирует условие, поэтому перевёл соответствующе.
Я счёл, что пример, взятый из оригинала, более корректно иллюстрирует условие, поэтому перевёл соответствующе.
Нетривиально, если учесть, что требуется не любая строка, а минимальной длины.
Можете предложить решение для подпоследовательностей?
Это очень похоже на задачу поиска наибольшей общей подпоследовательности из двух строк, которая решается динамическим программированием за
Нужно рассмотреть ф-цию F(a,b), которая решает задачу на урезанных входных строках длины a и b, а затем вычислять F(a,b) для всех a=1..N, b=1..M, опираясь на предыдущие вычисленные F
Обычно в таких задачах даже можно уложиться по памяти не в O(N*M), а в O(max(N,M)), т.к. рекуррентная формула обращается только к предыдущей строке матрицы.
На собеседовании, наверное, я бы записал рекуррентное соотношение минут за 15-30, но сейчас думать лень )))
O(NM), N=length(s1), M=length(s2)Нужно рассмотреть ф-цию F(a,b), которая решает задачу на урезанных входных строках длины a и b, а затем вычислять F(a,b) для всех a=1..N, b=1..M, опираясь на предыдущие вычисленные F
Обычно в таких задачах даже можно уложиться по памяти не в O(N*M), а в O(max(N,M)), т.к. рекуррентная формула обращается только к предыдущей строке матрицы.
На собеседовании, наверное, я бы записал рекуррентное соотношение минут за 15-30, но сейчас думать лень )))
вопрос 1) 58 сек
вопрос 2) 6 забегов
вопрос 2) 6 забегов
Есть ошибки :)
В 1 вопросе бактерия делением звонит пробирку за 60 секунд на 2^60. 4 бактерии заполнят: 2^60/4 и от этого числа взять логарифм по основанию 2
Задача 2) 25 лошадей делим на 5 лошадей в забеге и получаем 5 победителей, потом ещё 1 забег. Правда в этом случае не сработает если все хорошие лошади в одной пятерке.
Задача 2 вариант 2) из каждого забега брать по 3 лошади и формировать пятерки из них итого 12 забегов.
По 3 из всех не обязательно брать. Достаточно отсортировать забеги по забегу лидеров первых пяти гонок, а затем сравнить в одном забеге 1.2, 1.3, 2.1, 2.2 и 3.1 (место_лидера_пятёрки_в_6_забеге.место_лошади_в_забеге_с_этим_лидером_из_первых_5_забегов).
степени, логарифмы — как сложно-то…
Состояния «в пробирке уже 4 бактерии» исходная особь достигает за 2 секунды (1->2->4), итого 60-2=58.
Состояния «в пробирке уже 4 бактерии» исходная особь достигает за 2 секунды (1->2->4), итого 60-2=58.
12 забегов, кмк
решение
5 забегов по 5 лошадей — среди них выбираем по 3 лучших из каждого — осталось 15 лошадок
3 забега по 5 — выбираем по 3 лучших из каждого — осталось 9 лошадок
2 забега 5+4 — выбираем по 3 лучших — осталось 6
1 забег из 5 лошадей — 3 лучших идут в следующий забег
1 забег из 4х лошадей (3 из предыдущего и +1 отдыхающая лошадь) — по результатам определяем 3 быстрейших лошади
лошадки, конечно, должны бегать стабильно по своему максимальному результату и не уставать :)
3 забега по 5 — выбираем по 3 лучших из каждого — осталось 9 лошадок
2 забега 5+4 — выбираем по 3 лучших — осталось 6
1 забег из 5 лошадей — 3 лучших идут в следующий забег
1 забег из 4х лошадей (3 из предыдущего и +1 отдыхающая лошадь) — по результатам определяем 3 быстрейших лошади
лошадки, конечно, должны бегать стабильно по своему максимальному результату и не уставать :)
Теоретический минимум — 5 забегов, даже если бы был таймер, чтобы протестировать всех лошадей. Максимум при последовательном переборе — 11, если из каждого забега оставлять тройку лидеров и заменять последних двух лошадей свежими: 5-2-2-2-2-2-2-2-2-2-2. У меня получилось минимум 9 забегов.
Всё же можно уложиться в 7 забегов — 5 основных, 6й — между лидерами, 7-й между 5ю оставшимися лошадьми, как описано в комменте Nick_mentat
Мои решения.
Заголовок спойлера
1) Подобная задача у нас была ещё в школе, классе примерно 8-м. И даже тогда она легко решалась.
2) Первое решение — это разбить всех на 5-ки. Пустить 5 забегов (узнать места внутри пятерки). Выбираем 5 лидеров. Затем пока не наберем нужное количество поступаем так: устраиваем забег, выбираем первую лошадь, и на её место ставим следующую лошадь из её пятерки. Всего 8 забегов. Причем это общий подход, на любое количество лошадей.
А второе решение (7 забегов) пришло, когда а нарисовал на листке положение лошадей после 6-го забега и вычеркнул тех, кто не может претендовать на тройку.
3) Вот это уже сложная задача, решение приличное я не нашел. Она одна стоит больше всех остальных вместе взятых. Даже не утерпел и посмотрел решение Nick_mentat, но к нему у меня много вопросов.
4) Тут 2 варианта. Если разрешено использовать дополнительные ячейки, тогда нужно приводить путем умножение на 10^n к "одной весовой категории", сохранить для каждого числа получившиеся значение, которые уже и сравниваются. При этом, в случае равенства, нужно сравнивать исходные числа (чтобы упорядочить 10 и 100). Этот вариант более быстрый, за счет того, что операция приведение (а она не дешевая) выполняется 1 раз.
Второй вариант — это написание КОМПОРАТОРА, который принимает на вход 2 числа, и сравнивает их. А дальше можно вызывать стандартную функцию сортировки. Это не требует лишней памяти, но требует приведения чисел каждый раз при сравнении.
5) Самый простой способ — это вычислить сумму чисел обоих массивов и произведение чисел (на 0 не умножаем) обоих массивов. Тогда мы получим произведение и сумму искомых чисел. Эти 2 уравнения приводятся к полиному второй степени, и элементарно находятся. Но тут несколько моментов. Первоначально нужно посчитать количество нулей в обоих массивах, если оно разное, то находить произведение смысла нет. С суммой тоже вопросов нет, достаточно взять тип целого, который больше используемых чисел. Например если массивы заполнены 32-битными значениями, то использовать надо 64-битное. С умножением сложнее, умножение пару сотен чисел переполняет даже самые большие типы целого. Значит для умножения нужно использовать числа с плавающей точкой. Да, там будет потеря точности, но старшие биты должны вытянуть (обеспечить) правильное значение.
Насчет задачи 3). Лучшее, что я придумал — это полный перебор, когда первое слово перемешивается со вторым (с сохранением последовательности внутри), для каждого варианта ищем букву из первого слова, которая оказалась равна рядом стоящей букве из второго слова (т.е. эту букву можно выкинуть). Считаем количество таких букв, запоминаем комбинацию, когда их число максимально. Такой алгоритм дает гарантированный результат, но имеет очень плохую алгоритмическую сложность, что-то вроде O(n^m).
Прошу прощения. Нумеровал задания по порядку. 1) и 2) — это вопросы. 3), 4), 5) — это задачи 1, 2 и 3.
Уточнение к решениям
Заголовок спойлера
Задача с массивами: там можно обойтись без произведения, просто посчитать сумму чисел в массиве, и сумму КВАДРАТОВ чисел в массиве. Это также приводит к квадратичному уравнения. Но избавляет от необходимости отдельной проверки на нули. По сути — это обработка в 1 проход, с использованием всего 2-х переменных. Короче решения я представить не могу.
Задача с подмножествами. Здесь очевидно, нужно работать с укороченными строками, выбросив те буквы из первого слова, которые не входят во второе, и буквы из второго слова, которых нет в первом. Остатки от 2-х слов уже пытаемся перебором «перемешать» в строку минимальной длины. А уже потом (и это тривиально) добавить выкинутые буквы. В худшем варианте (когда буквы нельзя выкинуть) сложность остается той же, но зато существенно сокращает сложность, когда у обоих слов всего 1 буква общая.
Задача с подмножествами. Здесь очевидно, нужно работать с укороченными строками, выбросив те буквы из первого слова, которые не входят во второе, и буквы из второго слова, которых нет в первом. Остатки от 2-х слов уже пытаемся перебором «перемешать» в строку минимальной длины. А уже потом (и это тривиально) добавить выкинутые буквы. В худшем варианте (когда буквы нельзя выкинуть) сложность остается той же, но зато существенно сокращает сложность, когда у обоих слов всего 1 буква общая.
Задача с подпоследовательностями. Решение.
Заголовок спойлера
Пусть даны слова OPACKADOS и MABUDYDCMAB
1) Первым делом находим общие буквы в обоих словах. Как это сделать (через хэш, массив или полным поиском) — не принципиально. Общие буквы у них — ACD.
2) Для обоих слов создаем урезанные варианты (оставляем только общие буквы), и при этом запоминаем соответствие. Получаются слова ACAD и ADDCA, и соответствие [3,4,6,7] и [2,5,7,8,10].
3) Создаем массив размером произведения длин сокращенных слов, в нашем случае 4 * 5.
Выбираем слово ACAD проходим по нему с конца (начиная с буквы D). Для каждой такой буквы из первого слова проходим по второму в обратном порядке, и ищем совпадающие буквы. Когда буквы совпали, делаем проход по первому слову в правильном порядке, начиная с буквы справа от текущей (слева от D в нашем примере ничего нет, поэтому ничего не делаем) и смотрим что стоит в массиве для этой буквы и её положения. Находим максимальное значение, прибавляем к нем 1 и сохраняем в массиве в текущем положении и для всех леволежащих, пока не найдем число большее. И того у нас получается тройной цикл (по первому слову-по второму слову-по первому слову).
В чем смысл массива — значение в ячейке x,y говорит нам о максимальной подпоследовательности которая бы начиналась с x-места первом слове, y-места второго слова.
Чтобы было понятно приведу результаты обработки ACAD и ADDCA.
A [3 1 1 1 1]
C [2 2 2 2 0]
A [2 2 1 1 1]
D [1 1 1 0 0]
максимальное значение — 3. Теперь мы имеем в наличии длину искомой последовательности, и букву (положение) в первом слове, с которой она начинается.
4) Используя всё это и массив находим узлы (положение букв в обоих словах) за 1 проход.
В нашем случае A(1,1) C(2,4) A(3,5).
5) Возвращаемся к исходным словам, переводим по таблице соответствия наши узлы.
OPACKADOS и MABUDYDCMAB => A(3,2) C(4,8) A(6,10). После чего разбиваем наши слова на участки (между узлов, узлы не входят ). Берем первый участок первого слова, прибавляем первый участов второго слова и прибавляем сам узел, и так далее…
OP — M — A…
Вычислительная сложность что-то типа между O(n*n+m*n) в случае, если каждая буква встречается не чаще 1 раза и O(n*n*m) в случае, если все буквы одинаковы. Т.е. сложность между квадратичной и кубической.
Ура товарищи!!!
1) Первым делом находим общие буквы в обоих словах. Как это сделать (через хэш, массив или полным поиском) — не принципиально. Общие буквы у них — ACD.
2) Для обоих слов создаем урезанные варианты (оставляем только общие буквы), и при этом запоминаем соответствие. Получаются слова ACAD и ADDCA, и соответствие [3,4,6,7] и [2,5,7,8,10].
3) Создаем массив размером произведения длин сокращенных слов, в нашем случае 4 * 5.
Выбираем слово ACAD проходим по нему с конца (начиная с буквы D). Для каждой такой буквы из первого слова проходим по второму в обратном порядке, и ищем совпадающие буквы. Когда буквы совпали, делаем проход по первому слову в правильном порядке, начиная с буквы справа от текущей (слева от D в нашем примере ничего нет, поэтому ничего не делаем) и смотрим что стоит в массиве для этой буквы и её положения. Находим максимальное значение, прибавляем к нем 1 и сохраняем в массиве в текущем положении и для всех леволежащих, пока не найдем число большее. И того у нас получается тройной цикл (по первому слову-по второму слову-по первому слову).
В чем смысл массива — значение в ячейке x,y говорит нам о максимальной подпоследовательности которая бы начиналась с x-места первом слове, y-места второго слова.
Чтобы было понятно приведу результаты обработки ACAD и ADDCA.
A [3 1 1 1 1]
C [2 2 2 2 0]
A [2 2 1 1 1]
D [1 1 1 0 0]
максимальное значение — 3. Теперь мы имеем в наличии длину искомой последовательности, и букву (положение) в первом слове, с которой она начинается.
4) Используя всё это и массив находим узлы (положение букв в обоих словах) за 1 проход.
В нашем случае A(1,1) C(2,4) A(3,5).
5) Возвращаемся к исходным словам, переводим по таблице соответствия наши узлы.
OPACKADOS и MABUDYDCMAB => A(3,2) C(4,8) A(6,10). После чего разбиваем наши слова на участки (между узлов, узлы не входят ). Берем первый участок первого слова, прибавляем первый участов второго слова и прибавляем сам узел, и так далее…
OP — M — A…
Вычислительная сложность что-то типа между O(n*n+m*n) в случае, если каждая буква встречается не чаще 1 раза и O(n*n*m) в случае, если все буквы одинаковы. Т.е. сложность между квадратичной и кубической.
Ура товарищи!!!
В английской версии вопросов похоже много ошибок. Вы сами составляли?
- how long it takes -> how long does it take
- what is the minimum number of races you can find the top 3 -> what is the minimum number of races to find the top 3
- You have make a new string s3 -> You have to make a new string s3
- B contains exactly same numbers -> B contains exactly the same numbers (насчет этого не уверен)
- Find the two elements with minimum time and space complexity -> Find two elements using algorithm with minimum time and space complexity
Спасибо за задачки :)
Почти все не так просты, как кажутся на первый взгляд.
Решения под спойлером
Вопрос 1 (про бактерии)
Нетрудно понять, что если бактерий на старте 1, то через две секунды будет их 4.
Значит, для заполнения пробирки от 4-х бактерий надо на 2 секунды меньше, т.е. 60 — 2 = 58.
Впрочем, можно показать это и математически.
Количество бактерий в момент времени “t”, если начинать с 1-й штуки, 0≤t:
1; 2; 4; 8; 16; … 2^t; …
Если взять объем пробирки (кол-во умещающихся бактерий) за "V", и время заполнения в секундах за "t", то имеем:
V = 2^t
Количество бактерий в момент времени “x”, если начинать с 4-х штук, 0≤x:
4; 8; 16; 32; 64; … 2^(x + 2); …
V = 2^(x + 2)
Поскольку объём пробирки один и тот же, то:
2^t = 2^(x + 2)
t = x + 2
Зная, что t = 60 (пробирка от 1-й бактерии заполняется за минуту), имеем:
60 = x + 2
x = 58
Ответ: пробирка с 4-мя бактериями заполнится за 58 секунд.
Вопрос 2 (про лошадиные бега)
Есть 25 лошадей. За одну гонку можем пустить не более 5 лошадей.
Что это значит – если в гонке участвовали 5 лошадей, то максимум 3 из них входят в топ-3 (логично, э?), ну а 2 худшие – однозначно не входят.
Разделив лошадей на 5 пятёрок, мы можем за 5 гонок отбраковать из них 5 x 2 = 10 однозначно нетоповых лошадок. Остаётся 15 штук.
По тому же принципу, оставшихся 15 делим на 3 пятёрки, по результатам гонок отбраковываем 3 x 2 = 6 однозначно нетоповых лошадок.
Всего проведено 5 + 3 = 8 гонок, осталось на рассмотрении 25 — 10 — 6 = 9 лошадок.
Делим оставшихся 9 на две группы, одна 5, другая 4 лошадки. Проводим 2 гонки, отбраковывая ещё 2 + 1 = 3 однозначно нетоповых лошадок.
Всего проведено 5 + 3 + 2 = 10 гонок, осталось на рассмотрении 25 — 10 — 6 — 3 = 6 лошадок.
Выбираем из оставшихся 6 лошадок любые 5 и проводим 11-ю по счёту гонку. Ещё 2 однозначно нетоповые лошадки выбывают из рассмотрения.
Всего проведено 5 + 3 + 2 + 1 = 11 гонок, осталось на рассмотрении 25 — 10 — 6 — 3 — 2 = 4 лошадки.
К лучшим 3-м из 11-го забега лошадкам добавляем ту 1-у, которая не участвовала в 11-м забеге, и устраиваем (из получившихся 4-х лошадок) финальный, 12-й, забег.
Лучшие 3-и лошадки по итогам этого, 12-го, забега и будут топ-3.
Итого: на 25 лошадок нужно не менее 12-и забегов. К сожалению, не могу доказать, что данный алгоритм является наилучшим и нет возможности выявить топ-3 за меньшее число забегов, нежели 12.
Ответ: 12 забегов.
Задача 1 (Построить строку с подмножествами)
Из условий задачи ясно, что 1-я строка будет полностью входить в результирующую строку. Ну а из 2-й строки нужно взять только те символы, которых «не хватает» до объединённого множества символов обеих (с учётом повторяемости, т.е. когда в одной строке есть “r”, в другой – “rrr”, то в конечном результате имеем “rrr”).
Код (C#):
using System;
using System.Linq;
using System.Text;
using System.Collections.Generic;
static class Solution
{
// для простоты не учитываю регистр символов (но это легко поправить)
static void Main(string[] args)
{
string s1 = "apple";
string s2 = "pear";
// подсчитываем встречаемость символов 1-й строки
Dictionary<char, int> d1 = s1.GroupBy(c => c).ToDictionary(v => v.Key, v => v.Count());
// подсчитываем встречаемость символов 2-й строки, которых "не хватает" в 1-й строке (так, если в 1-й строке есть "r", а во второй "rrr", в d2 попадёт "rr")
Dictionary<char, int> d2 = s2.GroupBy(c => c).Where(v => (!d1.ContainsKey(v.Key)) || (d1[v.Key] < v.Count()))
.ToDictionary(v => v.Key, v => v.Count() - (d1.ContainsKey(v.Key) ? d1[v.Key] : 0));
// буфер результата
StringBuilder result = new StringBuilder(s1);
// проходим по 2-й строке и берём из неё те символы (в порядке их следования), которых не хватает в 1-й строке
for (int i = 0; i < s2.Length; i++)
if ((d2.ContainsKey(s2[i])) && (d2[s2[i]] > 0))
{
result.Append(s2[i]);
d2[s2[i]]--;
}
// вывод результата (если во 2-й строке нет таких символов, которых бы "не хватало" во 1-й строке, то будет выведена в точности 1-я строка)
Console.WriteLine(result.ToString());
}
}Если в 1-й строке “n” символов, а во 2-й строке “m” символов, то сложность самого алгоритма (без учёта [не]удачности реализации) будет складываться из:
- O(n) на подсчёте встречаемости символов 1-й строки
- O(m) на подсчёте встречаемости символов 2-й строки (предполагаю, что словарь Dictionary<char,int> основан на хэш-таблице со сложностью O(1) в поиске и обновлении элементов)
- O(m) на проходе по 2-й строке для взятия «недостающих» символов
Итого: что-то вроде O(n+m+m).
Задача 2 (Словарная сортировка чисел)
Похоже на задачу по деревьям. Но поскольку я в них слабоват, то выкрутился другим способом :)
Были бы числа одного порядка (из одинакового количества цифр), то их можно было бы отсортировать по значениям и не париться…
Но коль значения разных порядков, то… можно их привести к одному, наибольшему порядку.
И затем уже сортировать. Правда, при этом числа 100 и 1 могут выстроиться в неправильном порядке относительно друг друга – ведь их «приведённые» значения будут одинаковы и равны, допустим 1000.
Но это на самом деле не проблема – сортируем сразу по двум значениям каждого числа: сначала по «приведённому» значению (1000, 1000), затем по исходному (100, 1), и данные числа таки расположатся правильно.
Код (C#):
using System;
using System.Linq;
static class Solution
{
// вспомогательная структура для сортировки
struct SortingNum
{
// сортировочное значение числа
public int SortValue;
// исходное значение числа
public int OriginalValue;
public SortingNum(int sort_value, int original_value)
{
this.SortValue = sort_value;
this.OriginalValue = original_value;
}
}
static void Main(string[] args)
{
// входной массив чисел
int[] nums = new int[] { 1, 2, 10, 20, 100, 110 };
// находим опорное число - наименьшую степень 10, которую не превосходит ни одно из исходных чисел
int ref_value = 10;
while (ref_value < nums.Max())
ref_value *= 10;
// составляем новый массив из исходных чисел
SortingNum[] sort_nums = new SortingNum[nums.Length];
for (int i = 0; i < nums.Length; i++)
{
int srt_val = nums[i];
// повысить исходное число до порядка опорного числа
while (srt_val < ref_value)
srt_val *= 10;
sort_nums[i] = new SortingNum(srt_val, nums[i]);
}
// сортируем массив чисел, сначала по сортировочному значению числа, затем по исходному
int[] results = sort_nums
.OrderBy(v => v.SortValue).ThenBy(v => v.OriginalValue)
.Select(v => v.OriginalValue).ToArray();
// вывод результатов
Console.WriteLine(string.Join("; ", results.Select(v => v.ToString())));
}
}Данная реализация не оптимальна, и её можно улучшить. Но даже и так, сложность будет зависеть от сложности используемого алгоритма сортировки.
Надо полагать, оценка O(n*log(n)) будет вполне подходящей.
Задача 3 (Найти добавочные элементы в массиве) - пока нет решения
Что-то нету свежих мыслей. Только тривиальные.
Можно загнать первый массив в хэш-таблицу (множество), получая сложность O(n), где n – размер первого массива.
Затем проходим по второму массиву, и каждое число проверяем на входимость в составленную хэш-таблицу. Если входимости нет – выводим как результат. Сложность O(m), где m – размер второго массива.
Итого: сложность будет как-то так: O(n+m).
Вроде бы и неплохо, но тут у меня совершенно нет закладки на малое количество чисел 2-го массива, не содержащихся в 1-м.
Наверняка, тут должна быть какая-то изощренная мысль, которая от меня пока что ускользает :)
Наконец-то интересные, не очень баянистые задачи, спасибо!
Попробую и я свои силы.
- Вопрос про бактерииСтарая задача. Простейший способ рассуждений: если в 1 пробирке вначале была 1 бактерия, а на 60 секунде — полная пробирка, то в этой же пробирке на 2 секунде — 4 бактерии. Сделаем вторую секунду новым началом отсчёта, и получим правильный ответ — 58.
- Вопрос про лошадейЭту задачу я тоже где-то видел, хотя решение не помнил, пришлось придумывать.
Ответ — 7 заездов.
В первых пяти заездах находим 10 точно-не-призовых-лошади, в 6 заезде из победителей первых 5 находим самую быструю. А дальше, если нарисовать схему, можно заметить, что на 2 и 3 место могут претендовать только 5 лошадей — между ними и разыгрываем 2 и 3 призовые места.
- Задача про строку из подмножеств остается пока что без ответа
- Задача про сравнение чиселИз формулировки условия («Как бы Вы отсортировали целые числа в словарном порядке») не следует наличие у нас полного списка чисел, которые нужно отсортировать (хотя я бы это еще уточнил). Поэтому я бы писал компаратор.
При сравнении нужно число разбить на список символов. Проще всего это сделать в отдельном классе, и поскольку функция split недоступна — нужно будет каждый раз вычислять остаток от деления на 10, сохранять в массив символов. Если число отрицательное — нужно не забыть добавить символ '-' в этот же массив. Поскольку при полной сортировке списка одни и те же числа будут участвовать при сравнении много раз, чтобы не считать каждый раз заново, можно сохранять результаты в хеш-таблицу, хотя ее целесообразность зависит от задачи.
Соответственно, при наличии такого разбиения в компараторе достаточно только перебирать символы массивов с конца до нахождения первого несоответствия.
- Задача про добавленные элементыА вот эта задача мне очень понравилась — мой ответ менялся несколько раз.
От сравнения каждого элемента с каждым я отказался сразу, временная сложность O(n^2) это много. Вот если бы массивы были отсортированы, можно было бы за 1 проход найти нужные элементы… Наверное, их нужно отсортировать. Две сортировки quicksort'ом и один проход по отсортированным элементам — временная сложность O(n*log(n)), памяти используется O(1). Казалось бы, куда лучше?
При сортировке меньшую сложность получить не удастся, значит, для уменьшения сложности от полной сортировки нужно отказаться. Следующая идея появилась при более детальной проверке, что происходит при самой сортировке:
Представим, что прошел первый шаг быстрой сортировки для обоих массивов, и (один и тот же) опорный элемент разделил оба массива на 2 части. Представим, что количество элементов в левой части массива A совпадает с количеством элементов в левой части массива B. Это значит, что все добавочные элементы находятся в правой части массивов , а значит нам левую часть сортировать не нужно!
Пользуясь этой информацией, можно сделать программу, которая после каждого разбиения массивов на 2 части вычисляет, что нам нужно сортировать, а что нет. Если оба добавочных элемента попадают в одну часть массива — значит, вторую сортировать не нужно; если же в разные — ну, тогда придется сортировать обе (хотя поскольку добавочных элемента только два, такое может быть только один раз).
Наибольшее количество сортировок происходит, если при первом же проходе добавочные элементы попадают в разные части массивов, поэтому для оценки сложности рассмотрим этот случай. Для каждого массива первый проход по массиву — это O(n) операций; для каждой половины массивов при первом шаге происходит O(n/2) операций, при втором O(n/4), при третьем O(n/8)… То есть в сумме каждая половина массива подобным образом упорядочивается за O(n) операций, а значит и в сумме будет временная сложность O(n) при сохранении сложности по памяти O(1). Меньше сделать не получится никак, потому что хотя бы один раз, но нужно будет все числа прочитать =)
С этим радостным фактом я пошел читать ответы сообщества. Ничего интересного не нашел, первая задача так и не решена, но для этой задачи многие люди предлагают другое решение — найти сумму и произведение всех чисел для обоих массивов, из этого найти сумму и произведение двух добавочных чисел, а дальше решить квадратное уравнение. Сам способ не очень хорош — для больших чисел или больших массивов произведение сможет храниться только в biginteger, с большой временной сложностью умножения и деления. Хотя, он меня натолкнул на очередное улучшение моего алгоритма:
После каждого разбиения quicksort'ом на две части, проверяем, попадают оба числа в одну и ту же часть или в разные. Если в одну — запускаем этот же алгоритм для этой части (в два раза меньшей). Если в разные — для каждой части ищем сумму в массиве A, сумму в массиве B, и с помощью вычитания находим оба добавочных элемента. Сложность не меняется, также временная сложность O(n) и сложность по памяти O(1), но теперь алгоритм стал гораздо нагляднее.
Скорее всего, это всё еще можно улучшить,Скрытый текстно дальше уже не нужно
На правах рекламыjunior java dev, ищу работу :-)
Задача 1 не особо интересна, т.к. решение тревиально.
Задача 2 решения, которые предлагаются мне не до конца ясны, почему то все считают, что устроив 5 забегов для разных наборов лошадей мы каким то образом сможем получить корреляцию между лошадьми из разных забегов, но никто не гарантирует что первая пятерка лошадей, например, не была лучше всех остальных, таким образом на мой взгляд правильное решение такое:
Всего 11 забегов.
Задача 3 не понимаю что требуется, пример ужасно путает.
Задача 4 думаю нужно привести все числа к одному разряду и дальше отсортировать их, затем сравнить для одинаковых исходные и отсрортивать их.
Задача 5 не хочется повторять решения предложенные выше, поэтому массив B делим пополам и начинаем для каждого элемента из выбранной части массива B выполнят проверку на наличие его в массиве А, как только нашли то удаляем его из массива А и В, если нет печатаем его. Если проверили первую половину полностью то повторяем алгоритм рекурсивно для второй части массива В.
Задача 2 решения, которые предлагаются мне не до конца ясны, почему то все считают, что устроив 5 забегов для разных наборов лошадей мы каким то образом сможем получить корреляцию между лошадьми из разных забегов, но никто не гарантирует что первая пятерка лошадей, например, не была лучше всех остальных, таким образом на мой взгляд правильное решение такое:
- Проводим забег из 5 лошадей(осталось проверить 20)
- Берём 3-х лучших и добавляем к ним ещё 2-х. И так до тех пор пока не останется тройка лучших.
Всего 11 забегов.
Задача 3 не понимаю что требуется, пример ужасно путает.
Задача 4 думаю нужно привести все числа к одному разряду и дальше отсортировать их, затем сравнить для одинаковых исходные и отсрортивать их.
Задача 5 не хочется повторять решения предложенные выше, поэтому массив B делим пополам и начинаем для каждого элемента из выбранной части массива B выполнят проверку на наличие его в массиве А, как только нашли то удаляем его из массива А и В, если нет печатаем его. Если проверили первую половину полностью то повторяем алгоритм рекурсивно для второй части массива В.
В последней задачи деление второго массива на части ничего не дает по сравнению с последовательным проходов, вам все равно в худшем случае надо будет проверить все элементы. Вероятность досрочного нахождения элементы такая же. Кроме того, вы меняете данные в массивах (портите их), а не факт что это разрешено. Для правильной работы вам придется сделать копии массивов, а это ДОПОЛНИТЕЛЬНАЯ ПАМЯТЬ.
Задача с конями решается быстрее.
Задача с конями решается быстрее.
Я не согласен с предлагаемыми выше решениями задачи про коней, по уже описанной причине (нет гарантии что все самые быстрые лошади не в первой пятерке, например).
Все варианты решения тут уверяют ю что мы можем сказать лошадь 3 из забега 1 точно хуже лошади 1 из забега 2 или 3, потому что нет секундомера, поэтому мы не можем сравнивать лидеров независимы забегов, или я не прав?
Все варианты решения тут уверяют ю что мы можем сказать лошадь 3 из забега 1 точно хуже лошади 1 из забега 2 или 3, потому что нет секундомера, поэтому мы не можем сравнивать лидеров независимы забегов, или я не прав?
Варианта с «все самые быстрые лошади не в первой пятерке» отрабатывается корректно. Лидер первой пятерки попадает автоматом в топ после 6-го забега. А далее в 7 забеге участвуют 2 другие лошади из первой пятерки. Они в этом забеге соревнуются с лидерами второй и третей пятерки + второй лошади второй пятерки. Если они выигрывают (приходят первой и второй) 7 забег, то они и попадают в топ.
Не можем, однозначно не можем, но мы можем их прогнать вместе в 7-м забеге и узнать точно нужные места. Заметьте, что мы оставляем 3 лошади из первой пятерки, 2 лошади из второй, и 1 лошадь из третьей. Всего 6 штук, но одна из них гарантированно лидер.
Все варианты решения тут уверяют ю что мы можем сказать лошадь 3 из забега 1 точно хуже лошади 1 из забега 2 или 3, потому что нет секундомера, поэтому мы не можем сравнивать лидеров независимы забегов, или я не прав?
Не можем, однозначно не можем, но мы можем их прогнать вместе в 7-м забеге и узнать точно нужные места. Заметьте, что мы оставляем 3 лошади из первой пятерки, 2 лошади из второй, и 1 лошадь из третьей. Всего 6 штук, но одна из них гарантированно лидер.
Я не совсем понимаю, с чего вы взяли по 7 забегов в задаче о конячках. Я полностью согласен о первых 6 забегах, о нахождении самой быстрой, однако у меня возникает вопрос: почему вы с каждой пятёрки выкидываете аж по 3 лошади (что уже в корне не верно, так как в любой из пятёрок может находится та самая троица). А ещё утверждение рода «лошадь №3 из первого забега 100% медленне лошади №2 из четвёртого забега».
Прошу ответить, почему некоторые нашли 10/11 забегов минимум, может я чего упустил.
Прошу ответить, почему некоторые нашли 10/11 забегов минимум, может я чего упустил.
Запрещено
Что мы имеем после перых 5 забегов? Мы смело можем убирать с каждой пятёрки по 2 лошадки, так как они физически не входят в топ-3. Итого имеем: 5 групп по 3 лошади = 15 лошадок (1,2 и 3 места соответственно).
Далее мы выбираем из каждой пятёрки по 1 месту и прогоняем шестым забегом, определяя топ-1. Теперь у нас 14 лошадок и 6 забегов, хорошо (Прошу заметить, господа, 14!).
Каков у нас выбор? Делить группы на 3 и 4 смысла нет, это увеличение кол-ва забегов, поэтому делим по максимуму. 5,5 и 4 лошади на забег, соответственно.
Делаем 7,8 и 9 забеги, определяя (внимание) по 2 самых быстрых лошади на каждую группу (так как мест осталось 2, а остальные снова не помещаются). Итого имеем на 9 забегов группы: 2-2-2 (выкинули 3-3-0, соответственно).
У нас 6 лошадей. Теперь делим на группы по 3 особи. 10 и 11 забеги: находим по самой быстрой лошадке на каждую группу.
12 забегом забираем этих двух лошадок и сравниваем, получая топ-2 и топ-3 места.
Далее мы выбираем из каждой пятёрки по 1 месту и прогоняем шестым забегом, определяя топ-1. Теперь у нас 14 лошадок и 6 забегов, хорошо (Прошу заметить, господа, 14!).
Каков у нас выбор? Делить группы на 3 и 4 смысла нет, это увеличение кол-ва забегов, поэтому делим по максимуму. 5,5 и 4 лошади на забег, соответственно.
Делаем 7,8 и 9 забеги, определяя (внимание) по 2 самых быстрых лошади на каждую группу (так как мест осталось 2, а остальные снова не помещаются). Итого имеем на 9 забегов группы: 2-2-2 (выкинули 3-3-0, соответственно).
У нас 6 лошадей. Теперь делим на группы по 3 особи. 10 и 11 забеги: находим по самой быстрой лошадке на каждую группу.
12 забегом забираем этих двух лошадок и сравниваем, получая топ-2 и топ-3 места.
Заголовок спойлера
В 6-м забеге мы сравнили лидеров пятёрок. Пятерки (или оставшиеся тройки), лидеры которых пришли 4-й и 5-й вприницпе не могут рассчитывать на призовые места, так как лидеры этих пятерок уже проиграли 3-м другим лидерам, а внутри тех пятерок ситуация ещё хуже.
Итого остается при беглом рассмотрении всего 9 лошадок (по 3 лошади из 3-х пятёрок). При более подробном рассмотрении, оказывается, что лошадь, которая пришла в прошлый раз первой — лучшая среди всех. И её можно исключать сразу, а далее нужно просто понять кто займет 2 и 3 место. Из оставшихся 8-ми лошадок можно выкинуть ещё 3. Остается как раз 5 для выявления серебра и бронзы.
Итого остается при беглом рассмотрении всего 9 лошадок (по 3 лошади из 3-х пятёрок). При более подробном рассмотрении, оказывается, что лошадь, которая пришла в прошлый раз первой — лучшая среди всех. И её можно исключать сразу, а далее нужно просто понять кто займет 2 и 3 место. Из оставшихся 8-ми лошадок можно выкинуть ещё 3. Остается как раз 5 для выявления серебра и бронзы.
Можно ли уточнить, почему осталось 9 лошадок (а точнее, почему вы взяли всего 3 пятёрки)? В каждой пятёрки есть по 3 лидера и по 2 проигравших лошади (после 5 первых забегов). Мы сразу получаем 15 лошадей. Отбирая топ-1 с каждой группы и устраивая забег, мы получаем победителя, а тех лошадей возвращаем обратно, потому что мы не уверены, что, например, вторая лошадь с пятой группы (которую вы, как я понял, уже откинули) медленнее первой лошади с любой иной группы. По такой же аналогии мы не можем быть уверены, что третья лошадь с какой-то группы обязательно медленнее любой другой лошади с 1/2 места но с другой группы. Поэтому я не вижу вообще варианта с 9 лошадками.
Заодно, пользуясь случаем, исправлю себя
Заодно, пользуясь случаем, исправлю себя
Заголовок спойлера
10 и 11 забегом (который над 3 лошадками) мы не ищём победителей, а выкидываем как раз проигравших (то бишь треертью лошадку), получая по 2 лошадки на группу. И 12 забегом сливаем эти 4 лошадки в 1 кучу и после пробега забираем первых двух.
Шестой забег — это забег лидеров предыдущих пяти пятерок. И те лидеры, которые в шестом забеге прибежали на 4 и 5 месте — уже не попадают в общую лучшую тройку. А значит и лошади из их забегов тоже (они ведь еще хуже).
Объясню на примере: допустим в шестом забеге лошади прибежали в таком порядке:
- Лидер из забега №2.
- Лидер из забега №3.
- Лидер из забега №5
- Лидер из забега №1.
- Лидер из забега №4.
Таким образом ВСЕ лошади из забегов №1 и №4 точно не могут входить в общую лучшую тройку. Ведь лидеры забегов №2, №3 и №5 — гарантированно быстрее.
На хакерорге был вариант первой задачи с условием умирания бактерий
Инглиш
Scientists have noted that a member of a strange bacteria species has a cycle of life like this:
Day 1: the bacterium is born from a division of his 'mother'.
Day 2: the bacterium divides itself into two bacteria (one of them is a brand new bacterium).
Day 3: the bacterium divides itself into two bacteria again (one of them is a brand new bacterium).
Day 4: the bacterium has already divided itself twice. Now it's ready to die.
Day 5: the bacterium dies.
A unique member of this kind has been collected by scientists. After 8 days, the population is 47. The question is: after how many days will the entire population of bacteria originated by this unique member reach the count of 1,000,000,000,000?
Day 1: the bacterium is born from a division of his 'mother'.
Day 2: the bacterium divides itself into two bacteria (one of them is a brand new bacterium).
Day 3: the bacterium divides itself into two bacteria again (one of them is a brand new bacterium).
Day 4: the bacterium has already divided itself twice. Now it's ready to die.
Day 5: the bacterium dies.
A unique member of this kind has been collected by scientists. After 8 days, the population is 47. The question is: after how many days will the entire population of bacteria originated by this unique member reach the count of 1,000,000,000,000?
Перевод
Ученые заметили, что для каждой бактерии этого вида характерен такой жизненный цикл:
День 1: Рождения бактерии из разделения его прародителя
День 2: Бактерия разделяется надвое
День 3: Бактерия снова разделяется надвое
День 4: Бактерия уже разделилась дважды и готова умереть.
День 5: Бактерия умирает
Ученые пронаблюдали за отдельно взятой бактерией. Через 8 дней численность их
популяции достигла 47 бактерий.
Вопрос: через сколько дней популяция достигнет отметки в 1 000 000 000 000?
День 1: Рождения бактерии из разделения его прародителя
День 2: Бактерия разделяется надвое
День 3: Бактерия снова разделяется надвое
День 4: Бактерия уже разделилась дважды и готова умереть.
День 5: Бактерия умирает
Ученые пронаблюдали за отдельно взятой бактерией. Через 8 дней численность их
популяции достигла 47 бактерий.
Вопрос: через сколько дней популяция достигнет отметки в 1 000 000 000 000?
Решение
А вот это интересно. Интуитивно сложно подобрать функцию кол-ва бактерий от дня.
Но это Fi_(n+1) + Fi_(n-1), где Fi — это Фибоначчи. Теперь осталось сделать функцию Фибоначчи, которая итерирует n+1 до момента когда есть хотя бы 1*10^12 бактерий, а затем возвращает последний n.
Но это Fi_(n+1) + Fi_(n-1), где Fi — это Фибоначчи. Теперь осталось сделать функцию Фибоначчи, которая итерирует n+1 до момента когда есть хотя бы 1*10^12 бактерий, а затем возвращает последний n.
Сложная часть
Рассмотрим отдельно только новорожденных бактерий — отметки, с которых для каждой из них начинается цикл размножения. По сути бактерия один раз ветвится, и один раз ветвится на двух потомков — один новый, один более не способный к размножению. Значит это всё равно как если бы он просто передал свои полномочия по размножению новой бактерии — всё равно старую половинку можно считать уже никем. Значит из одной новой бактерии получаются в итоге две, одна завтра, одна с запаздыванием — послезавтра. Это приводит нас к ряду Фибоначчи — сегодня способных к размножению столько, сколько вчера плюс позавчера. Но есть ещё старички. Они один день готовятся к смерти, и один день умирают. Значит это те кто новорожденным 3 и 4 дня назад. Т.е. нам надо добавить к общему числу бактерий Fi_(n), Fi_(n-3) и Fi_(n-4), но мы знаем, что Fi_(n-3) + Fi_(n-4) это Fi_(n-2). Я проверил гипотезу по числу 47, но они, видимо имеют ввиду что через n дней — это значит идёт n+1-ый. То есть индексацию надо сдвинуть на один. Ещё неясно, считается ли бактерия на 5 день мёртвой, или уже умершей, но это тоже проясняет проверочное 47 на 9 шаге цикла.
Обещали ответы "на следующей неделе", следующая неделя закончилась. Где ответы?=\
Мне интересно, как 1 задача решается.
Задача с подпоследовательностями решена красиво. O(n*m). Это лучше, чем предлагал я.
В решении последней задачи, наверное, стоило использовать long для сложения квадратов. Конечно, в задачи не указывалось ограничение по максимальному значению, и в примере достаточно малые числа, но квадрат int очень часто выходит за диапазон этого типа.
В решении последней задачи, наверное, стоило использовать long для сложения квадратов. Конечно, в задачи не указывалось ограничение по максимальному значению, и в примере достаточно малые числа, но квадрат int очень часто выходит за диапазон этого типа.
Последнюю задачу можно решить xor'ом — это красивее, и не будет проблем с длиной числа. Правда, известное мне решение будет работать дольше (но не асимптотически дольше), чем предложенное.
Я думал в эту сторону, ничего не придумал.
Также думал складывать числа по разным модулям, чтобы применить теорему об остатках, тоже не дошёл до завершённого решения.
Также думал складывать числа по разным модулям, чтобы применить теорему об остатках, тоже не дошёл до завершённого решения.
Решение с xor'ом:
Для начала, предположим, что у нас «лишнее» число одно. Тогда мы можем проxorить все числа из А и В, все совпадающие попадут в этот большой xor дважды и взаимно уничтожатся, останется лишнее число.
PS: А еще эта задача часто дается не для двух отдельных массивов, а для одного массива, в котором все числа по парам, а одно (или два) лишнее. Тогда получается еще гарантия того, что найденные числа будут различными, а это чуть легче.
Для начала, предположим, что у нас «лишнее» число одно. Тогда мы можем проxorить все числа из А и В, все совпадающие попадут в этот большой xor дважды и взаимно уничтожатся, останется лишнее число.
Код
Для двух чисел сложнее и уже не так красиво, но тоже ничего.unsigned task3(const std::vector<unsigned>& a, const std::vector<unsigned>& b) {
unsigned ans = 0; // Инициализация
for (const auto& v: {a, b}) { // Для обоих массивов
for (const unsigned& e: v) { // Пробегаемся по всем элементам
ans ^= e; // Добавляем к xor'у
}
}
return ans;
}PS: А еще эта задача часто дается не для двух отдельных массивов, а для одного массива, в котором все числа по парам, а одно (или два) лишнее. Тогда получается еще гарантия того, что найденные числа будут различными, а это чуть легче.
Боюсь, что «для 2-х чисел» это не сложнее, а совсем другая задача. Ну вот получите вы что xor даст число 11111. И что с этого? Ведь искомые числа могут быть и (10000,01111) и (10101,01010), и куча других вариантов. Причем даже наличие суммы двух чисел и xor-а не позволяет сделать однозначный вывод об этих числах.
Правильно замечено, что к массиву должна быть применена операция, обладающая свойствами коммутативности и ассоциативности. Например это сложение, умножение, сложение квадратов… и даже xor. Причем нужны минимум 2 операции, чтобы построить систему из 2-х уравнений, поскольку неизвестных у нас тоже 2. Но не любые 2 операции (их комбинация) способны построить решаемую систему. И для xor-а я здесь места не вижу.
Прошу предъявить решение, если оно у вас имеется.
Правильно замечено, что к массиву должна быть применена операция, обладающая свойствами коммутативности и ассоциативности. Например это сложение, умножение, сложение квадратов… и даже xor. Причем нужны минимум 2 операции, чтобы построить систему из 2-х уравнений, поскольку неизвестных у нас тоже 2. Но не любые 2 операции (их комбинация) способны построить решаемую систему. И для xor-а я здесь места не вижу.
Прошу предъявить решение, если оно у вас имеется.
Неверно сначала понял условие задачи — подумал, что гарантируется, что искомые числа различны (как в уже известной мне задаче про поиск двух непарных чисел в массиве).
Сначала решение в предположении наличия этой гарантии. Искомые числа не равны, поэтому их xor не равен 0. Поэтому в нем есть хотя бы один ненулевой бит. Значит, наши два числа в этом бите различаются (и этот бит мы умеем находить). Поэтому нам достаточно разделить наш массив на две части: состоящую из чисел, у которых в этом бите 0, и состоящую из чисел, у которых в этом бите 1. Применение к ним решения выше дает наши два числа.
В случае, если наши числа равны, мы дойдем до конца этой функции, не выйдя из нее по if'у в последнем цикле. Не уверен, можно ли дальше обойтись xor'ом единым, но, как минимум, у нас здесь есть уверенность в том, что числа равны, так что можно найти их с использованием сложения (ну, разделить пополам придется). Это уже получается не так красиво, как чисто с xor'ом, и подвержено проблеме переполнения. Но мы хотя бы не требуем того, чтобы сумма квадратов всех чисел умещалась в целый тип — нам достаточно того, что каждое число по отдельности будет меньше, чем 2^31.
Сначала решение в предположении наличия этой гарантии. Искомые числа не равны, поэтому их xor не равен 0. Поэтому в нем есть хотя бы один ненулевой бит. Значит, наши два числа в этом бите различаются (и этот бит мы умеем находить). Поэтому нам достаточно разделить наш массив на две части: состоящую из чисел, у которых в этом бите 0, и состоящую из чисел, у которых в этом бите 1. Применение к ним решения выше дает наши два числа.
Код (делается за один проход, чтобы не нужно было сохранять последовательность)
std::pair<unsigned, unsigned> task3(const std::vector<unsigned>& a, const std::vector<unsigned>& b) {
unsigned xor = 0; // xor всех чисел
std::array<unsigned, 32> xors; // массив xor'ов для чисел, у которых в конкретной позиции 1
for (const auto& v: {a, b}) { // Для обоих массивов
for (unsigned e: v) { // Пробегаемся по всем числам
xor ^= e; // Добавляем к xor'у
for (unsigned i = 0; i < 32u; ++i) { // Для каждого разряда
if (e & (1u << i)) { // Если надо
xors[i] ^= e; // Добавляем к соответствующему xor'у
}
}
}
}
for (unsigned i = 0; i < 32u; ++i) { // Пробегаемся по всем разрядам
if (xor & (1u << i)) { // Нашли ненулевой
return{xors[i], xors[i] ^ xor}; // Возвращаем два числа: xor всех, у кого в этом разряде 0 и xor всех остальных
}
}
}В случае, если наши числа равны, мы дойдем до конца этой функции, не выйдя из нее по if'у в последнем цикле. Не уверен, можно ли дальше обойтись xor'ом единым, но, как минимум, у нас здесь есть уверенность в том, что числа равны, так что можно найти их с использованием сложения (ну, разделить пополам придется). Это уже получается не так красиво, как чисто с xor'ом, и подвержено проблеме переполнения. Но мы хотя бы не требуем того, чтобы сумма квадратов всех чисел умещалась в целый тип — нам достаточно того, что каждое число по отдельности будет меньше, чем 2^31.
По сути вы сводите дело к 32-м уравнениям.
В любом случае это один проход.
Мне кажется, что этот момент не существенен, во-первых потому что он вами указан (т.е. предусмотрен), а во-вторых вы сами же и предложили как его обойти.
В любом случае это один проход.
подумал, что гарантируется, что искомые числа различны (как в уже известной мне задаче про поиск двух непарных чисел в массиве).
Мне кажется, что этот момент не существенен, во-первых потому что он вами указан (т.е. предусмотрен), а во-вторых вы сами же и предложили как его обойти.
Ну, меня скорее расстраивает тот момент, что решение оказалось более кривым, чем я думал изначально (в виде добавления сложения или какой-либо более сложной операции). Да и для того, чтобы полностью избавиться от проблемы переполнения, придется что-то экзотическое добавлять, вроде поразрядного сложения в троичной сбалансированной системе счисления.
Поэтому нам достаточно разделить наш массив на две части: состоящую из чисел, у которых в этом бите 0, и состоящую из чисел, у которых в этом бите 1Не понял идею. Допустим, XOR-ы отличаются на 1, т.е. разница двух чисел только в младшем бите. Но 2 лишних числа могут быть и (12,13), и (201,202). Как восстановить старшие биты?
Код (делается за один проход, чтобы не нужно было сохранять последовательность)Не работает:
int main()
{
std::vector<unsigned> A = { 1, 4, 2, 6, 3 };
std::vector<unsigned> B = { 4, 0, 7, 6, 3, 2, 1 };
auto Z = task3(A, B);
std::cout << Z.first << ',' << Z.second;
return 0;
}выводит
3435973835,3435973836
Не работает:Ошибка в строке 3: забыта инициализация переменной. Фикс:
std::array<unsigned, 32> xors = {};Не понял идею. Допустим, XOR-ы отличаются на 1, т.е. разница двух чисел только в младшем бите.Что значит, что разница двух чисел только в младшем бите? Значит, одно из них имеет в этом бите единицу, а другое — ноль. Рассмотрим величину xors[0]: что в нее входит?
В нее входят все те числа из обоих массивов, у которых в нулевом бите единица. То есть, в нее входит ровно одно из наших двух искомых чисел, и еще какие-то другие числа в четном количестве (в четном потому, что они есть и в A, и в B в одинаковом количестве). Учитывая, что a ^ b ^ b = a, получаем, что все числа, кроме искомого, взаимно уничтожаются.
Таким образом, xors[0] равно одному из искомых чисел, а xor — их xor. Значит, xor ^ xors[0] — второе искомое число.
В ответе ко второй задаче про лошадей, вероятно, есть ошибка.
Проверяем «от противного».
Предположим, что в первой пятерке собраны все лучшие лошади. Как это выяснить.
сначала проводится 5 забегов 5-ти пятерок. После чего отбрасываются все 4 и 5 места. (Это точно не 1, 2 и 3 лучшие).
Остается 15 лошадей.
Далее проводится забег 6, 7 и 8 в которых выявляются лидеры среди первых, вторых и третьих мест.
Это нужно еще и потому, что возможен вариант, что в первой тройке разрыв между 1 и 2 местом был столь велик, что туда могли поместиться, например, пара лошадей из другого забега.
Итого выявляются лидеры среди лошадей, занявших 1, 2 и 3 места.
Т.е. 1 место теперь известно точно.
Но 2-я лошадь из 3-го, например, забега, могла быть быстрее, чем 1-я лошадь из второго забега.
Поэтому теперь 4 лошади занявшие 1-е места должны соревноваться с лидером среди забегов «2-х мест» и «3-х мест».
Это значит еще два забега.
Т.е. 9 и 10.
Т.о. чтобы определить три лучших лошади необходимо 10 забегов.
Определение в 7 забегов произвольно исключает вероятность нахождения трех самых быстрых лошадей в одном из первых забегов. Т.о. содержит ошибку.
Проверяем «от противного».
Предположим, что в первой пятерке собраны все лучшие лошади. Как это выяснить.
сначала проводится 5 забегов 5-ти пятерок. После чего отбрасываются все 4 и 5 места. (Это точно не 1, 2 и 3 лучшие).
Остается 15 лошадей.
Далее проводится забег 6, 7 и 8 в которых выявляются лидеры среди первых, вторых и третьих мест.
Это нужно еще и потому, что возможен вариант, что в первой тройке разрыв между 1 и 2 местом был столь велик, что туда могли поместиться, например, пара лошадей из другого забега.
Итого выявляются лидеры среди лошадей, занявших 1, 2 и 3 места.
Т.е. 1 место теперь известно точно.
Но 2-я лошадь из 3-го, например, забега, могла быть быстрее, чем 1-я лошадь из второго забега.
Поэтому теперь 4 лошади занявшие 1-е места должны соревноваться с лидером среди забегов «2-х мест» и «3-х мест».
Это значит еще два забега.
Т.е. 9 и 10.
Т.о. чтобы определить три лучших лошади необходимо 10 забегов.
Определение в 7 забегов произвольно исключает вероятность нахождения трех самых быстрых лошадей в одном из первых забегов. Т.о. содержит ошибку.
Из того, что вы придумали алгоритм, находящий ответ за 10 забегов, никак не следует, что найти ответ за меньшее число забегов нельзя.
Может быть можно. Не возражаю. Но предложенный алгоритм в ответе на задачу имеет ошибку, т.к. не учитывает всех вариантов.
Учитывает. Просто ваш подход не оптимальный.
Если не трудно, то приведите контрпример — вариант, когда алгоритм дает не правильный результат. Уверяю, что вы этот контрпример не сможете подобрать.
Если не трудно, то приведите контрпример — вариант, когда алгоритм дает не правильный результат. Уверяю, что вы этот контрпример не сможете подобрать.
Ну как же не учитывает. Пусть у нас лошадь с номером i бежит i секунд (то есть, как и в вашем комментарии выше, все лучшие лошади попадают в первую пятерку — я так понимаю, что это вы считаете контрпримером).
В соответствии с алгоритмом из поста, мы проводим 5 забегов и получаем следующую картину:
1 2 34 5
6 7 89 10
11 12 1314 15
16 17 1819 20
21 22 2324 25
Вычеркнуты те лошади, которые в тройку лучших точно не попадут, а жирным выделены те, что точно попадут.
Дальше мы проводим 6 забег: пять лучших лошадей (1 6 11 16 21). Из него точно понятно, что лошадь 1 в ответ попадет (поскольку она лучше всех). Также понятно, что лошади 16 и 21 в ответ не попадут (поскольку есть три лошади, которых они хуже: 1, 6 и 11). Также в ответ не попадут лошади 12 и 13 (поскольку они хуже, чем 11 лошадь, судя по первым пяти забегам, а 11 лошадь хуже, чем 1 и 6). И еще в ответ не попадет лошадь 8 (поскольку она хуже, чем 6 и 7, а 6 хуже, чем 1).
То есть, мы получаем следующую картину:
1 2 34 5
6 78 9 10
1112 13 14 15
16 17 18 19 20
21 22 23 24 25
То есть, нам осталось из лошадей 2, 3, 6, 7 и 11 выбрать тех, кто попадет на 2 и 3 места. Очевидно, это можно сделать за один забег (7), поставив в него всех этих лошадей и взяв двоих лучших.
Это то, как работает алгоритм из статьи в случае, если все лучшие лошади попадают в первый забег. Вы же провели забеги 6, 7 и 8 по-другому, из-за чего вам и потребовалось больше забегов. Это не доказывает, что нельзя сделать за 7.
В соответствии с алгоритмом из поста, мы проводим 5 забегов и получаем следующую картину:
1 2 3
6 7 8
11 12 13
16 17 18
21 22 23
Вычеркнуты те лошади, которые в тройку лучших точно не попадут, а жирным выделены те, что точно попадут.
Дальше мы проводим 6 забег: пять лучших лошадей (1 6 11 16 21). Из него точно понятно, что лошадь 1 в ответ попадет (поскольку она лучше всех). Также понятно, что лошади 16 и 21 в ответ не попадут (поскольку есть три лошади, которых они хуже: 1, 6 и 11). Также в ответ не попадут лошади 12 и 13 (поскольку они хуже, чем 11 лошадь, судя по первым пяти забегам, а 11 лошадь хуже, чем 1 и 6). И еще в ответ не попадет лошадь 8 (поскольку она хуже, чем 6 и 7, а 6 хуже, чем 1).
То есть, мы получаем следующую картину:
1 2 3
6 7
11
То есть, нам осталось из лошадей 2, 3, 6, 7 и 11 выбрать тех, кто попадет на 2 и 3 места. Очевидно, это можно сделать за один забег (7), поставив в него всех этих лошадей и взяв двоих лучших.
Это то, как работает алгоритм из статьи в случае, если все лучшие лошади попадают в первый забег. Вы же провели забеги 6, 7 и 8 по-другому, из-за чего вам и потребовалось больше забегов. Это не доказывает, что нельзя сделать за 7.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Выпуск#5: ITренировка — актуальные вопросы и задачи от ведущих компаний