ivan.popelyshev's blog

By ivan.popelyshev, 5 years ago, In Russian,

Спутник и чемпион: как победили русские программисты

Дорогие друзья!

Мы все гении в определённом пространстве — в алгоритмах, ну может быть вообще в CS. Но когда мы лезем в политику — мы котята слепые. Тема на самом деле страшная и волнительная, нервов в это утекает уйма.

Я нисколько не претендую на то чтобы быть супер-осведомлённым, но запостить это я должен.

Дмитрий, я всё отлично понимаю. Но новость о победе и о своих взглядах на этом ресурсе надо было разнести, я могу потом объяснить почему.

 Д.Е.: «Спутник» мне интересен как ресурс, наиболее близкий по политическим взглядам к моим, а также не содержащий фактических ошибок и подлога (по крайней мере которые я бы отловил). Как у человека, который часто ездит в другие города и имеет много знакомых из самых разных частей нашей Родины (в том числе и за пределами текущих государственных границ РФ), многие либеральные ресурсы вызывают у меня недоверие. Как мне верить сайту, который ежедневно рассказывает, что крымчане раскаиваются в своем выборе на референдуме, когда мой знакомый из Крыма говорит мне, что его знакомые и народ в целом вполне довольны текущим положением дел?

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

Так вот. Зачем я это пишу? Чтобы через несколько лет кто-то бампнул тему комментарием "блин, Ваня же нас предупреждал". Про крым я уже что-то писал три года назад в другой теме.

UPD. ещё раз — Дмитрий всё правильно сказал, но статья вышла там где не надо, ну хотя бы на две части надо было разделить.

UPD2. Ладно, Дмитрий не всё правильно сказал, там есть большой подвох который я сам не сразу понял. Оставляю это вам на домашнее задание.

Read more »

 
 
 
 
  • Vote: I like it  
  • -23
  • Vote: I do not like it  

By ivan.popelyshev, 6 years ago, In Russian,

Программисты, инженеры и представители гуманитарных специальностей понадобились армии. Министр обороны России Сергей Шойгу на встрече с ректорами вузов и представителями общественности заявил о начале формирования "научных рот" и пообещал создать талантливым профессионалам все условия для работы.

"Я сегодня по телевидению услышал, что студенты одного из питерских вузов в пятый раз стали чемпионами мира по программированию. Их надо найти. Надо как-то с этими ребятами поработать, потому что они нам очень нужны", — сказал министр, добавив, что военное ведомство готово создать все необходимые условия для работы этих людей.

Утро

Лента

Обсуждение на oper.ru

P.S. Новый шрифт в меню на codeforces — ня-ня-ня!

Read more »

 
 
 
 
  • Vote: I like it  
  • +116
  • Vote: I do not like it  

By ivan.popelyshev, 6 years ago, In Russian,

Собираюсь открыть вакансию Java или JS программиста для игровых проектов. Работаем в Москве, пока что в бизнес-инкубаторе МГУ. В случае очной фулл-тайм работы З/П порядка 100к. В других случаях будем договариваться.

Предупреждаю — если команда не будет отжигать то через три месяца всё кончится. Результат зависит от всех напрямую. Цель — собрать и воспитать крутую команду и взорвать всем мозг своими игрушками.

Обещаю полную жесть, cutting-edge web и mobile-технологии, 24-часовые хакатоны, поездки в другие страны с целью обмена опытом с аналогичными стартапами.

Если кто пропустил — основной проект http://bombermine.com , самая крутая massive multiplayer online retro arcade на вебе.

UPD. немножко слов: netty, GWT, j2objc, angular.js, typescript, firefox OS, Tizen OS.

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +145
  • Vote: I do not like it  

By ivan.popelyshev, 6 years ago, In Russian,

Не читайте, если вы ещё хотите написать тренировку.

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

Краткое условие: дано дерево из N вершин, необходимо найти кол-во способов выбрать 3 вершины так, чтобы попарные расстояния между ними были равны D.

Вот решение, это O(N), вся суть в dfs.

Подвесим дерево.

Для каждой пары (вершина X, число K) будем хранить такую информацию:

  1. количество потомков X на расстоянии K от неё.
  2. количество пар потомков X на расстоянии K от неё, LCP которых находится на расстоянии K - D / 2 от X.

