Эта фраза не от хорошей жизни. Работаю в техподдержке, с рассчётом на более продвинутого пользователя эту фразу изменил — спрашиваю «а вы уже пробовали роутер перезагружать?»
Примерно каждый пятый не пробовал. И — о чудо! — после перезагрузки всё исправляется.
Старая задача. Простейший способ рассуждений: если в 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), но теперь алгоритм стал гораздо нагляднее.
Скорее всего, это всё еще можно улучшить,
Неужели эту власть ты не хотел бы сохранить?)
Примерно каждый пятый не пробовал. И — о чудо! — после перезагрузки всё исправляется.
Обещали ответы "на следующей неделе", следующая неделя закончилась. Где ответы?=\
Мне интересно, как 1 задача решается.
Ответ — 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), но теперь алгоритм стал гораздо нагляднее.
Скорее всего, это всё еще можно улучшить,