Количество пересечений в двудольном графе

Это очередной пост из серии "записки дилетанта о спортивном программировании". Тут как в том анекдоте: "Лев Толстой очень любил играть на балалайке, но не умел. Порой пишет очередную главу, а сам думает: тренди-бренди, тренди-бренди...". В общем, точно про меня и спортивное программирование.

Итак, задача с крайне простой постановкой.

Дан произвольный двудольный граф: "n" вершин слева, "m" справа и некоторое количество дуг. Требуется ответить на вопрос: сколько раз дуги графа пересекаются.

В данном примере n=5, m=4, десять дуг: 1-1, 1-2, 2-1, 2-2, 3-3, 4-1, 4-3, 5-1, 5-2, 5-4, количество пересечений: 10.

Факт пересения рассматривается всегда попарно. Например, если уж так случилось, и три дуги пересекаются в одной геометрической точке, формально пересечений все равно три, а не одно.

Задача имеет решение за O(n*m).

Challenge 24 Pre Electronic Сontest

В эту субботу наша команда в составе Leonid, Lomir и меня "разогревались" на тестовом раунде "Challenge 24 Contest". Задачи уже доступны. В этом раунде не было никакого рейтинга, а просто можно было ознакомиться с правилами и системой. Хотя лично для меня задачи были вполне себе серьезные. Например, P, конечно, совсем простая, но остальные для меня вполне реальны.

Мне нравится этот контест тем, что он не заточен исключительно на алгоритмические задачи. Например, в Q надо было сделать хорошую эвристику, в R - типа взломать код, ну а S - это алгоритм.

Я по-пенсионерски попросился решать R. В итоге написал какой-то невообразимый велосипед на С++, которым таки получилось сделать играемый wav, прослушать сообщения и сдать задачу, и только потом, немного успокоившись, на питоне получилась короткая программа, делающая чистые 16-битные wav'ы.

import wave, struct

def make_soundfile(sample, freq, fname):
    frate = 7000

    data_size = len(sample)

    sine_list = []
    for x in sample:
        sine_list.append(float(x) / 2 * 32768)

    wav_file = wave.open(fname + ".wav", "w")

    nchannels = 1
    sampwidth = 2
    framerate = int(frate)
    nframes = data_size
    comptype = "NONE"
    compname = "not compressed"

    wav_file.setparams((nchannels, sampwidth, framerate, nframes, comptype, compname))
    for s in sine_list:
        wav_file.writeframes(struct.pack('h', int(s)))
    wav_file.close()

 for n in range(1, 11):
    fname = "test-%02d.tst" % n
    print fname
    sample = open(fname).readlines()
    sample = sample[1:]
    freq = len(sample)
    make_soundfile(sample, freq, fname)

Конечно, авторское решение было еще проще.

awk 'NR > 1 {printf "%c",int(128*($1+1))}' *.in >/dev/dsp

Погдядим, что будет в реальном раунде в эту субботу.

Интервью с домашним заданием

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

И вовсе не потому, что я часто люблю менять работу (совсем наоборот). А потому, что в этом процессе есть несколько полезных сторон.

Для начала – это вызов. Задача, которую надо решить (ведь помните, что мы должны быть разносторонними, а не только на С++ программировать). Это как участвовать в ТопКодере. У меня это всегда легкое (а порой и не очень легкое) волнение и ощущение бабочек внизу живота. Предлагаемая задача не решается в лоб академическими знаниями и всегда требует, чтобы ты себя проявил.

Затем идет чисто практическая сторона – опыт, который никаким другим способом не получить. Даже если тебя все устраивает на текущей работе или собственном бизнесе, всякое может случиться, и иметь опыт устройства на работу (как бы формально и прагматично это не звучало) иметь стоит. К тому же усилий для его получения надо не так и много. Чтобы успешно пройти интервью – надо уметь это делать. Хоть многие компании и заявляют, что они целенаправленно набирают специалистов, а не специалистов по устройству на работу – это блеф. Люди всегда оценивают людей. И порой надо догадаться, что за критерии отбора скрыты за вопросами и задачами, предлагаемыми тебе на интервью.

Например, многие думают, что все интервьюеры – это супер/мега/экстра спецы, которые видят тебя насквозь. И причина этому – просто что «он» задает тебе вопросы, а не ты ему. Хотя в большинстве случаев, особенно в больших компаниях, интервьюируют обычные разработчики (а некоторые и без особого желания), и если догадаешься, что ему надо – успех гарантирован.