Будем быстро получать эту информацию для очередной вершины по её детям. Окончательный ответ мы будем обновлять в процессе объединения результатов детей, поэтому самое важное — понять именно обновление и получение нужной информации.

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

Чтобы получать нужную информацию через детей, научимся:

  1. Добавлять ребро в начале поддерева. Понятно, что при этом в каждом векторе в начале появляется нолик. Но добавление в начало вектора — штука тормозная, поэтому вектора будем хранить перевёрнутыми, и добавлять нолики в конец.

  2. Соединять два поддерева. Будем добавлять меньшее к большему. Это состоит из нескольких действий:

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

— Обновим второй вектор для случая, когда в каждом поддереве по столице. Ясно, что тогда обе столицы на расстоянии D / 2 от данной вершины.

Кол-во способов это сделать мы легко получим произведением значений первых векторов у поддеревьев в позициях K = D / 2, а затем просто добавим во второй вектор нового поддерева в позицию, соответствующую K = 0.

— Обновим первый вектор. Если вершина одна, то она либо в первом, либо во втором поддереве, так что просто надо сложить первые вектора старых поддеревьев, чтобы получить первый вектор нового.

Всё.

Почему O(N)? Это просто.

Что мы делаем в процессе решения?

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

Больше мы ничего не делаем. А 2-ая операция не может удалить больше, чем сделала 1-ая.

Написание и отладка заняли 20 минут, зашло сразу.

Read more »

 
 
 
 
  • Vote: I like it  
  • +38
  • Vote: I do not like it  

By ivan.popelyshev, 7 years ago, In Russian,

image <-- жать на картинку

Поднимаем пост на хабре! http://habrahabr.ru/post/151961/

Хардкорный текстовый квест про сдачу сессии на мат-мехе СПбГУ пройти не так уж и просто. Действие разворачивается в 1998 году. Выдержка из документации к оригиналу:

«Эта программа — некоторый синтез всех тех эмоций, что получил автор, пытаясь (с грехом пополам) выйти на сессию в конце второго семестра первого курса на мат-мехе. Правда, при этом автор находился в более выгодном положении, чем Вы — центральный персонаж этой игры, которому предстоит получить зачёты по 6-ти предметам практически с нуля.»

image

Процессу портирования посвящён пост в жж.

Официальный сайт mmheroes

Оригинальная игра была сделана на Borland Pascal Дмитрием Петровым (image diam-2003), а портировал её под веб наш товарищ SharpC

UPD.

xxx: "Герои мехмата" или "Сдать сессию и остаться в живых". Остросюжетный пошаговый симулятор мехматянина портирован из глубины веков на Javascript и доступен прямо из браузера. esci.ru/_/mmheroes/
yyy: предлагаю ввести монетизацию - оплати зачёт по смс

Read more »

 
 
 
 
  • Vote: I like it  
  • +111
  • Vote: I do not like it  

By ivan.popelyshev, 7 years ago, translation, In English,

Competition starts at 21 July 20:10

May the Force be with you!

[Ads mode on] Nothing to do before a match? Try bombermine [Ads mode off]

Read more »

 
 
 
 
  • Vote: I like it  
  • +36
  • Vote: I do not like it  

By ivan.popelyshev, 7 years ago, In Russian,

Регулярный кросс-пост из блога sharpc.livejournal.com

Найдите ляп на картинке!

ссылка выше

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

Read more »

 
 
 
 
  • Vote: I like it  
  • -5
  • Vote: I do not like it  

By ivan.popelyshev, 7 years ago, In Russian,

Dart: http://www.dartlang.org/ Kotlin: http://kotlin-demo.jetbrains.com/

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

Google Dart — детище корпорации зла. Напомню что одна попытка скрестить Java с JS у неё уже была — GWT (читается gwit). Исполняется в Dart VM или транслируется в JavaScript.

Dart

Kotlin — разработка JetBrains, собирается и как байт-код и как Javascript. Обратите внимание на примеры с использованием HTML5 canvas. Уже есть интеграция с Ant и Maven. То есть Kotlin можно использовать в сочетании с огромным количеством java-библиотек.

