*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

понедельник, 24 мая 2010 г.

Совершенные числа

Решал я тут одну задачу из раздела теории чисел про нахождение совершенных чисел.

В принципе, тривиальная задача. Элементарное разложение на множители.

Как я ее решал. Прочитав определение совершенных чисел (до этого я не знал про такие числа, и далее будет понятно, что это было моей главной проблемой) и поняв, что мне надо разложить число на множители, я написал что-то вроде:

bool is_perfect(long long n) {
  if (n == 1) return false;
  long long s = 1;
  long long q = sqrt((double)n);
  for (long long i = 2; i <= q; ++i) {
    if ((n % i) == 0) {
      s += i;
      if (n/i != i) s += n/i;
    }
  }
  return s == n;
}

...
  bool found = false;
  while (m <= n) {
    if (is_perfect(m)) {
      os << m << endl;
      found = true;
    }
    m += 1;
  }
  if (!found) os << "Absent" << endl;
...

Ничего оригинального. Работает на данных тестовых контрольных примерах. Прогоняю в системе. На одном из тестов мне сообщают, что программа работает более двух секунд, и это превышение данного временного лимита.

И только тут я смотрю на органичения задачи. А именно, что верхняя граница для N - это 5*10^18, то есть если при этом дать M=1, то мой цикл должен будет пробежать ~10^18 значений, что в отведенные на это 2 секунды явно не укладывается.

Почесав репу, я начал гуглить, так как идей по ускорению алгоритма не было.

Первый же поиск раскрыл мне суть проблемы - а сколько вообще есть таких совершенных чисел? Оказывается, что на интервале от 0 до 5*10^18 их всего-то восемь, и они уже давно вычислены!

6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128

Поэтому вместо самостоятельного вычисления этих чисел надо просто найти, какие их этих восьми попадают в данный интервал [M, N]. Как говорится "Easy peasy lemon squeezy!".

Естественно, после этого решение успешно засабмитилось.

Мораль (кстати, верная не только для спортивного программирования) - начинать решение алгоритмической задачи следует с выяснения верхних ограничений входных данных, ибо чаще всего они подсказывают путь решения. Как это ни странно, почему-то вместо этого сразу хочется кодить, откладывая на потом осознание факта, что в ограничения-то программа не укладывается.

Мораль 2. Есть случаи, когда надо просто знать, как решать тот или иной тип задач. А знать это можно только хотя был раз их прорешав. Можно, конечно, и самому изобрести новый QuickSort с нуля, но это будет уже другая история.

P.S. Сейчас идет Google Gode Jam 2010.

В квалификации я решил полностью две задачи из трех, что достаточно для этого раунда. В раунде же 1 (я пробовал все его подтуры) я решал только одну задачу, что, увы, маловато.

Еще интересный момент. В подраунде Round 1B участвовал известный своим юным возрастом "спортивный" программист Геннадий Короткевич (третья позиция сверху таблице результатов). Я всегда очень люблю смотреть решения других людей. Поглядев на его решения, а был реально поражен тем, что они написаны на Дельфи! (а фактически на Паскале) (на Code Jam'е по статистике есть решения и на более "экзотических" языках типа BrainFuck'а или PostScript'а, но такие программы скорее всего сгенерированы из "традиционного" языка, и это уже иная тема). И эти решения кратки и понятны, и не используют различные шаблонные заготовки, которые в целом в ходу в спортивном программировании. Это еще одно подтверждение, что даже для алгоритмических задач "неудобный" язык не является проблемой в написании быстрой и понятной программы.

P.P.S. Один мой друг учавствовал в раунде 1, сидя с ноутом на полу в аэропорту через Wifi. Это не помешало ему получить 127-е место и проход в следующий раунд.

5 комментариев:

  1. Raund-1_А в 4 утра был по киевскому, а у вас наверно часов в 5?:)
    Сам участвовал в B,C и тоже только первые решил, но для меня наибольшие проблемы вызывало понимание задач, что и бесило сильно (и дело не только в моём среднем английском)

    ОтветитьУдалить
  2. Round 1A у меня был в 2 часа ночи. Более менее удобно. А вот B и С были днем.

    Согласен, на родном то проще понимать, и времени меньше уходит. А в задачах каждое слово важно понимать правильно. Поэтому подсознательно и тянешься на сайты, где есть русский типа acmp.ru или codeforces.ru. Но увы, английский в этом деле -- стандарт.

    ОтветитьУдалить
  3. Участвовал в B,C, оба раза первые две зада полностью сдал, оба раза над 2ой задачей долго думал, хотя решения простейшие оказались. Прошел в следующий раунд.
    В Code Jam формулировки задач витееватее, то ли дело в TopCoder - все задачи лаконичные, написаны на Simple English, а с ACM задачами еще сложнее в этом плане, условия по 2-3 страницы не редкость.

    ОтветитьУдалить
  4. Пчему Вы считаете что Дельфи(паскаль) неудобный язык?

    ОтветитьУдалить
  5. @X: Сугубо мое личное мнение: что мне не нравится в Паскале или Дельфи: об'явление переменных в начале блока, отсутствие перегрузки операторов, странный приоритет операций (необходимость скобок для "if (a=b) or (a=c)" вместо "if a=b or a=b", общая многословность. Вкратце так.

    ОтветитьУдалить