Лично я понял, увы, не сразу, насколько важно быть не только технически подкованным, но и собрать максимально информации и компании, а по возможности и о предстоящем интервьюере. Благо сейчас у всех есть блоги, ЖЖ, Фейсбук, ЛинкедИн, МайСпейс и т.д.

А любой, даже самый позорный провал – это крайне полезная пища для самоанализа и понимания путей развития. Лично я всегда тщательно анализирую все интервью, разбираю задачи, на которых облажался, и много раз это возвращалось – люди ленивы, и не все интервьюеры утруждаются придумыванием задач, так что шанс получить однажды нерешенную задачу в другом месте очень даже велик.

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

Ладно, это лирика.

Хочу поделиться интересным примером.

Интервьюировался я недавно в одной небольшой трейдинговой фирме на позицию обычного разработчика на С++. Сначала было очень короткое пятнадцатиминутное телефонное интервью, которое я легко прошел (но увы, я не вынес из него всей полезной информации – см. ниже). Стандартный набор: С++, multithreading и пару вопросов про сложность. Под занавес товарищ ненавязчиво спросил, какими скриптовыми и функциональными языками я в принципе владею и интересуюсь.

Затем, они мне прислали домашнее задание.

Суть задачи: есть шахматная доска MxN и набор фигур: короли, ферзи, слоны, кони и ладьи (каждой фигуры есть некоторое количество). Пешек нет, и цвет фигур не имеет значения. Надо сгенерировать все возможные расстановки данных фигур на поле. В расстановке должны участвовать в точности все данные фигуры.

Было дано несколько простых тестовых данных. Для задачи большой размерности (поле 7 на 7, 2 короля, 2 ферзя, 2 слона и одна ладья) надо только вывести количество возможных позиций.

И далее было самое главное ограничение: можно писать задачу на любом языке, кроме C, C++, C#, Java, Python, PHP, Pascal.

Срок – неделя.

Я сначала почесал репу (вроде все выглядит как перебор с возвратами, и надо только позаботиться об исключении повторяющихся конфигураций), написал все сначала, конечно, на С++, отладил алгоритм. И стал думать, на чем мне сдавать задачу. Решил на Go. Написал, проверил. Результаты совпадают.

Отправил. Приходит ответ, что все неплохо, но типа мы ищем человека с более оригинальным подходом, чем использование С-подобного языка Go, когда мы явно не рекомендовали использовать императивные языки, тем более из семейства С, и ожидали реализацию на каком-то скриптовом или функциональном языке. Увы, отказ.

Ну, в общем, суть понятна. Задача была не в задаче, а в «показать себя разносторонним программистом», не который если что, так расчехляет С++.

Я поблагодарил их за время, а себя записал еще одно поражение из-за недостаточного анализа требований, пусть и весьма расплывчатых.

Вот.

P.S. Для желающих – исходники мой оригинальной программы на С++. Там же есть версия на Go, но плюсовый вариант содержит самый быстрый алгоритм, который я сумел придумать.

У меня больше нет идей, чтобы еще можно ускорить.

Желающие могут попробовать. Было бы очень интересно время работы теста #3.

Тесты (можно и добавлять свои) и проверяющая система уже встроены прямо в исходник. Его можно скомпилировать:

cl /O2 /EHsc problem.cpp

У меня печатается:

Case #0 OK (line 235)
Case #1 OK (line 248)
Case #2 OK (line 271)
Case #3 OK (line 318) time 1.495s

Для своей версии вам надо переписать функцию “solve()”. Присваивая переменной «problem_filter» значения, отличные от «-1», можно запускать не все тесты, а по одному.

Вообще, я спользую эту мини проверяющую систему для олимпиадных задач. Предложения приветствуются.

Проба на Эрланге

Решал я тут одну красивую задачу. Решение - рекурсивная функция, динамическое программирование.

Для эксперимента написал свою первую программу на Эрланге как решение этой задачи.

Вот оригинал на C++ (рекурсия с кешированием):