здесь должна быть аналогичная картинка для kotlin, но забыл где я её видел

Как сторонник Java я наверное выберу Kotlin, как патриот я тоже его выберу (его разрабатывают Питерцы). А теперь вопрос: кто с этим уже разбирался и что вы думаете?

UPD. Блин, если минусуете то пишите хотя бы почему.

Read more »

 
 
 
 
  • Vote: I like it  
  • +28
  • Vote: I do not like it  

By ivan.popelyshev, 7 years ago, In Russian,

27-ого апреля состоялся финал соревнования КРОК-2012. Я трагически прогулял 1-ый раунд, и я наверное единственный, кто не нервничал на ивэнте.

Московский офис компании КРОК пустил корни между метро Курская и Площадью Ильича.

После регистрации участников, Михаил Мирзаянов толкнул бодрящую вступительную речь, которую я, к сожалению, проспал :(

Состав участников получился очень молодым: почти все папки укатили на Challenge24 (что не повлияло на хавку: в середине дня был фуршет)

Сам финал должен был начаться в 5 вечера, а до этого участников развлекли Code Game Challenge-эм. Нужно было написать бота, который бы перемещался по полю, пил поушены маны и здоровья, швырял в противников всякие нехорошие заклинания или просто бил их посохом (что большинство времени и делал занявший 8-ое место MyasnoyRobot).

Бот vepifanov выиграл для Сергея Рогуленко (SergeyRogulenko) 11-дюймовый макбуку эйр. Бот Епифанова (vepifanov) SergeiRogulenko вылетел из 1/8. Трёхчасовой кодинг бота и послефуршетный просмотр боёв поставили в равные условия невыспавшихся красноглазиков и свеженьких участников финала.

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

И вот, турнир начался!

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

В этот раз соревнование обошлось без травм головы о задачи, и без характерной боли в закостеневшей за 3 часов сидения тазовой части наборщика кода.

Условия были ясные, тесты корректные, а решения безшаманские. Авторы МОЛОДЦЫ.

Когда соревнование закончилось, все собрались в конференц-руме (в отличие от румов на CF он был один) и упёрлись взглядом в табло (а вот их было два).

Систесты сидели на цепи и угрожающе рычали.

Миша отзвонился Геральду (Gerald), тот спустил собак и они принялись грызть решения на прочность.

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

Победителями стали ( в скобках указаны ники на Codeforces.ru).

1.  Эмиль Лернер, Россия, Москва  (neex.emil)

2.  Дмитрий Егоров, Россия, Санкт-Петербург (Dmitry_Egorov)

3.   Владислав Епифанов, Россия, Нижний Новгород (vepifanov)

Немного самокритики от Романа Андреева (romanandreev) — победителя facebook Hacker Cup 2012!

Остальные видео с контеста смотрите в  моем канале youtube.

Итоговые результаты.

И еще фотографии:

Контест по спортивному программированию. КРОК 2012.

Контест по программированию КРОК 2012.

Контест по программированию. КРОК 2012 - финал.

Read more »

 
 
 
 
  • Vote: I like it  
  • +58
  • Vote: I do not like it  

By ivan.popelyshev, 7 years ago, In Russian,

Сайт: http://bombermine.ru/

Приложение на ВК: http://vk.com/app3168464 , прошу распространять среди социальных друзей.

Дизайн для ВК по-моему офигенен, делал мой партнёр по делу Марк Зубовский.

Чтобы узнать что поменялось с тех древних времён, когда я создал эту тему , смотрите блог

Последние изменения есть в ченжлоге

Далее идёт оригинальный пост:

 Первый тест

Для проверки игрового движка на Java/HTML5 использую простую игру, написанную на нём за одну неделю.

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

Для игры нужен Google Chrome, Firefox 11 или Опера (opera:config, и в user prefs должно быть enable websockets.).

UPD. Текущий рекорд — 50 человек.

UPD2. Некоторые браузеры не поддерживающие WebSockets теперь могут быть использованы для игры. Но Internet Explorer 9 показывает какую-то хрень.

Идеи сюда: http://bombermine.reformal.ru/

UPD3. Понифицировали.

Read more »

 
 
 
 
  • Vote: I like it  
  • +148
  • Vote: I do not like it  

By ivan.popelyshev, 7 years ago, In Russian,

Накопилось много идей, решил сделать движок для браузерных РТС (свой, с покером и шахматистиками). Работа уже идёт, описание оставил на gamedev: http://www.gamedev.ru/projects/forum/?id=160559

Стек технологий: Java, GWT, HTML5. Если тут кто фанатеет серией Dune и C&C, могу принять в команду. Задача — быстро разработать игру, которая займёт свою нишу, аналогично Minecraft.

UPD. Мне уже писал сценарист. В результате обсуждения его бреда, я его послал и сам всё придумал. По этому вопросу можете больше не писать.

Read more »

 
 
 
 
  • Vote: I like it  
  • +21
  • Vote: I do not like it  

By ivan.popelyshev, 7 years ago, translation, In English,

Let my contribution to increase.

Competition will held at 9 february 16:00 GMT (20:00 Saratov).

May the Force be with you!

Read more »

 
 
 
 
  • Vote: I like it  
  • +59
  • Vote: I do not like it  

By ivan.popelyshev, 7 years ago, In Russian,

Условие задачи

Есть N ≤ 1018 пар (Pi, Wi) сгенерированных по следующему алгоритму:
  • Pi = ((A*Pi-1 + B) mod M) + 1
  • Wi = ((C*Wi-1 + D) mod K) + 1
  • Где  M, K ≤ 107, P1, W1, A, B, C, D заданы.
  • Требуется найти:
  1. Количество пар  (Pi, Wi)  таких что не существует пары (Pj, Wj) такой что Pj ≤ Pi и  Wj < Wi либо  Pj < Pi и  Wj ≤ Wi
  2. Количество пар  (Pi, Wi)  таких что не существует пары (Pj, Wj) такой что Pj ≥ Pi и  Wj > Wi либо  Pj > Pi и  Wj ≥ Wi 
Разберемся с первой частью, вторая делается аналогично.
Заметим, что если все Pi одинаковы, то ответ это количество минимумов.
Переходим к двумерной задаче: для каждого P < M будем хранить текущий минимум minp и количество найденных пар вида (P, minp)
Если посчитать эти величины, то ответ ищется просто: для каждого p надо проверить что нет такого p0 < p что minp0 ≤ minp , и в этом случае прибавить к ответу количество  пар вида (P, minp). Это делается за один проход.

Как же искать этот minp ?

Понятно, что через max(M, K) элементов обе последовательности зациклятся. Обработаем этот кусок, выкинем его и рассмотрим циклы, осталось обработать N1 = N - max(M, K) пар.
Получившиеся циклы:
p0, p1, p2, p3,  ... pA - 1
w0, w1, w2, w3, ... wB - 1
Для фиксированного pi важно знать минимум и количеством минимумов тех  w, что попадают в пару вместе с фиксированным pi:
Для p0 они имеют индексы 0, A%B, (2 * A)%B, ...
Для p1 это 1, (A + 1)%B, (2 * A + 1)%B, ...
Для p2 это 2,  (A + 2)%B,  (2 * A + 2)%B,  ... 
Для p(A - 1) это (A - 1)%B,  (2 * A - 1)%B, ... 
Все индексы меньше N1

Вот тут можно поступить по-разному
  • Разбить цикл из w на орбиты элементов которые идут через A и на каждой использовать RMQ. Это  O(max(M, K) * logN) по времени. Можно улучшить до O( max(M, K) ) используя RMQ за O(1) два раза, ведь последовательности могут иметь длины N1 / A и  N1 / A.
  • Cчитать минимум и количество минимумов среди элементов w проиндексированных (i + j * A)%B , 0 ≤ j < 2k для каждого k, и использовать на этом двоичный подъём, "перемножая" массив как при быстром возведении в степень. Это  O(max(M, K) * logN) по времени
В обоих случаях получается и и O(max(M, K)) по памяти. 

Лично я выбрал второе, макстест на Java работал за 17 секунд, но на их 20 тестах программа уложилась в 2 минуты. К тому же можно было запускать это сразу на нескольких компах/ядрах.


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

Read more »

 
 
 
 
  • Vote: I like it  
  • +70
  • Vote: I do not like it  

By ivan.popelyshev, 8 years ago, In Russian,
//import java.util.*;

public class Main {
public static void main(String[] args)
{
double a = 2.3;
double b = 0.2;
System.out.println( a % b );
}
}

И ведь работает!
А если поставить a=2.4, то она вернет число близкое к 0.2 , это нормально для вещественной арифметики.

Read more »

 
 
 
 
  • Vote: I like it  
  • +23
  • Vote: I do not like it  

By ivan.popelyshev, 8 years ago, In Russian,

Бывает же такое...


Read more »

 
 
 
 
  • Vote: I like it  
  • +8
  • Vote: I do not like it  

By ivan.popelyshev, 8 years ago, translation, In English,

It's time to restore my contrib points.

One person from Russian Code Cup finalists said that he code slow in early morning. We have a chance, don't miss it!

Competition will held at 18:00 EDT (5:00 Moscow) 

May the Force be with you!

Read more »

 
 
 
 
  • Vote: I like it  
  • +17
  • Vote: I do not like it  

By ivan.popelyshev, 8 years ago, In Russian,
У меня фоток нет, напишу коротко. Все поселились в славном swissotel krasnie holmi (прям хилтон какой-то), познакомились с организаторами, очень хорошо пообщались, каждый участник получил по ipad2 в рюкзачке, посмотрели интересные слайды, провели ядреные дискуссии на тему компьютерного образования в школах и вузах. Финал 18 числа в 11 утра, болейте за нас.

Общее впечатление: финал acm только личный. Mail.ru молодцы.

Read more »

 
 
 
 
  • Vote: I like it  
  • +73
  • Vote: I do not like it  

By ivan.popelyshev, 8 years ago, In Russian,
 
 
 
 

By ivan.popelyshev, 8 years ago, In English,

Coding begins in 12:00 PM EDT (20:00 Moscow time)

May the Force be with you!

P.S. Discuss it here and increase my contrib.



Read more »

 
 
 
 

By ivan.popelyshev, 8 years ago, In Russian,

Кросспост (нажмите сюда чтобы перейти на оригинал)

В рамках проекта SnarkNews стартовала летняя серия индивидуальных соревнований по программированию SnarkNews Summer Series - 2011. Серия состоит из 5 раундов. При этом каждый раунд проходит по правилам TCM/Time. Участвовать в серии могут те, кто или уже зарегистрирован на сервере личных соревнований SnarkNews (список зарегистрированных доступен по ссылке "Пользователи" в верхнем меню), или подал заявку на участие в SNSS-2011 согласно правилам серии по адресу sn_register(собака)snarknews(точка)info.
Участвовать в SNSS-2011 можно, начиная с любого раунда.

01.08.2011 (пн) 15:00. Стартовал первый раунд SnarkNews summer series-2011. Окончание первого раунда - 10.08.2011 15:00.


Отсебятина: Просим на время каждого из раундов не обсуждать задачи.

Read more »

 
 
 
 
  • Vote: I like it  
  • +15
  • Vote: I do not like it  

By ivan.popelyshev, 8 years ago, translation, In English,

Congratulations to Petr Mitrichev impressive victory!

We need to assign some number from 0 to 6 to each of the 14 squares. Note that if you take the solution and apply some permutation of digits to the field, you obtain another correct solution. So, the solution is characterized by division of 14 squares to pairs. If we have such a partition, then it is possible to generate a 7! corresponding solutions. Count of possible partitions is 13!! = 13·11·9·7·5·3 = 135135 . It is easily to verify the correctness for each of the 100k options.

With up to rotations, count of all field configurations that have solutions is about 6000. The largest number of solutions - 22·7!.


Подколки:
1) If you do not optimize the solution in 7! time, you can get a TL. As was shown in the comments it’s enough to optimize 7 times.
2) You would think that the squares are divided into two classes - 7 squares that have double dominoes, and 7, in which it is not present. If we talk in terms of graphs there are 7 vertices with degree 2, and 7 with degree of 4. Clearly, two vertices of degree 2 can not correspond to a single digit, otherwise we get two double dominoes. With this division is sufficient to iterate over 7! possible matches vertices of the second type to vertices of the first type.


