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

Автор Abra, 13 лет назад, По-русски
Привет.

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

Писать я решил клеточные автоматы - это интересно, и на маркете я не нашел приложения с тем функционалом, что я планировал реализовать.

Вот что получилось:

// извиняюсь за лого, нарисованное в 4 ночи в пейнте)

Фичи:
- относительно быстро считает
(самое эффективное, что придумал: для каждой клетки динамикой узнаем количество живых клеток в ее окрестности, знаем, живет она или умирает)
// интересно, можно ли быстрее?
- можно создать свои правила для клеточного автомата или выбрать существующие (Conway's Life, Day And Night, HighLife и много еще на выбор)
- можно создавать свои собственные паттерны или тоже выбрать существующий
- вес в 30 кб

Просьба качать, ставить, тестить и оценивать =)

И у меня такой вопрос к опытным в этом деле людям (такие, думаю, здесь найдутся =).
Как привлечь народ?

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

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

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

Мне кажется, что этот контест незаслуженно слишком мало обсуждался, поэтому создаю этот пост. =)


Немного информации с сайта
Google AI Challenge - контест о создании искусственного интеллекта, в котором могут принимать участие все: от начинающих до проффесионалов. Используя один из начальных пакетов, вы можете создать компьютерную программу (на любом языке), которая будет управлять колонией муравьев в битве за превосходство.
За 5 минут вы можете послать бота из начального пакета на сервер и посмотреть, как ваши муравьи сражаются с колониями других людей со всего мира. Потом прочитайте инструкции о том, как запускать бота на локальном компьютере и начитайте кодить! 

В прошлом году был похожий контест на основе игры Galcon.

Завтра (20 октября) откроется регистрация и начнется основной контест, который продлится до середины декабря.
Призываю всех принять участие, потому что это очень интересно =)
А тут устроить обсуждение стратегий.

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

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

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

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

Но я подумал: "Гораздо лучше жить N лет в общаге с людьми, которые имеют с тобой хоть что-то общее, чем просто с рандомными соседями." И из моей предыдущей записи (в которой нашлось место даже теории операторных пространств О_о) следует, что на кодфорсах есть люди, поступившие на ФИВТ в этом году. Так давайте объединяться в комнаты по кодфорсовому признаку! =) 

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

Вот тут есть немного странное обсуждение той же проблемы.

<маленький оффтоп> недавно наткнулся на projecteuler.net, понравилось, кто-нибудь знает что-нибудь похожее? </маленький оффтоп>

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

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

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

1) Из какой школы (лицея/гимназии) выпустился
2) Куда собираешься поступать
3) Почему именно туда

И начну с себя:

1) Самарский медико-технический лицей
2) МФТИ ФИВТ (МГУ Мехмат/ВМК, МФТИ ФУПМ, ВШЭ Программная инженерия)
3) Понравилось в Долгопрудном, нравится учебная программа и привлекает уделяемое внимание ACM'у и атмосфера Физтеха

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

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

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

15 - 17 апреля 2011 года Самарский государственный университет при поддержке Министерства образования Самарской области и компании CQG проводит I (XII) открытый командный студенческий чемпионат Поволжья по спортивному программированию.
Информационное письмо о чемпионате доступно в формате pdf.


Чемпионат проводится в один тур в формате ACM ICPC. 
Расписание чемпионата
 (будет уточняться) 
15 апреля - регистрация прибывших команд(в первой половине дня), пробный тур (во второй половине дня). 
16 апреля - основной тур, подведение итогов, разбор задач. 
17 апреля - день отъезда для иногородних участников.

Участники чемпионата
К участию в чемпионате приглашаются команды, составленные из трех студентов или аспирантов одного вуза. 
Каждый участник на момент проведения Чемпионата должен являться студентом или аспирантом очной формы обучения, не более одного раза принимавшим участие в финалах ICPC ACM. Для каждого из участников должно быть выполнено по крайней мере одно из следующих условий: 
— в год проведения чемпионата участнику исполняется не более 24 лет 
— в год проведения чемпионата исполняется не более 5 лет с того момента, как участник впервые приступил к получению послешкольного образования. 
Команду может сопровождать тренер. Если у команды есть тренер, он является официальным контактным лицом команды.

Ориентировочное количество участников - 40 команд.
Оргвзнос за участие в чемпионате не предусмотрен.


Сайт чемпионата.


Upd.

Список команд (new!)

Чемпионат проводится в один тур в формате ACM ICPC

Расписание чемпионата (предварительное) (new!) 

Все мероприятия будут проходить в главном корпусе Самарского государственного университета по адресу ул. Академика Павлова, 1

15 апреля 2011 г.

10:00 - 14:30 Регистрация 
14:50 - 15:50 Открытие
15:50 - 16:30 Встреча с членами жюри и технического комитета 
16:40 - 18:10 Пробный тур 

16 апреля 2011 г.

09:30 - 09:45 Сбор команд у аудиторий перед основным туром 
10:00 - 15:00 Основной тур 
17:00 - 18:00 Закрытие 
18:00 - 19:30 Разбор задач основного тура 

17 апреля - день отъезда для иногородних участников.

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

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

Автор Abra, 14 лет назад, По-русски
Сегодняшняя дата напомнила мне об интересной задачке на spoj.pl.
Все просто - нужно вывести как можно больше верных знаков числа Пи в десятичной записи за 25 секунд.
Я перепробовал множество методов: 
от самых простых, (~200 знаков)

через забавные, (~1000 знаков)
 

к наиболее эффективному из тех, что я пробовал (~7300 знаков)




Витает еще идея использовать хитрую формулу

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

Лучшее мое решение написано на яве с использованием BigDecimal и самописного квадратного корня.

Может оптимизировать длинку? Или искать другие методы, ведь есть же решения, выводящие 20002 знаков за 2.5 секунд?

Подскажите, как вычислить миллион знаков =)

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

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

Автор Abra, 14 лет назад, По-русски
Привет, мир! Это мой первый разбор. =)

A. Разведка 2

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

B. Распродажа

Отрицательные элементы складываем в массив, сортируем, находим сумму m наибольших по модулю.

C. Список

Решается массивом булей, единственная заковыка - с выводом, но вполне преодолима.

D. Карта дорог

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

E. Столкновения

Заведем переменную времени ct, которая вначале равна 0.
Начинаем моделировать:
Пусть dt равен t - ct, просматриваем все пары шариков, по формуле 
x1 + v1 * dt = x2 + v2 * dt
dt = (x1 - x2) / (v2 - v1)
находим минимальную dt - промежуток времени, через который какие-нибудь шарики столкнуться, или время моделирования закончится.
Сдвигаем шарики на этот промежуток времени, снова просматриваем все пары, если координаты двух совпадают, меняем их скорости по формуле из условия.
Повторять, пока ct не сравняется с t.
Особое внимание стоит уделить точности, наверное на этом и подловили RAVEman'а с ACRush'ем. =)
В принятом решении я использовал double и точность сравнений 10-10.

Удачи в контестах!

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

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