bignum f(int n, int k, int t, int& K, vector<vector<vector<bignum> > >& dp) {
  if (n == 0 && k == 0 && t == 0) return 1;
  if (n == 0 || k < 0) return 0;

  if (!(dp[t][n][k] == -1)) return dp[t][n][k];

  bignum ans = 0;

  if (k < K) {
    ans = ans + f(n - 1, k - 1, t, K, dp);
    if (t == 1 || (t == 0 && k < K - 1))
      ans = ans + f(n - 1, k + 1, t, K, dp);
  }

  if (t == 1 && k == K) {
    ans = ans + f(n - 1, k - 1, 0, K, dp);
    ans = ans + f(n - 1, k - 1, 1, K, dp);
  }

  dp[t][n][k] = ans;
  return ans;
}

А теперь Эрланг:

main(_) ->
  N = 50, K = 25,
  io:format("~w\n", [rbs(2*N, 0, 1, K)]).

rbs(0, 0, 0, _) -> 1;
rbs(0, _, _, _) -> 0;
rbs(_, K, _, _) when K < 0 -> 0;

rbs(N, K, 0, MAX_K) ->
  if 
    K < MAX_K-1 -> rbs(N-1, K-1, 0, MAX_K) + rbs(N-1, K+1, 0, MAX_K);
    K < MAX_K   -> rbs(N-1, K-1, 0, MAX_K);
    K =:= MAX_K -> 0
  end;

rbs(N, K, 1, MAX_K) ->
  if
    K < MAX_K   -> rbs(N-1, K-1, 1, MAX_K) + rbs(N-1, K+1, 1, MAX_K);
    K =:= MAX_K -> rbs(N-1, K-1, 0, MAX_K) + rbs(N-1, K-1, 1, MAX_K)
  end.

Красиво, а?

Но вот увы, кеширование результатов пришлось делать тоже вручную, так как без нее программа имеет экспоненциальное время. Так что итоговый вариант выглядит так:

#!/usr/bin/env escript

main(_) ->
  N = 50, K = 25,
  io:format("~w\n", [rbs(2*N, 0, 1, K)]).

rbs(0, 0, 0, _) -> 1;
rbs(0, _, _, _) -> 0;
rbs(_, K, _, _) when K < 0 -> 0;

rbs(N, K, 0, MAX_K) ->
  if 
    K < MAX_K-1 -> rbs_memo(N-1, K-1, 0, MAX_K) + rbs_memo(N-1, K+1, 0, MAX_K);
    K < MAX_K   -> rbs_memo(N-1, K-1, 0, MAX_K);
    K =:= MAX_K -> 0
  end;

rbs(N, K, 1, MAX_K) ->
  if
    K < MAX_K   -> rbs_memo(N-1, K-1, 1, MAX_K) + rbs_memo(N-1, K+1, 1, MAX_K);
    K =:= MAX_K -> rbs_memo(N-1, K-1, 0, MAX_K) + rbs_memo(N-1, K-1, 1, MAX_K)
  end.

rbs_memo(N, K, T, MAX_K) ->
  Name = rbs,
  case ets:info(Name) of
    undefined ->
      ets:new(Name, [public, named_table]);
    _ -> true
  end,
  Key = {N, K, T, MAX_K},
  case ets:lookup(Name, Key) of
    [] ->
      Val = rbs(N, K, T, MAX_K),
      ets:insert(Name, {Key, Val}),
      Val;
    [{_, Val}] -> Val;
    Else -> Else
  end.

Странно, ведь можно было бы заложить кеширование прямо в языке. Ведь когда функция вызывается повторно с теми же самыми аргументами, то очевидно, что результат будет такой же (ибо Эрланг - это "чистый" функциональный язык, и side effects тут исключены). Но в целом функция кеширования весьма универсальна и ее можно быстро адаптировать для других ситуаций.

По времени выполнения эрланговый вариант не уступает C++. При это надо учесть, что Эгланге по умочанию арифметика "длинная", а в С++ мне пришлось использовать доморощенный класс bignum.

О том, как я «ломал» RSA

Решал я как-то очередную задачу:

Будем говорить, что число a лучше числа b, если сумма цифр a больше суммы цифр числа b, а в случае равенства сумм их цифр, если число a меньше числа b. Например, число 124 лучше числа 123, так как у первого из них сумма цифр равна семи, а у второго – шести. Также, число 3 лучше числа 111, так как у них равны суммы цифр, но первое из них меньше.

Дано число n (1 ≤ n ≤ 10^5). Найдите такой его делитель (само число n и единица считаются делителями числа n), который лучше любого другого делителя числа n.

