Основные две оптимизации проверки делимости числа:
1. Сначала я собрал все цифры в Set, который ещё дополнительно уменьшил по следующим правилам:
val set = mutableSetOf<Char>()
string.forEach { set.add(it) }
if (set.contains('9')) set.remove('3')
if (set.contains('8')) set.remove('2' и '4')
if (set.contains('6')) set.remove('2' и '3')
if (set.contains('4')) set.remove('2')
set.remove('1')
set.remove('0')
2. Потом я оптимизировал проверку делимости BigInteger, используя признаки делимости на 2, 4, 5 и 8. Но эта оптимизация уже не дала сильный прирост, как предыдущая. И всё равно решение задачи не принимали из-за 11-го теста.Пришлось долго думать над условием, что же я пропустил и понял, что количество проверяемых чисел в одном тесте может быть большим, но туда могут передавать одинаковые или близкие числа. И я добавил кэш
Map<Ref>, чтобы не пробегать второй раз для записи в него.
data class Ref(var value: BigInteger)
...
val dividend = readLine()!!.toBigInteger()
val applicable = map[dividend] ?: Ref(dividend).also {
while (true) {
map[it.value] = it
if (test(it.value)) break
it.value = map[++it.value]?.value ?: continue
break
}
}
В результате решение задачи приняли с временем прохождения 1715 мс. Подумав над условием задачи, я понял, что для неё можно не использовать BigInteger, а достаточно использовать Long. Это позволило сократить время исполнения до 1169 мс, а использование памяти - в два раза (с 130000 до 60000 кб)
Круто.
ОтветитьУдалитьХотя более простые решения тоже зашли бы.
Проблема Питона в том, что он по умолчанию работает с целыми числами, как с длинной арифметикой.
Хитрое решение не питоне зашло бы за ~400 мс, простое - примерно в два раза дольше.
На котлине при использовании Long простое решение может зайти за ~400 мс.
Что есть простое и что есть хитрое? Я простым на Котлине получил 1200. Как его можно уменьшить в 3 раза - пока не понимаю
УдалитьЭто простое на Котлине: просто откусываем по цифре и проверяем, если цифра больше 1. Думаю, что сам Long::toString выполняет аналогичную работу, а арифмитические действия в современных процессорах очень быстрые.
ОтветитьУдалитьfun readInt() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun main() {
repeat(readInt()) {
var n = readLong()
while (!ok(n)) n++
println(n)
}
}
fun ok(n_in: Long): Boolean {
var n = n_in
while (n > 1) {
val d = n % 10
if (d > 1 && n_in % d != 0L) return false
n /= 10
}
return true
}
Прикольная проверка делимости. Спасибо!
УдалитьТак как Питон использует длинную арифметику (а это выделение памяти в хипе и прочие сложности), деление на Питоне на порядок медленнее. Хитрость в решении состоит в том, что в диапазоне чисел есть такие, что числа, которые делятся на все свои цифры распределены неравномерно, и есть такие, среди которых большие промежутки.
ОтветитьУдалитьВ тестах мы можем найти такие тесты, что все входные данные одинаковы (и требуют маскимального времени на вычисление). Соответственно, в код добавляем кэш.
def check(n):
m = n
while n:
r = n % 10
if r:
if m % r:
return False
n = n // 10
return True
x = dict()
for _ in range(int(input())):
n = int(input())
if x.get(n, 0):
print(x[n])
continue
for i in range(n, 10**19):
if check(i):
print(i)
x[n] = i
break
Можно добавить оптимизацию в методе check на проверку неравненства не только 0, но и 1. То есть вместо while n написать while n > 1
Сорри, код на Питоне получился совсем плохой. Там форматирование влияет на логику.
УдалитьНо логика аналогична коду на Котлине.
Например return True в методе check выполняется уже после завершения цикла.
Хитрость в том, что догадаться ввести кэш - неочевидно. И второе - скорее всего при выборе языка PyPy 3, а не Python 3 результат будет лучше (быстрее).
Удалитьhttps://stackoverflow.com/questions/18946662/why-shouldnt-i-use-pypy-over-cpython-if-pypy-is-6-3-times-faster
Мне показалось, это очевидно, но перечитал, и решил добавить тест в этот абзац:
УдалитьМожно добавить оптимизацию в методе check на проверку неравненства не только 0, но и 1. То есть вместо while n написать while n > 1
Можно добавить оптимизацию в методе check на проверку неравненства не только 0, но и 1. То есть вместо while n написать while n > 1 и вместо if r написать if r > 1
Дядька СЭМ, а насколько дорого держать мапу по ключу в один символ - цифру? Может, дешевле обычный прямой массив с метками (булевскими, например), есть цифра по индексу или нет? Тогда это можно напрямую склеить с брутфорсом, оптимизируя количество операций %, которые часто в железе дорогие (зависит от железа). Мы у себя внимательно смотрим, если надо делать / или %.
ОтветитьУдалитьВ данном случае будет проще завести массив из десяти элементов. В любом случае, серьёзная оптимизация требует вдумчивого подхода, а времени подумать тут нет - всего два часа на 5 задач.
Удалить