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

Автор Alex_KPR, 5 месяцев назад, По-русски

Всем привет! Предлагаю челлендж. :)

В двух словах — нужно:

  1. Собрать проект DevilutionX — это кроссплатформенный порт Diablo 1 + Hellfire — и научиться запускать его, (вам для этого потребуется оригинал игры).
  2. Создать в мультиплеере Hellfire персонажа и познакомиться с игрой.
  3. Засекайте время с момента открытия исходников: нужно суметь получить несколько колец под названием Obsidian Ring of the Zodiac.
  4. Убедиться, что эти кольца в ванильной сборке валидны, не мутируют, не исчезают и не приводят к крэшу клиента.
  5. Пользоваться AI нельзя.

Эта задача по формату была бы близка финалу Challenge24. Но я её считаю лучшей из известных мне задач для собеседования инженера-программиста 10 лет назад: она проверяет способность быстро разобраться в незнакомом коде, придумать оптимальное решение и написать его.

Полная версия условия, аргументы в пользу этой задачи как "идеальной", мой опыт собеседований, подробный анализ решений и мысли по поводу — всё здесь: kouprin.com/notes/obzod.

Напишите в комментариях, сколько вам потребовалось времени. :)

Спасибо al13n, Gassa и qwerty787788 за идеи, решения и бета-тестирование. Спасибо парням, делающим DevilutionX, — но я никого не знаю из них и не смогу ответить на вопросы о проекте.

game screenshot


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

  1. Мастер может не сбилдиться. Несмотря на то, что ребята официально поддерживают около 20 платформ, бывают необъяснимые проблемы даже на убунту.
  2. Ребята в любой момент могут скрыть репозиторий или что-нибудь сделать ещё. По большому счёту, челлендж актуален только к сегодняшнему коммиту — и может протухнуть со временем из-за изменений в кодовой базе и возможных расхождениях в зависимостях. Спешите. :)
  3. Я мог что-то не учесть и драматически облажаться. В таком случае — извините. :)

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

Удачи!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +20
  • Проголосовать: не нравится

Автор Alex_KPR, 15 лет назад, По-русски

Блэкджек (задача A, 2-ой дивизион). Автор задачи - Alex_KPR

 

 

Очевидно, что масти никакой роли не играют. Рассмотрим теперь подробно все случаи:

[0 - 10] — ноль способов.
[11] — четыре способа, используя тузы.
[12 - 19] — четыре способа, используя карты от 2 до 9.
[20] — 15 способов, они описаны в примечании условия задачи.
[21] — четыре способа, используя тузы.
[22 - 25] — ноль способов.

 

 

Сложность алгоритма — O(1).

 

Полный текст и комментарии »

Разбор задач Codeforces Beta Round 80 (Div. 2 Only)
  • Проголосовать: нравится
  • +24
  • Проголосовать: не нравится

Автор Alex_KPR, 15 лет назад, По-русски

Всем привет!

Вот и пришло время очередного, уже 80-го по счёту раунда на Codeforces.

Контест готовили: Alex_KPR, winger, RAD, Connector, it4.kp. Надеюсь, что всё пройдёт гладко, и всем понравятся задачи про пробуждение Ктулху, ограбление корована, унылость штанов шахтёра и, конечно же, про очаровашку Хексадесимал.

Кстати, Connector сегодня отмечает свой день варенья — давайте дружно его поздравим с праздником! =)

Всем удачи и приятного времяпрепровождения!
_____________________________________

Спасибо всем за участие! =)

Подведём итоги раунда. В первую десятку в первом дивизионе вошли:

Место
Кто
1
 SergeiRogulenko
2
 hos.lyric
3
 Romka
4
 neal
5
 sdya
6
 KADR
7
 ftiasch
8
 niyaznigmatul
9
 dolphinigle
10
 AleX

Стоит отметить, что с задачей E справилось всего двое: победитель раунда SergeiRogulenko, и MBabin, занявший 76-е место.

Первые три места во втором дивизионе заняли:

Место
Кто
1
 anrieff
2
 zplinti1
3
 Efgen

Поздравляем победителей и желаем всем удачи в следующем раунде!

Официальный разбор будет опубликован позднее. Стоит отметить, что AlexanderBolshakov уже опубликовал свой разбор на страницах Codeforces.

Спасибо Delinur за перевод условий на английский язык!
_____________________________________

Опубликован разбор.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +208
  • Проголосовать: не нравится

Автор Alex_KPR, 15 лет назад, По-русски

Предсказание Панорамикса (задача A, 2-ой дивизион). Автор задачи - Alex_KPR

 

 

В начале условия задачи подробно описано, что называется простым числом, и что называется следующим после x простым числом. Суть задачи сводилась к тому, чтобы проверить, является ли m следующим после n простым числом.

Поскольку n гарантированно простое, нужно проверить два случая:

1. Число m является простым, и

2. Между n и m нет других простых чисел