Простая задача: ищем все делители n, у каждого делителя считаем сумму цифр, и среди найденного выделяем все делители с минимальной суммой, и уже среди них находим минимальное по значению. Просто надо аккуратно запрограммировать.

Я все сделал, и решение прошло.

Далее была вторая задача:

Будем говорить, что число a лучше числа b, если сумма цифр a больше суммы цифр числа b, а в случае равенства сумм их цифр, если число a меньше числа b. Например, число 124 лучше числа 123, так как у первого из них сумма цифр равна семи, а у второго — шести. Также, число 3 лучше числа 111, так как у них равны суммы цифр, но первое из них меньше.

Дано число n (1 ≤ n ≤ 10^5000). Найдите такой его делитель d (само число n и единица считаются делителями числа n), что любой другой делитель c числа n лучше, чем d.

По сути, такая же задача, что и предыдущая – просто нужно в паре мест поменять «больше» на «меньше» и наоборот. Я поменял, и на небольших тестах решение прошло.

Но тут я замечаю, что в это задаче верхнее ограничение на n какое-то очень большое. Я заменяют тип «int» на класс «длинной» арифметики (5000 тысяч знаков – пустяк, было и более) и пробую: на малых тестах работает, значит, алгоритм верный.

Посылаю решение, и конечно, получаю ответ «Time limit exceeded». После небольшого раздумья становится ясно, что слишком много надо считать, и подход в целом неправильный.

Пишу письмо Leonid’у с просьбой прояснить ситуацию.

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

В итоге выяснилось, что данная задача решается не только без «длинной» арифметики, но даже и без короткой, одним циклом в пару строк. Просто надо понять, что за тип чисел просят найти.

Сумма цифр числа в Excel'е

Разбираясь с задачей из последней SRM'ки, решил я посмотреть, как будет выглядеть график у функции Y=D(X), где X - натуральное число, а D(X) - сумма цифр его десятичной записи. Оказывается, вот такой хитрой формулой:

=SUMPRODUCT(--MID(A1,ROW(INDIRECT("1:" & LEN(A1))),1))

можно в Экселе посчитать этот самый D(X). Ума не приложу, что это формула значит, но точно работает.

А вот и сам график, кому интересно:

TopCoder SRM 473. Уроки

Сегодня ночью была очередная SRM’ка. Как водится, я узнал сам про себя много нового. Например, я изобрел совершенно уникальный и доселе невиданный метод решения линейной системы из двух уравнений.

Итак, по порядку. Дивизион 2, 75 минут, 3 задачи + 10 минут после на взлом (challenge) чужих решений.

Задача номер 1.

Есть набор куриц и коров. У каждой курицы две ноги и одна голова. У коровы четыре ноги и одна голова. Даны два числа: количество ног и количество голов (каждое число от 1 до 10^6). Надо ответить на вопрос: возможно ли существования некоторого количества куриц и коров при заданном количестве ног и голов.

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

Все просто. Но! В два часа ночи я родил иной подход: перебор! (для системы-то из двух линейных уравнений). Я даже помню ход свох мыслей: так как количество только 10^6, значит можно перебрать все возможные значение количество куриц. Для каждого значения вычислить количество коров, исходя их количество ног и из количество голов. Полученные значения сравнить, и если совпадают, значит найдено возможное решение.

Вот такой вот «мега»-подход. В ходе челленджа я просмотрел решения всех участников в комнате, но такого «оригинального» решения не видел. Представляю круглые глаза тех, что пытался зачеленджить мое решение, когда они видели решение двух линейных уравнений перебором.

Кстати, решение в итоге не прошло системных тестов. И к лучшему.

Задача номер 2.

Дано неограниченное поле, в некоторой точке которого стоит робот. Дана программа для робота – строка, каждый символ которой – команда: «S» - шаг вперед на какую-то константную величину, «L» - поворот налево, «R» - поворот направо. Требуется сказать, будет ли траектория робота, двигающего по этой программе, ограничена конечной окружностью, или робот будет постоянно удалятся от исходной точки. Длина программы для робота до 250 символов.

Как один из вариантов решения: можно прогнать 4 итерации программы, и если хотя б после одной, робот вернется в исходную точку, то траектория робота ограничена.

Решение есть. Теперь его надо запрограммировать. Надо было сделать имитацию выполнения программы, то есть команды робота «вперед», «влево» и «вправо».

