У нас с Мишкой на
прошедшем соревновании вторая
задача прошла претесты, но в зачёт не попала, так как какие-то тесты упали по времени. Сегодня мы с ним её разбирали.
Основные две оптимизации проверки делимости числа:
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 кб)