Double domino 4-4 split between the two squares. There are 6 vertices of degree 2 and 8 vertices of degree. Challenge Succeeded.
Furthermore:

Here for two double dominoes lie between squares!

And bonus, one of the most beautiful configurations with several holes:

Disconnected configuration with solutions don’t exist :(

Read more »

 
 
 
 
  • Vote: I like it  
  • +31
  • Vote: I do not like it  

By ivan.popelyshev, 8 years ago, translation, In English,

> The IPSC 2011 contest will be held from June 5, noon CEST to June 5, 5:00 pm CEST.

I inspired by team "Never Retired" and  Problem Q from practice,

Team list

Onine standings

Lets discuss it here, but not in the time of event.

Read more »

 
 
 
 
  • Vote: I like it  
  • +26
  • Vote: I do not like it  

By ivan.popelyshev, 8 years ago, In Russian,
Очередной кросспост с http://sharpc.livejournal.com/68313.html#cutid1

Сегодня на Открытом Кубке мне впервые удалось успешно применить в спортивной практике метод графического дебага, и об этой success story дальше и пойдет повествование :)


Смотреть задачу O
В задаче требуется найти, с какой скоростью (от 0 до 300 м/с) должна выстрелить пушка, направленная под углом d (от 0 до 78°), чтобы из точки (xu,yu) попасть в (xo,yo), если на снаряд действует ускорение свободного падения g и ускорение силы ветра w, либо вернуть −1, если это невозможно.

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