Приведу фрагмент программы, которую родил мой воспаленный мозг ночью:

...
      if (cmd == 'S') { 
        x += dx; 
        y += dy; 
      } else { 
        if (cmd == 'L' && dx ==  0 && dy ==  1) dx = -1, dy =  0; 
        else if (cmd == 'R' && dx ==  0 && dy ==  1) dx = +1, dy =  0; 
        else if (cmd == 'L' && dx ==  1 && dy ==  0) dx =  0, dy =  1; 
        else if (cmd == 'R' && dx ==  1 && dy ==  0) dx =  0, dy = -1; 
        else if (cmd == 'L' && dx ==  0 && dy == -1) dx =  1, dy =  0; 
        else if (cmd == 'R' && dx ==  0 && dy == -1) dx = -1, dy =  0; 
        else if (cmd == 'L' && dx == -1 && dy ==  0) dx =  0, dy = -1; 
        else if (cmd == 'R' && dx == -1 && dy ==  0) dx =  0, dy =  1; 
...

Даже сейчас я не могу смотреть на это без содрогания. Надо то было всего:

...
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };
int d = 0;
...
if (cmd == ‘S’) {
  x += dx[d];
  y += dy[d];
} if (cmd == ‘L’)
  d = (d + 4 - 1) % 4;
else if (cmd == ‘R’)
  d = (d + 1) % 4;
...

И все!

Но увы. Когда время ограничено, на ум приходят странные решения.

Хотя мое решение прошло системные тесты, от его вида как-то грустно.

Задача 3.

Дано определение числа Y: Y = X/D(X). X – натуральное число, D(X) – сумма цифр в десятичной записи числа Х. Если Y получается целым, то читается, то Y есть «предок» числа X. Дан интевал чисел от «а» до «b» (каждое от 0 до 10^9), но «a-b» всегда не более 10000.

Спрашивается, сколько есть на данном интервале есть числе Y, у которых нет предка (то есть нет такого Х, чтобы Y был целым).

Итак, для решение перебираем все значения Y от «а» до «b» (их не более 10000). Для каждого Y числа надо проверить, если ли у него «предок». Ясно, что заменатель D(X) принимает только значения от 1 до 81 (число с максимальной суммой цифр – это 999999999, а их сумма 81). Итак, делаем внутренний цикл от 1 до 81, и вычисляем X как X=Y*i (i от 1 до 81). Далее по факту равенста i и D(X) (надо вычислить сумму цифр, составляющих текущее X) можно понять, если ли у текущего Y предок или нет.

Всего итераций будет максимум 10^4 * 81 * 9 ~= 10^6 = 1000000, что вполне реально.

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

Итак, выводы.

А вывод простой – работая под жестким временным ограничением, порой самые очевидные вещи вылетают из головы, не говоря уже об «экзотике», типа хитрых алгоритмов. Но так же вывод – так как решения таки были, то значит есть потенциал и закодить из вовремя.

Заснуть под утро я так уже не смог. Все думал.

Анализатор последовательностей

Многие задачи в спортивном программировании из раздела динамического программирования сводятся к задаче отыскания формулы какой-либо последовательности.

Формула может быть в замкнутом виде, когда ты просто подставляешь аргументы и разом получаешь результат за время O(1), или в динамической, рекуррентной форме, когда для вычисления i-го члена надо вычислить предыдующие.

Классический пример замкнутой формы - это сумма ряда n положительных чисел:

S(n)=n*(n-1)/2.

А для динамической, или рекуррентной формы - это, например, формула для i-го члена последовательности чисел Фибонначи:

F(i)=F(i-1)+F(i-2).

Например, вот такая задача (для школьников!).

Есть N чисел от 1 до N. Требуется разместить эти числа в ряд слева направо. Первым числом всегда идет 1. Каждое последующее может отличаться от предыдущего не больше, чем на 2. Например:

1 2 3 4 5 ...
1 3 2 4 5 ...
1 3 5 4 2 ...

и т.д. (эта задача есть на Тимусе).

Требудется найти количество возможных размещений по этому правилу для N чисел. N от 1 до 55.

Просто перебором в лоб не получится, так как вариантов будет 55! ~ 10^73, а времени дается всего одна секунда.

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

