Dropbox

Как-то осознал, что реально подсел на Dropbox.

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

Все файлы имеют историю ревизий, и их можно делать выборочно публичными. Почти как Google Docs, только есть автоматическое синхронизирование с локальными файлами.

Недавно вышел официальный клиент Dropbox для Android, так что теперь файлы еще и доступны прямо с телефона. Захотел в метро исходничек глянуть или pdf-ку - пожалуйста.

Конечно, класть в эту папку более менее конфиденциальные данные было бы глупо, хотя Dropbox гарантирует их сохранность, но для рабочих документов и исходников - это самое оно. Они и так у меня почти все лежат на Google Code.

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

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

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

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

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’ах).

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

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

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

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

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

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

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

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

Плавающая точка уплыла

Решал одну задачу на UVa Online Judge. Долго не мог найти проблему и проверял алгоритм.

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

#include <iostream>
#include <cmath>
using namespace std;

int main(int argc, char* argv[]) {
  double f = 1.15;
  int a = f * 100.0 + 0.1E-9;
  int b = f * 100.0;
  cout << "a = " << a << endl;
  cout << "b = " << b << endl;
  return 0;
}

Я ожидал два числа 115.

Нет, у меня на VS2008 она печатает:

a = 115
b = 114

Вот такие дела.

Update:
Кстати, если попробовать так:

#include <iostream>
#include <cmath>
using namespace std;

int main(int argc, char* argv[]) {
  double f = 1.15;
  int a = f * 100.0 + 0.1E-9;
  int b = f * 100.0;
  cout << "a = " << a << endl;
  cout << "b = " << b << endl;
  double f1 = 0.15;
  int a1 = f1 * 100.0 + 0.1E-9;
  int b1 = f1 * 100.0;
  cout << "a1 = " << a1 << endl;
  cout << "b1 = " << b1 << endl;
  return 0;
}

то результат будет:

a = 115
b = 114
a1 = 15
b1 = 15

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

На ТопКодере есть отличная статья на эту тему (часть 1 и часть 2). Все кратко и по делу.