Руководствуясь этими несложными соображениями, я написал такой код с несколькими отсечениями:

double solve(double x, double y, double w, double d)
{
    double omega = atan(w / g);
    d -= omega;
    double xx = x * cos(omega) + y * sin(omega);
    double yy = x * -sin(omega) + y * cos(omega);
    double a = sqrt(g * g + w * w);
    if (xx < 0.0) return -1;
    if (xx * tan(d) <= y) return -1;
    double v2 = a * xx * xx / 2.0 / (xx * tan(d) - yy) / cos(d) / cos(d);
    if (v2 < 0.0) return -1;
    double v = sqrt(v2);
    if (v >= 0.0 && v <= 300.0) {
        return v;
    }
    return -1;
}

И получил WA2. Самые внимательные, конечно, уже заметили ошибку, но я в их число никогда не входил и принялся дебажить :) Однако придумать подходящий тест не получилось. «А хорошо бы посмотреть для большого количества пар (x,y), как летят снаряды» — подумал я. Но стандартные средства, используемые на контестах, типа силовой отладки или логов не особо удобны для обнаружения багов в подобных задачах. Несколько удобнее была бы псевдографика, но все же она недостаточно наглядна. Хорошо бы подошел BMP, но по памяти его написать не очень просто. И тут я вспомнил о самом простом графическом формате — portable pixmap format (PPM), обнаруженном в процессе игр с AGG. Его открывают, например, XnView, Lister@Total, Photoshop. Скопирую пример из википедии:

