Блог пользователя Egor

TopCoder Open 2010 Round 4
Автор Egor, 14 лет назад, По-русски
24 июля в 20:00 MSD состоится 4й раунд TopCoder Open
  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Мда, 500ка - это нечто. У всех идеи решений совсем не похожи, большую часть я так и не понял за время челлендж-фазы. Обидно, что в моём решении до правильного не хватало одного 0 в константе-бубне, и похоже, что многие решения попадали из-за вещей такого рода.
Кто как её делал? Моя гипотеза заключалась в том, что если у нас есть ненулевое произведение цифр x, то список кандидатов для него состоит из чисел вида n = ???..??99..9****, где p(n) = x, ??..?? - наименьшее число в классе чисел с таким произведением цифр.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Я решал так. Пусть ответ - это подпоследовательность X, X+1, ..., X+N-1. Рассмотрим самую старшую цифру, которая отличается хотя бы в двух из этих чисел. 

    Перебираем позицию этой цифры, перебираем значение этой цифры в числе X от 0 до 8, включительно. Пусть позиция равна P, P >= 0, а цифра - D. Тогда младшие P+1 цифра числа X будут образовывать число в диапазоне от (D+1)*10^P-N до (D+1)*10^P-1. Перебираем все эти значения и проверяем, что мы можем выбрать фиксированные для всех чисел подпоследовательности старшие цифры, чтобы получить нужные произведения.
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У меня не прошла из-за одного довольно обидного косяка - неаккуратно написал проверку.
    1) случаи когда все элементы prod - нули. Тогда ответ равен:
    10 если prod.size() == 1
    100 если prod.size() < 12
    1000 в противном случае
    2) в противном случае находим какой-то ненулевой элемент prod и генерим его разложения на сомножители (упорядоченные по возрастанию) от 1 до 9 длиной до 19 включительно. Далее неплохо бы поперебирать порядок. Но  будет долго. Можно добавить такой несложный хак. Будем перебирать цифры числа начиная с младшей. Если в какой-то момент мы поймем, что все перестановки оставшихся цифр будут давать такие X, которые будут генерить один и тот же вектор prod, перестаем перебирать все перестановки, вместо этого выписываем оставшиеся цифры в порядке возрастания. Другими словами если у нас prod.size() == 8, мы хотим сгенерить разложение 0-го числа из цифр 1, 2, 3 и на последнюю позицию мы выбрали число 1, то независимо от того как мы расставим оставшиеся числа, переполнения не произойдет, потому как 1 + 8 < 10. То есть самое лучшее число в этом случае 231. Такой хак достаточен для того чтобы решение проходило. Именно в нем я и набажил.
     
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится
    У ACRush очень хорошее решение как всегда - он написал рекурсивную функцию которая считает ответ от иходных данных prod[]. Внутри он перебирает кандидата на младшую цифру первого числа от 0 до 9, докустим это M:
    - проверим что числа правильно заканчиваются: очевидно что при данном M, i-е число заканчивается на (M+i) % 10. Поэтому все произведения цифр prod[i] должны делиться на (M+i) % 10 или быть равны нулю если (M+i) % 10 == 0. Если это не выполняется, то данное M нам не подходит
    - проверим что числа правильно начинаются: в рамках одного (M+i) / 10, т. е. пока у нас нет очередного переноса в старшие разряды, все произведения цифр исключая младшую prod[i] / [(M+i) % 10] должны быть равны (иначе не выполнится уловие что все prod[] идут по порядку). Если это не выполняется, то данное M нам также не подходит
    - когда нашли подходящую младшую цифру M - откусываеем ее, перестраиваем prod, считаем рекурсивно ответ через меньшую подзадачу как 10 * rec(prod_new) + M, и минимизируем

    Работает это видимо очень быстро - полходящих цифр очень мало, а количество элементов в prod убывает примерно в 10 раз на каждом шаге.
    → Ответить