Действительно, если между n и m есть некоторое простое число k, то m уже никак не может быть следующим после n простым. Ограничения в этой задаче небольшие, поэтому решать её можно следующим способом:

for(int i=n+1;i<=m;i++)
{
    if (prime(i))
    {
        if (i==m) return "YES"; else return "NO";
    }
}
return "NO";

где prime(i) - любая возможная проверка числа на простоту.

Другое простое решение этой задачи - учесть тот факт, что ограничения не превышают 50. Можно найти все пары чисел n и m вручную и написать решение в виде серии условий, примерно так:

if (n==2 && m==3) return "YES";
else if (n==3 && m==5) return "YES";
else ...
else if (n==43 && m==47) return "YES";
else return "NO";

Такое решение тоже проходило все тесты.

 

 

Асимптотика зависит от конкретной реализации и варьируется от O(1) до O(n + m).

Если вы не знаете, почему ваше решение получает вердикт "wrong answer", то возможно, вам стоит проверить своё решение на тесте "2 5".

 

Полный текст и комментарии »

Разбор задач Codeforces Beta Round 69 (Div. 1 Only)
Разбор задач Codeforces Beta Round 69 (Div. 2 Only)
  • Проголосовать: нравится
  • +41
  • Проголосовать: не нравится

Автор Alex_KPR, 15 лет назад, По-русски
Доброе время суток!

Рад всех приветствовать на Codeforces Beta Round #69. Как вы уже догадались, это будет не совсем обычный контест.

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

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

И ещё: разбалловка в первом дивизионе будет 500-1000-1500-2000-2000. У второго дивизиона будет классический вариант 500-1000-1500-2000-2500.

Раунд готовили Alex_KPR, dagon и Marishka. Много полезных вещей делали RAD, it4.kp. Задачи переводила Мария Белова. Контролировал весь процесс Майк Мирзаянов.

Всем удачи! =)
_____________________________________

Не забудьте проголосовать, понравилось ли вам разделение по дивизионам, или нет =)
_____________________________________

Первые десять мест в первом дивизионе заняли:
Место
Кто
1
 vepifanov
2
 KADR
3
 hos.lyric
4
 Zhukov_Dmitry
5
 e-maxx
6
 Romka
7
 ivan.popelyshev
8
 Shef
9
 RAVEman
10
 ktuan

Первые три места во втором дивизионе заняли:
Место
Кто
1
 Gluk
2
 nvilcins
3
 piloop

Поздравляем победителей и желаем всем удачи в следующем раунде!
_____________________________________

Опубликован разбор.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +177
  • Проголосовать: не нравится

Автор Alex_KPR, 16 лет назад, По-русски
Задача A. Сон Студента.

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

Если мальчик пойдёт слева от девочки, то он возьмёт своей правой рукой её левую руку, а оставшиеся руки (левая мальчика и правая девочки) окажутся незадействованными. Если наоборот, мальчик пойдёт справа, то он возьмёт своей левой рукой правую руку девочки. Это написано в условии. Осталось проверить, "совместимы" ли руки для прогулки хотя бы в одном из этих случаев.

Полный текст и комментарии »

Разбор задач Codeforces Beta Round 58
  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

Автор Alex_KPR, 16 лет назад, По-русски
Добрый вечер!

Рад всех приветствовать на 58-м раунде. Задачи к сегодняшнему контесту готовили коллективы команд Orel STU и NNSU.

Задачи тура будут посвящены забавным жизненным ситуациям: вы встретитесь с самым суровым преподавателем в мире, вернётесь в средние века, разрешите противоборство крупных IT-компаний, выпустите Вселенское Зло из Большого Адронного Коллайдера и решите проблему червяка Арни, про которого обычно говорят: "Арни огорчает твой жим". =)

Спасибо коллективу Codeforces, который помог подготовить предстоящий контест.

Надеюсь, что раунд вам понравится! Удачи!



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



Подведены результаты контеста. И снова Геннадий одержал! =)

Спасибо всем, кто участвовал в раунде!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +38
  • Проголосовать: не нравится

Автор Alex_KPR, 17 лет назад, По-русски

Всем привет и добро пожаловать на Codeforces Beta Round #9!

Если не случится ничего страшного, то он начнётся в 15:00 по московскому времени.

Сегодняшним автором задач буду я. :) Задачи старался сделать легкочитаемыми и забавными. Огромное спасибо нужно сказать Мише Мирзаянову (за выбор задач к контесту и организацию соревнования), Игорю Кудряшову (за тщательную проверку авторских решений и написание генераторов тестов), Диме Матову (за исправление всего, что можно было исправить :)) и, конечно же, Юле Сатушиной (за прекрасный перевод условий).

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

Надеюсь, что контест Вам понравится, уважаемые участники! Прошу оставлять здесь свои предложения и пожелания.

Удачи!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +23
  • Проголосовать: не нравится