P3
# The P3 means colors are in ASCII, then 3 columns and 2 rows,
# then 255 for max color, then RGB triplets
3 2
255
255 0 0 0 255 0 0 0 255
255 255 0 255 255 255 0 0 0

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



Немного поиграв с w и d, на одной из картинок я увидел странный артефакт — видимо, сработало какое-то отсечение, «испортившее» параболу:



Подкрасив разные отсечения разными цветами, я нашел ошибочную строку :)



if (xx * tan(d) <= y) return -1;

Исправил и получил AC :)

К слову, метод графического дебага, пожалуй, единственно возможный в написании рендеров. Кто видел геймдевелоперов-рендеристов за работой, тот под LSD скучает!

Read more »

 
 
 
 
  • Vote: I like it  
  • +66
  • Vote: I do not like it  

By ivan.popelyshev, 8 years ago, translation, In English,
Member single round match 501 will start at 3.00 PM Moscow, 12:00 AM GMT.
Discuss it here.

Read more »

 
 
 
 
  • Vote: I like it  
  • +12
  • Vote: I do not like it  

By ivan.popelyshev, 8 years ago, In Russian,
Шарпиц продолжает радовать нас замечательными постами в жж.
Предлагаю обсудить сей эпичный пост:
http://sharpc.livejournal.com/67583.html

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +30
  • Vote: I do not like it