А вот теперь подходим к сути поста. Недавно я наткнулся на волшебный сайт - Онлайн-энциклопедия целочисленных последовательностей. Там ты просто вводишь несколько известных тебе членов последовательности, а сайт по большой базе данных ищет совпадения с какими-либо известными последовательностями, и в случае наличия такого совпадения, дает исчерпывающую информацию - формулы, статистический анализ и т.д.

Итак, я нашел пяток первых значений решения задачи перебором - генерировал все возможные перестановки для i членов, для i от 1 до 8, и проверяя для каждой перестановки правильность выполнения условий размещения, считал количество вариантов.

В итоге, магия произошла. Когда я ввел вычисленные первые элементы последовательности в этот анализатор, мне просто сказали, что формула для i-го члена этой последовательсти: a(n)=a(n-1)+a(n-3)+1. И все! И по данной формуле задача решается пулей одним циклом за O(N).

Конечно, для реальных соревнований такое метод не годится, так как никто не даст доступа в интернет. Да и цель задачи несколько иная - научиться выводить такие динамические соотношения самому.

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

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

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

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

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

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-е место и проход в следующий раунд.

Судоку для программистов или олимпиадные задачи

Последнее время радикально подсел на алгоритмические задачки по программированию.

Каким-то чудом и к великому сожалению сейчас вся эта тема олимпиадного программирования сильно меня не зацепила в школе и институте. Хотя там для этого было бы больше времени.

И самое что в этом всем отрезвляющие, что порой ступор наступает на казалось бы «очевидных» и типа «уже когда-то давно изученных» тобой задачах. Например, практически над каждой из серии «задач для обучения и закрепления материала» по динамическому программированию я изрядно чесал репу, хотя выглядят конкретно они весьма академично. И практически каждую я засабмитил далеко не с первого раза. Думается, что на том же ТопКодере каждая из них была бы первой задачей (то есть самой простой).

Вообще появляется некоторая зависимость. Зависимость от количества решенных задач. После нескольких успешных сабмитов хочется еще, еще и еще, а задачи становятся сложнее и сложнее. Своеобразное программистское судоку.

В принципе, тут необязательно маньячить на онлайн матчах, когда счет идет еще на время. Тут ты просто решаешь в свое удовольствие. Хотя, может желание соревновательности приходит с появлением опыта.

И все это – абсолютное знание. Твой единственный судья – это программа проверки результата и тестовые наборы данных, которые одинаковы для всех. Говорят, что на том же ТопКодере есть пути нечестного поднятия рейтинга, но очень несильно. Если посмотреть на топ-листы независимых онлайновых контестов, то можно увидеть там одни и те же имена. Неужели все эти люди знают как «читить» на всех сайтах? Конечно нет.

Притягивает тут абсолютность знания. Все что нужно, чтобы выиграть – это просто решить задачи быстрее всех. Казалось бы, что может быть проще. Как сказал мне тут один товарищ, что нейроны необходимо постоянно задр***вать, а иначе они теряют эластичность.

Сайтов для онлайнового решения задач много. Я пока остановился на Школа программиста, Timus Online Judge, UVa Online Judge (классика жанра), Codeforces и, конечно, TopCoder (пока только в practice room’ах).

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

Единственное что важно, особенно сначала, когда можно удобно выбирать задачи по тематике и сложности. Вот тут и стоит покопаться на нескольких системах, ибо каталоги могут быть устроены по-разному.

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

Если вместо сотни красивых слов в резюме про где и как человек учился и над чем замечательным работал, будет просто указана ссылка на профайл того же ТопКодера, то это будет в сотни раз полезнее. Там тебе и примеры кода, и тематика решенных задач, время из решения (после этого можно не спрашивать, как «человек работает под стрессом»), и, что очень важно с моей точки зрения – страсть к программированию, увлеченность (а как иначе можно объяснить многолетнее постоянное участие в «пустой трате времени», как спортивное программирование).

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

Например, другой товарищ рассказывал, когда его стандартно попросили у нас на интервью нарисовать функцию для вычисления чисел Фибоначчи разными способами – рекурсивно, рекурсивно с хвостовой рекурсией, а затем просто циклом, он написал матричный вариант через производящую функцию, который работает за логарифмическое время, вместо линейного. У товарища, кстати, неплохой рейтинг на ТопКодере.

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

В общем, решайте задачи, тренируйтесь, держите себя в форме.