MikhailRubinchik's blog

By MikhailRubinchik, history, 2 weeks ago, In Russian,

Всем привет!

В январе 2018 года в Свердловской области пройдёт зимний лагерь по спортивному программированию для школьников.

.

Read more »

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

By MikhailRubinchik, history, 5 weeks ago, In Russian,

Всем привет!

Трансляцию УрКОП 2017 можно читать здесь (контест начнётся через пару часов).

Read more »

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

By MikhailRubinchik, history, 2 months ago, In Russian,

Всем привет!

В этом году мы решили, что мало иметь кволы чф, нужно ещё и кволы для уркоп (это наш отбор на вкошп).

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

Детали можно посмотреть на официальном сайте: uralsportprog.ru/urcop/2017/

У нас есть зачёт кволов для других регионов, так что можно регаться всем школьникам cf :)

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

P.S. Если вам интересно следить за школьными олимпиадами и олимпиадными лагерями в Свердловской области, то вступайте в группу vk.com/ural_sp_school

Read more »

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

By MikhailRubinchik, history, 4 months ago, In Russian,

Всем привет!

Есть некоторое количество "продающих лозунгов" для IT-специальностей универов и IT-компаний.

Наиболее яркий пример такого использования я видел на Московском Фестивале Спортивного Программирования. Там был замечательный рекламный плакат компании Никс. Он тут девушками немного закрыт:

Но в целом суть понятна: Big Data, Data Mining и пара языков.

Сам плакат целиком сходу не нагуглил, но по частям его можно собрать из этого поста (мысленно совмещая части и убирая девушек) http://www.nix.ru/computer_hardware_news/hardware_news_viewer.html?id=192425

А ещё за эту весну было несколько постов, написанных с целью привлечения абитуриентов. Как минимум два из них набрали не меньше 100 лайков, так что думаю, что их заметил не только я :)

Вот пара скринов из подобных постов:

Все эти слова часто выглядят как магические заклинания, на которые бездумно бегут абитуриенты и будущие сотрудники :) А правда ли бегут? Или может бегут, но обдуманно?

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

А именно нужны ответы на вопросы:

  1. Какие подобные заклинания вам приходилось слышать?

  2. По каким коротким словосочетаниям вы сами искали/планируете искать универ/работу?

  3. По каким заклинаниям на универ/компанию клюют или клевали ваши знакомые?

Из постов выше можно увидеть следующие: биоинформатика, машинное обучение, нейронные сети, системы искусственного интеллекта, анализ данных, эволюционные алгоритмы, большие данные, data mining (не умею это переводить, или это и есть анализ данных? Русскоязычная статья википедии не переводит этот термин в заголовке http://ru.wikipedia.org/wiki/Data_mining ).

UPD из комментариев: Deep Learning

Буду очень признателен, если вы найдёте время и добавите пару заклинаний в комментариях :) Заранее спасибо!

P.S. Обещаю, если будет достаточно новых заклинаний, сделать после отдельный пост о том, где, кто и как их использует и на сколько это просто заклинания или просто адекватное описание реальности :)

Read more »

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

By MikhailRubinchik, 5 months ago, In Russian,

Всем привет!

[В этом посте будет рассказ об очередном лагере по олимпиадной информатике :) Я уже хочу]

Я занимаюсь подготовкой студентов и школьников к соревнованиям по спортивному программированию уже около 12 лет. Но в основном всё это время я занимался студентами. С этого года хочу более активно заняться школьниками.

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

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

Лагерь в ноябре будет ориентирован на подготовку ко ВКОШП для самых сильных и к муниципальному этапу ВсОШ для более новичков. Лагерь в январе будет ориентирован на подготовку к региональному этапу ВсОШ.

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

Если вы не из Свердловской области, после голосования укажите, пожалуйста, ваш регион в комментарии.

P.S. участие в опросе не означает заявку в лагерь, мы просто хотим оценить степень интереса к лагерям, чтобы принять решение.

Хочу в лагерь.

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

Read more »

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

By MikhailRubinchik, 5 months ago, In Russian,

Всем привет!

Я уже писал в моих еженедельных постах о тренировках, что у нас в УрФУ есть свой канал на ютьюб. Он появился только этой зимой. Там выкладываем видео с нашего семинара (сейчас их около 20).

В нём есть одна проблема. Ссылка на него вот такая: https://www.youtube.com/channel/UCkRTYySiCAqX1tQIYXjKBQw. Длинная и сложная :) А хочется такую: youtube.com/spural

Ютьюб ставит 4 требования к каналу, чтобы на него можно было поставить хорошую ссылку. 3 из них мы выполнили. Осталось последнее: 100 подписчиков (у нас сейчас 50).

Уверен, что на кф найдётся немало людей, которые не знали раньше о канале, но кому может показаться интересной наша тематика.

Поэтому ставьте лайки, подписывайтесь на канал :)

Заранее спасибо за помощь в развитии нашего канала! :)

Read more »

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

By MikhailRubinchik, history, 8 months ago, In Russian,

Всем привет!

Мне в научной статье понадобилось сослаться на дерево отрезков. Для этого хочется какой-то фундаментальный труд, где оно упоминается. Я думал, есть в Кормене, но сходу там не нашёл. Если кто-то видел его там, можете подсказать, в каком издании и какой главе смотреть? Описаны ли там ДО с отложенными операциями (проталкиванием)?

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

Или может хотя бы кто-то знает, как в научных статьях их называют? :) По segment tree гуглятся в том числе деревья, в каждой вершине которого лежат геометрические отрезки.

Read more »

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

By MikhailRubinchik, 9 months ago, In Russian,

Тут часть людей сбежали с предыдущих лекций :)

Моя лекция будет примерно в 18:25 (может чуть раньше).

Возвращайтесь к ней в 105 аудиторию. Обещаю веселые картинки со снарками и другими персонажами:)

P.S. буду говорить по-русски

Read more »

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

By MikhailRubinchik, 12 months ago, In Russian,

Всем привет!

Я традиционно пишу перед полуфиналом посты о каких-то проблемах и решениях, связанных с организацией NEERC. В прошлом году я, например, делился опытом кволов, в позапрошлом рассказывал об идее кволов, а ещё за год до этого жаловался на плохие правила распределения квот. Что интересно, в этом году правила квот, наконец, формализовали и немного изменили.

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

Многие мои соображения исходят из тезиса “АСМ должен быть как можно доступней”. Этот тезис не мой, а Билла Паучера, но я его полностью разделяю.

1.Отсутствие АСМ в Таджикистане и Туркменистане

Я уже немного начал решать этот вопрос. Этот пост — первая попытка. К сожалению, пока неудачная. В этом году я связался с ребятами из Туркменистана. Сходу удалось найти только школьников и они подали заявку на вкошп. Вы можете уже найти их в списках. Связался я довольно поздно и не факт, что ребята успеют сделать визы. Но возможно, в следующем году в Туркменистане уже появится свой отбор на вкошп и свой чф. Во всяком случае я надеюсь на такой исход и в Туркменистане, и в Таджикистане.

Вообще, я в большинстве случаев мыслю не в масштабах NEERC, а в масштабах АСМ. И если руководство NEERC не создаст АСМ в этих странах, то возможно это сделают другие полуфиналы из азии. Но может и нет. И моё основное желание конечно же в том, чтоб АСМ в этих странах появился. С другой стороны я всё-таки патриотичен и для меня более хорошее решение — это появление четвертьфиналов NEERC в этих двух странах. Кроме того я считаю, что несмотря на имеющиеся проблемы структура NEERC лучше структур всех остальных полуфиналов (Кстати, Билл Паучер с этим согласен, он говорил об этом со сцены на финал АСМ в Екатеринбурге).

2.Отсутствие кволов

Отсутствие кволов создаёт очень высокий порог входа для новых вузов.

У нас некоторые отвечали: что нам ехать на чф, мы там проиграем. А с введением кволов некоторые из таких вузов прошли на чф и поехали, ведь они уже знали, что они обогнали очень многих на кволах и могли показать бумагу об этом руководству. Кажется, что кволы не нужны только московскому чф ввиду маленькой площади и метро. Однако с точки зрения гарантированности одинаковых условий для Москвы конечно всё равно нужны кволы (но организаторы могут конечно часто забивают на необходимость одинаковых условий).

3.Оргвзнос мешает росту числа команд

Я точно знаю, что оргвзноса нет на урале и нет в Москве. Можете написать в комментариях, где ещё присутствуют или отсутствуют оргвзносы? Мне кажется, идеальная ситуация: ни на одном чф нет оргвзноса. Но в целом при появлении кволов приемлемая ситуация: на кволах нет оргвзноса, а на чф есть.

4. Лимиты на число команд от вуза на чф

На сколько я знаю, в некоторых четвертьфиналах, по-прежнему, действуют правила, запрещающие одному вузу выставлять больше 4-5 команд. Это правило конечно же вредное, т.к. уменьшает доступность АСМа и идёт в разрез с правилами полуфинала. Получается организаторы полуфинала предоставляют возможность вузам получить доп.квоты, а организаторы четвертьфинала мешают этому.

Опять же при наличии кволов с большим числом площадок такая проблема исчезает. ЧелГУ и ЮУрГУ было тесно в ЮУрГУ в прошлом году? ЧелГУ в этом году открыл свою площадку, а ЮУрГУ на своей площадке привёл огромное число своих команд.

В этом году на питерском чф СПбГУ привели около 30 команд. В итоге на чф у них было около 100 команд, а в итмо это около предела. Во всяком случае на пф готовы брать не более 100 с небольшим команд. Были бы кволы и площадка в СПбГУ, могли бы привести столько, сколько захотели.

5.Наличие многосайтовых чф и пф

Все мы видели историю с читерством на пф в прошлом и позапрошлом году. И наверное всем из нас это не понравилось. Кажется, что такую проблему нужно решать. Идеально решение с точки зрения этой цели — это односайтовый пф, но тут нужно очень аккуратно, чтоб не навредить цели “доступности АСМа”. Может быть отправка большего числа наблюдателей или выдача наблюдателям больших полномочий решила бы такой вопрос.

Аналогичная (но ещё хуже) ситуация в этом году была в чф Узбекистана из-за онлайнового проведения. Более того в Новосибирске на чф так было вообще всегда. Я считаю такую ситуацию недопустимой.

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

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

Поэтому мы берём с кволов на чф очень много команд (около 90-100 команд), а уже на чфе отбираем команды на пф.

6.Нарезка на четвертьфиналы сложилась исторически и теперь сохраняется статус-кво

Текущие четвертьфиналы появились ещё в прошлом веке и никто ни разу публично не говорил о том, как могут они меняться и могут ли. По факту мелкие изменения происходят (Орёл, как я понимаю, переходил из южного в центральный). Почему я считаю, что плохо здесь держать статус-кво? По той же причине доступности АСМа. Например, Сыктывкару довольно далеко ехать до Екатеринбурга, а Екатеринбург участвует дома. Мы почти закрыли эту проблему для нашего чф кволами, но всё равно людям надо тратить деньги на 1-2 команды и ехать целые сутки. Возможно, что ещё где-то есть такие проблемы. Будет здорово, если напишут люди, которые считают, что едут слишком долго или слишком дорого. Я считаю, что приемлемый вариант: вечером сел, утром приехал, остальные уже похуже. Я пока не думал о решении этой проблемы и предлагаю только сообществу задуматься, есть ли такая проблема или нет.

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

Если вы видите в neerc другие проблемы, пишите об этом :)

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

Read more »

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

By MikhailRubinchik, 12 months ago, In Russian,

Всем привет!

Как наверное все уже видели из постов Savinova, я в этом году по приглашению Botan Investments веду в группе vk.com/botaninvestments свой блог для тренеров. Многие посты совсем наивны и рассчитаны на новичков, но некоторые, на мой взгляд, могут быть полезны и довольно опытным в этом деле. Один из постов вызвал довольно резкую критику одного из участников сообщества (Sunar). Я ему ответил что-то краткое и не стал развивать дискуссию vk, но решил взять тот пост, подкорректировать и добавить комментарий по поводу позиции (Sunar). Если будет дополнительная критика и комментарии в данном посте, то это только хорошо :) Больше шансов прийти к истине.

Итак, я начну с поста из vk (с небольшими правками), а после добавлю ответ на комментарий Sunar. Вообще данный пост vk вырос из этого поста на cf. Правда здесь я буду говорить только про орг. работу, а не про работу тренера.


Часть 1.

В этом посте я буду говорить шире, чем просто о тренировках — чем универ может помогать АСМщику?

Вот студент хочет заниматься АСМ. Что ему нужно делать?

Обычный студент учится, спит, ест, развлекается. Ему нужно не вылететь из универа и иметь деньги на еду и развлечения. Продвинутый студент старается прокачаться в чем-то еще (помимо универа), и АСМ — один из видов такой прокачки. И вот наш студент, помимо того, что учится, ест, спит и развлекается, ещё и делает что-то в АСМ.

На первый взгляд кажется, что ничего сложного тут нет, и студент просто решает задачки.

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

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

Думаете, это всё? Я всё равно забыл про кучу мелочей. Но, наверное, все уже понимают, что работы здесь много. Цель данного поста в том, чтобы осознать, что, помимо решения задач, АСМщику нужно решать множество организационных вопросов, и это совсем не просто.

Я думаю, что для большинства АСМщиков гораздо нужней не тренерская помощь, а организаторская, которая поможет им разгрузиться от части этой работы. И я приведу список того, что может сделать университет. Где-то всё это будет делать тренер, где-то часть работы выполнит специальный человек, а где-то этим будет заниматься целый отдел. Также я расскажу, как этот процесс происходит в УрФУ. Конечно пост был бы лучше, если бы я разобрал это на примере и других вузов. Но обычно когда я начинаю что-то писать про другие вузы, находится кто-то несогласный, кто говорит, что я у них не учился и ничего о них не знаю. Поэтому, к сожалению, я буду писать только про УрФУ, зато про него я точно могу рассказать в деталях, т.к. варюсь в этом.

Часть 2.

В УрФУ почти всю (но не всю) организационную работу, связанную с тренировками и поездками, делаю я. Возможно, в некоторых вузах есть специальные люди для бюрократии :), но для участников это не так важно. Список конкретных дел:

1.Очень хорошо, если ваш вуз сможет оплатить все поездки, и участнику не нужно будет думать об этом и уточнять, дадут деньги или не дадут. Участнику достаточно просто знать, что если он пройдёт на соревнование, то всё будет оплачено без вопросов. У нас, например, каждый год часть расходов берёт на себя УрФУ, также есть долгосрочные договорённости с СКБ Контур и периодически другими спонсорами из Екб. В этом году нам пару поездок оплатил фонд Botan Investments. Старайтесь находить и договариваться со спонсорами. Конечно, всё в рамках разумного. Если у вас одна команда, то все поездки на год — это около 500 тысяч (2 сборов в МФТИ, 2 сборов ПетрГУ, полуфинал, турнир ICL, ЧУ, всесиб). Если же ребята хотят сгонять куда-то на соревнования или сборы за границу, то это уже “потустить” и нельзя это воспринимать, как важную трату.

2.Допустим, вы нашли деньги, и они оказались в бухгалтерии универа. Очень плохо, если вы отправите студента самого оформлять все эти служебки, приказы, отчитываться по командировкам. У нас студенты этого не делают, лишь изредка отчитываются по командировке (если вдруг едут без меня), а обычно им для отчетности нужно только принести посадочные талоны. Теперь допустим, что у вас есть деньги в чистом виде, не в бюрократической структуре. Тогда легко? :) Не тут-то было. Всё равно придётся купить билеты, забронировать гостиницы, оплатить оргвзносы, и при выборе этого всего согласовать с остальной частью команды. У нас всё это покупаю я (за редким исключением). Советую другим тренерам делать так же. Вообще ребята должны понимать, что они в надёжных руках, т.к. иногда случаются нестандартные ситуации, которые нужно решать оперативно. Для примера приведу несколько кейсов, которые приходилось решать, будучи тренером или участником: a.Отменили ночной самолёт Пермь-Казань. Едем на такси, приезжаем ночью, по пути бронируем гостиницу. b.Сборы в Петрозаводске наложились на отбор на РОИ. Договариваемся, чтоб отбор на РОИ был сыгран вместе с участниками Карелии. c.Сборы в Петрозаводске наложились на олимпиаду, с которой не договориться, а участник несовершеннолетний. Участник приезжает в птз позже (без меня). Моя жена везёт участника до Москвы и там сажает на поезд в птз.

3.Должно быть хорошее помещение для тренировок с круглосуточным доступом . В нем должны быть столы и стулья в достаточном количестве, принтер для печати решений. В общаге или дома играть неудобно, т.к. есть мешающие факторы. Можно попробовать найти комнату в универе или в местной it-компании. У нас есть АСМ-комната в УрФУ и в Контуре. В Контуре более удобная и большая, зато первая ближе к учёбе. Я думаю, что при достаточном организаторском таланте оба варианта достаточно реальны для вас.

4.Если серьёзно заниматься АСМ, то точно будут пропуски пар и экзаменов. Зимние сборы в ПетрГУ часто попадают на сессию, а из-за сборов в МФТИ участники пропускают много пар. Очень важно, чтобы у вузовских преподавателей не было негативного отношения к АСМщикам, иначе у студентов может пропасть всякое желание заниматься. Когда у моих студентов возникают проблемы, я сам хожу разговаривать с преподами. На халяву мы ничего не проставляем, но иногда продлеваем время сессии или переносим экзамены, а также проставляем некоторые спецкурсы для АСМщиков. Слышал много историй о том, что в некоторых вузах АСМщиков отчисляли. В УрФУ у серьёзных АСМщиков (тех, кто ездит на сборы) есть “вторая жизнь” на случай, если их соберутся отчислять. Хотя для справедливости надо сказать, что за то время, пока я учился, было только 2 АСМщика, которые бывали на грани отчисления (один из них я :) ).

5.Многие студенты-программисты рано идут работать, а АСМщик уже “работает” для популярности вуза. Поэтому здорово, если эта работа оплачивается. В УрФУ всех активных АСМщиков поощряют неплохими стипендиями. Самые маленькие, о которых я слышал, — в районе 8000 рублей, самые большие — больше 20 000 рублей.

6.Последний пункт уже чуть ближе к непосредственно тренерской работе: “пинание”. Если ребята в команде назвали список свободных дней, и в пересечении оказалось пусто, то тренировки могут не состоятся. Хорошо, если кто-то из ребят прогнётся и всё получится. Но если такого не случится, то инициативу на себя должен взять тренер: поговорить с каждым, попытаться найти компромисс, возможно на самого ленивого надавить или даже изменить состав команды. Также тренер должен подбадривать людей или ругать, если они мало решают архивы/пропускают тренировки.


Итак, теперь комментарий Sunar.
Мой ответ в группе

Осталось дать мой более развёрнутый комментарий.

Вообще, мы живём в условиях рыночной экономики. И тут мало кто кому-то что-то должен. Не делаешь ты что-то => с тобой не сотрудничают (не платят денег, не учат тебя, не учатся у тебя и т.д.). В данном случае мы должны понимать, что некоторые столичные вузы очень хорошо распиарены как минимум своими результатами. У них действует примерно такой алгоритм:

1.В вуз приходят крутые чуваки.

2.Их никто не тренирует в АСМ и никто не помогает с орг.работой.

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

4.О результатах слышат крутые школьники и снова идут в этот вуз.

Замкнутый круг счастья столичных вузов :)

Нет, я не говорю, что во всех столичных вузах дела обстоят так, но такие вузы точно есть. Более того, в вузах, где тренировки хорошо поставлены, этот фактор всё равно очень важен. Даже если вы сверхгениальный тренер и у вас всё супер организовано, но к вам не поступает ни одного призёра всеросса, вы никак не будете делать стабильно призёров финала АСМ (но иногда может везти конечно на талантливых студентов).

Так вот, если вы хотите, чтоб школьник выбрал ваш вуз, придётся создать условия, которые будут лучше большинства столичных вузов (хотя бы в части пунктов). Иначе каким бы чудесным тренером вы ни были, вам придётся качать людей за время универа с самых новичков.

Теперь конкретно про рассуждения Sunar. Мой список — это то, чего добились мы в УрФУ. Вероятно, его можно улучшать и улучшать, но в целом, я думаю, он довольно неплох. И строился он далеко не сразу: когда я пришёл в УрФУ студентом, были пункты 1, 2 (только билеты покупали), 4 (не отчисляли, но с преподом студенты договаривались сами), 5. По пунктам 2, 3, 6 не было хороших решений, их постепенно привносил я. Т.е. мы к этому шли годами, и я ни в коем случае не ругаю тренеров, которые пока сделали только малую часть. Ведь я “стоял на плечах гигантов”, а некоторые тренеры делают вообще всё с нуля. Я просто показываю, куда ещё можно развиваться, и буду рад, если какие-то советы им помогут :)

Read more »

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

By MikhailRubinchik, 13 months ago, In Russian,

Всем привет!

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

P.S. Может тема уже и поднималась на cf. Я наткнулся на неё только что на занятии с Ivan11.

#include <iostream>
#include <cmath>
#include <typeinfo> 

using namespace std;

int main()
{
	cout << typeid(abs(1)).name();
}

UPD: была опечатка в коде, сейчас код немного изменился

Read more »

 
 
 
 

By MikhailRubinchik, 14 months ago, In Russian,

Всем привет!

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

  1. Наши кволы 2016 кончились только что. Здесь можно посмотреть замороженные результаты: http://acm.timus.ru/monitor.aspx?id=399

  2. Контест я уже залил в мешапы (http://codeforces.com/group/DOo7Ng4jy4/contests) . Его можно отыграть прямо сейчас, но он без реальных участников. Кто-то может подсказать, как залить результаты в мешап? Если залить результаты нельзя без wizard, то залью, как только появится более удобный способ. Ну или любители рутины могут попросить у меня права на контест в полигоне

  3. Кволы теперь “легализованы”. Это отражено в новых правилах полуфинала http://neerc.ifmo.ru/information/selection-rules.html

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

  5. Кроме нас никто в этом году кволы не провёл. Увидим, что будет в следующем году :)

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

  7. В прошлом году в кволах участвовала 361 команда

  8. В этом году я сам не занимался PRом совсем. Мы только разослали письма прошлогодним участникам

  9. Тем не менее квол собрал 338 команд

  10. Из внезапного: ЮУрГУ привёл 85 команд! Я лично в шоке

UPD: В этом контесте много простых задач, но есть и сложные. Это можно видеть по монитору. Поэтому контест вполне для тренировки подходит и команде совсем новичков и команде уровня топ в птз.

Read more »

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

By MikhailRubinchik, 15 months ago, In Russian,

Всем привет!

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

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

Предлагаю ввести возможность добавлять такие ачивки в профили cf. Сейчас мы можем что-то узнать о человеке по его контестам именно на cf, его исходникам и его комментариям/постам. Было бы здорово, если бы можно было зайдя на страницу, узнать о человеке немного больше. На rcc у некоторых есть совсем перегруз (штук по 10 ачивок), можно сделать на cf лимит (не больше 5-7, скажем). В обычных соц.сетях тоже есть подобный функционал (я не пользуюсь fb, но оно точно есть vk).

Если у кого-то на эту тему есть замечания, предложение, негатив, пишите :)

Read more »

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

By MikhailRubinchik, history, 17 months ago, In Russian,

Всем привет!

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

Я тренирую студенческие команды не так давно (реально активно года 3). И последние пару лет я постоянно пытался расспрашивать наиболее титулованных тренеров (прежде всего Андрея Станкевича, Андрея Лопатина, но немного других), пытался экспериментировать и что-то придумывать сам.

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

Поэтому я решил сначала собрать больше информации от сообщества. Вопрос, который я задаю каждому читающему и комментирующему, шире, чем тот, который я вынес в заголовок. Что должен делать универ (это собирательное понятие из всех людей, кто в универе что-то делает для icpc) для АСМщика? Т.е. организация местных соревнований, поездок, лекции, тренировки, подбор сокомандников. Все подобные вещи можно и нужно включать в ответы. Возможно, вы считаете, что что-то нужно оставлять студенту, а от чего-то студента надо обязательно избавить. В общем, я бы хотел собрать как можно больше разнообразных мыслей по этому поводу.

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

Если у вас хватит дерзости, может посравнивать наших мэтров (итмо, СПбГУ, мгу, мфти и других) и попробовать предположить, у кого в чём преимущества. Также можно сравнивать их с провинциальными вузами и предполагать, чем столичные тренеры лучше провинциальных.

Read more »

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

By MikhailRubinchik, 18 months ago, translation, In English,

Hello everyone

I created and prepared all problems for the first round of Yandex.Algorithm . Below you will find editorial. I am sorry if something in solutions discriptions is not clear, if you have questions — please ask them in comments.

Problem A. Cheese

If potato takes less time to heat, than cheese to melt, then it is impossible. Otherwise, we either heat the potato a little and then put cheese on it, or heat the cheese to some degree, put it on the potato and continue to heat them together.

Problem В. Travelling in the Square

After leaving the central square there are four possible directions to go to, on the next step there is a choice from two turns and after that the route is fully determined. Thus, there are only 8 different routes. Each of them can be represented by a single string of length 9. Let’s put these strings in a constant array. While reading the input data let’s ignore all line breaks, so that we have a single string of length 9. Now we just need to find a string in the constant array, that equals to the input string (given that “?” is equal to any symbol).

Problem С. Opencup

Note, that if your team is not in top 30, it doesn’t matter which place it took. So let’s think that the only places available are the places from 1 to 31 (the last place means that we should output 1000). For every place from 1 to 30 let’s check whether we can stay in top 10. The worst case scenario is top 10 teams (excluding yours) take top 10 places in the last Grand Prix. Let’s assign a place to each of top 10 teams in such a way, so they would rank higher than you team. That we can do using simple brute-force. The total amount of operations will then be 31 * 10! * 10, which is about a billion. 31 can be replaced with log 31, and that takes us to about 200 million operations, which will probably be enough to get an OK for the solution, if it is implemented efficiently. Otherwise, several straight-forward optimizations will lead to a success. For example, you can check correctness of a permutation while building it. To eliminate a risk of exceeding the Time Limit, you can use a greedy approach when assigning points to top 10 teams.

Problem D. Cold countries

Let t be the number of pairs (boy + girl) that will eventually sleep next to each other. We are going to solve the problem for each t separately and then sum the answers with coefficients C(p, t). There are 2t! satisfying permutations if we are solving the problem for pairs only. To every such permutation we should now add w — t girls and m — t boys. Between some pairs (or between a pair and a wall) we can put only girls, and between other pairs — only boys. If t is odd, there is x ways to do it (for both girls and boys), where t = 2x — 1. The number of ways to put boys into permutation then looks like this: m! * C(m + x, x). First multiplier describes the order of boys and the second solves a standard combinatorics problem of putting m objects between t walls. We can then simplify the expression and get (m + x)! / x! (the same for girls). So, for an odd t we have an answer 2 * (t!) * (m + x)! * (w + x)! / x! / x!. We will not compute the answer for an even t here, but note, that in this case one should consider two possibilities: when the leftmost person in a first pair a boy and when it is a girl. This solution has O(p * log MOD) complexity, and this is too slow. The second factor appears because of the necessity of performing a division (or finding modular multiplicative inverse). Let’s notice, that we need to find it only for factorials of numbers from 1 to p and 1 / fact[y] = 1/ fact[y — 1] * 1 / y. We can find multiplicative inverse for numbers 1 .. p in O(p log log p) time, using Sieve of Eratosthenes, and then calculate the inverse for composite numbers in O(1), and for primes in log MOD. Also, you could have gotten an OK using only caсhing of already computed values. There is also a linear algorithm for finding multiplicative inverse elements, you can find its’ description in comments to this discussion: http://apps.topcoder.com/forums/?module=Thread&threadID=680416&mc=26&view=threaded

Problem E. Lillebror and Karlsson

Let’s represent a chocolate as a binary string of length m which contains n ones. We now need to split the string into a minimal amount of substrings, that fit our criteria. The resulting partition will contain n strings, of which some consist of ones and zeroes, and some only of zeroes (let’s call them zero-strings). To solve the problem we must minimize the amount of zero-strings. Let f[i] be a minimal number of zero-strings in a partition of a prefix of length i. We are going to initialize f[i] = f[j] if (i + j) / 2 — integer, s[(i + j) / 2] = ‘1’ and there are no other ones between positions i and j. If there is no such j, we initialize f[i] with infinity. Now we need to update f[i] = min(f[i], f[k] + 1]), using all k such that s[k..i] is a zero-string. Using the fact that all such k form a single substring, we can maintain minimum of them and update f[i] using O(1) time. We now have a solution with complexity O(m). Let’s transform it into O(n) solution. Initialization: f[0] = 0; f[i] = 1, if there are no ones to the left from i and s[i] = ‘0’. Now let’s find initial values of f[i] for all positions between the leftmost (first) ‘1’ and the second one. To do that we’ll need to reverse the array f. If the right end of array “covers” the right “1”, then we just need to delete everything after it. If the right end didn’t reach the right “1”, we need to add some values into array (let’s take a minimal value in the array + 1). After that step we have initial values for all positions between first two ones. Now let’s run through array from left to right and update a value on each position to a (minimum on the prefix with the end in this position) + 1. Similarly, we can calculate f[i] for all positions between second and third “1” and so on. Our array is too long, so we need to compress it. If there are x consecutive values y we will store corresponding part of array as a pair (x, y). Now we can add a bunch of equal values (and in this algorithm we only add equal values) in O(1) time. The amount of deleted values is not greater than the amount of added. Finally, let’s notice, that the difference between maximal and minimal values in the array is 1 or less. c — position of the minimal element in the array. To the right from it there can’t be a number greater than c + 1. Similarly, on a previous step we could not have had numbers greater than c + 1 to the left from it. Thus, our array in compressed form never has more than 3 elements, and we can reverse and run through it in O(1) time.

Problem F. Dynamic Complexity of String

For each border of length g there is a period of length T such that g + T = |S|. Because of that, we can find a minimal period of a string by subtracting from its’ length the length of maximal border. This is derived directly from the definitions of period and border (for more information search the Internet for “border array and period”). Furthermore, if the borders are scanned in decreasing order, the prefix function of each next border will be greater, than the previous one, and that means that minimal period will decrease (or stay the same). After calculating a prefix-function we can in O(1) find complexity for each prefix. To do that take the answer for the maximal border and add 1 if its’ period is different from the period of the next border (in decreasing order). We now know how to find an answer and how to write a checker for the problem. What left is to learn how to find the right string. First, it’s useful to look at known “interesting“ strings, for example “random string”, Zimin strings, Thue–Morse strings, Fibonacci strings, string from identical letters and so on (for more information search the Internet for “combinatorics on words”). In this case we can use Fibonacci strings. Note, that solution to this problem has a practical value. Some string algorithms have complexity O(dynamic complexity of string), and solution described above generates worst-case tests for such algorithms. Dynamic complexity of random strings is O(n), so if your problem can potentially be solved using borders’ analysis, you definitely should add such tests to a testset to increase the perfomance time of those algorithms by log n.

Read more »

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

By MikhailRubinchik, history, 19 months ago, In Russian,

Всем привет!

Наверняка многие ещё помнят срачи в комментах посты о квалификационном туре уральского четвертьфинала 2015. Пришло время немного освежить :)

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

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

Вот ссылка на наше информационное письмо в word, чтоб вы могли его подредактировать под себя.

Удачи!

Read more »

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

By MikhailRubinchik, history, 19 months ago, In Russian,

Всем привет!

Завтра состоится основной тур Чемпионата Урала 2016. С расписанием можно ознакомиться по ссылке.

mr146 и HamsterWool проведут для вас текстовую трансляцию основного тура через канал в telegram.

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

Read more »

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

By MikhailRubinchik, history, 21 month(s) ago, In Russian,

Всем привет!

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

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

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

Вот ссылка.

Read more »

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

By MikhailRubinchik, history, 22 months ago, In Russian,

Всем привет!

Легко убедиться, что на ВКОШПе играют школьники из Таджикистана. Достаточно поискать по слову Душанбе. Однако, на полуфинале нет ни одной команды из Таджикистана. Непонятно, куда после окончания школы деваются олимпиадники. Может конечно все поголовно уезжают в другие страны бывшего СССР (или в Иран, тогда и иностранный язык учить не нужно).

Может быть на cf есть кто-то из Таджикистана (или в прошлом из Таджикистана), кто умеет отвечать на этот вопрос? :)

Read more »

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

By MikhailRubinchik, 2 years ago, In Russian,

Всем привет!

Ранее была серия постов (из трёх штук), в которых я подробно описал нашу организацию квалификационного тура чф. Данный пост не является самостоятельным. Это выжимка самых важных моментов из предыдущих. Я протормозил с его написанием, поэтому решил опубликовать его прямо перед полуфиналом. Пользуясь случаем, сообщаю, что я сам уже в Питере. И если вы думаете о том, чтоб провести квалификационный тур в следующем году у себя, ловите меня и задавайте любые вопросы.

Важное напоминание: в этом посте я не отвечаю на вопросы “почему”, а просто перечисляю рекомендации. Аргументы есть в предыдущих. Этот пост можно взять за основу, когда возьмётесь за организацию.

0.Этот пункт новый, я о нём не писал в предыдущих постах, поэтому выделил жирным. Большинство участников ничего не знают о соревнованиях. После соревнования вышлете им письмо с рассказом о том, что такое ACM ICPC. Мы, например, выслали такое письмо.

1.Не проводите многосайтовый чф. Проводите квалификационный тур

2.Называйте квалификацией чф, а не ⅛

3.Во всём массовом пиаре слово “квалификация” отбрасывайте

4.Выберите дату уже весной, чтоб начать работать с площадками до летней сессии и зачётной недели

5.Делайте условия задач на русском

6.Делайте пару задач, которые могут решить люди, не умеющие программировать

7.Делайте задачи простыми, 10 тоталов — это нормально

8.Разрешайте все языки, какие сможете (жизненно необходимы c#, pascal, pascal abc, python)

9.Ставьте халявы в начале комплекта (задачи А, В, С)

10.Подавайте пример другим:

1)завешайте рекламой стены вуза 2)сделайте кучу репостов vk 3)наберите 50 (или хотя бы 20-30) команд своего вуза

11.Создайте площадку в каждом субъекте рф, а лучше в каждом городе, где есть вуз

12.Ведите гуглдок со всеми данными о площадках, со временем их станет слишком много, чтоб помнить. Пусть будет отдельный человек, который готов тратить на это много времени

13.Регистрируйте участников у себя, запрашивая необходимые данные и контакт, чтобы можно было потом узнать недостающие. Наберите команду волонтёров, чтобы они всех регали на бэйлор. Если вам нужна наша система регистрации (с аутентификацией через vk), попросите у нас права к ней. Либо можно (как в мосчф) регать через гуглформы

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

15.Найдите vk (а не почты!) завкафов, деканов и преподов, напишите им и после напомните о себе много раз. Постарайтесь привлечь много вузов

16.Детально пропишите все правила (отбор на основной тур, замены, участие неполных команд). Имейте в виду, что в правилах финала и полуфинала не описаны детали. Будьте готовы разрешать спорные ситуации

Read more »

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

By MikhailRubinchik, 2 years ago, In Russian,

Данный пост — третий в серии постов о квалификационном туре — посвящён задачам и правилам. Начните с чтения первого и второго постов.

1. Подготовка задач. Как сделать задачи и для тех, кто не умеет программировать, и для Dandelion?

Вообще-то такие задачи делать не нужно! На квалификационном туре совершенно нормально иметь десяток тоталов. Лишь бы всем не прошедшим командам было далеко до тотала. В нашем же случае я был не только автором задач, но ещё и тренером, поэтому мне хотелось, чтобы команде Dandelion было чем заняться в последние три с половиной часа контеста.

Read more »

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

By MikhailRubinchik, 2 years ago, In Russian,

Данный пост — второй в серии постов про квалификационный тур. Начните с прочтения первого. После читайте третий :)

Краткое вступление

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

1. Многосайтовость рождает макроорганизаторов

Мы много лет проводим соревнования, но в этот раз впервые проводили соревнование c таким количеством площадок. И когда я только начинал думать о нём, я считал, что объём нашей работы от появления новых площадок увеличится незначительно — отправим организаторам площадок письмо с подробными инструкциями, а дальше всё необходимое они сделают сами.

Оказалось, что это было очень наивно. Конечно, у нас остались все наши обычные задачи по организации контеста и кроме этого добавилась куча задач по “обеспечению многосайтовости” — так называемых “макрозадач”. К ним помимо меня имели отношение Александр Гальперин, Саша Ипатов aka Lich_Sandro и команда волонтёров, возглавляемая Ритой Шадриной, Дашей Ветошко и Мишей Вяцковым. По многим вопросам нам также помогал Олег Христенко. Дальше я расскажу про эти задачи и кто за что был ответственным. Ещё много людей занималось площадкой в УрФУ, но про эту работу я знаю не так много, как про макрозадачи, поэтому ничего писать про неё не буду.

Read more »

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

By MikhailRubinchik, 2 years ago, In Russian,

Всем привет!

Это первый из трёх постов о квалификационном туре четвертьфинала.

UPD: ссылка на второй и на третий

Краткое вступление

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

Ссылка на контест на сервере snark’a:

1) http://opentrain.snarknews.info//team.cgi?contest_id=006274

2) Там должны работать логины и пароли опенкапа

3) если не работают, обратитесь к координатору вашего сектора Опенкапа или напишите о проблеме в комментарии, а Олег прочитает и решит её

Read more »

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

By MikhailRubinchik, 2 years ago, In Russian,

Всем привет!

http://codeforces.com/blog/entry/2381 — 4 года назад e-maxx жаловался, что с DSU какая-то детективная история :)

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

Но мой соавтор по некоторым статьям и просто мой друг, Дима Косолобов*, написал пост на хабре, где приведено доказательство верхней оценки, которое можно понять в течение одной пары. Во всяком случае в УрФУ он провёл лекцию и есть студенты, которые поняли.

Вот ссылка: http://habrahabr.ru/post/266859/

P.S. пост на хабре основан на той самой статье, которую e-maxx собирался изучить в этом комменте http://codeforces.com/blog/entry/2381?locale=ru#comment-50438

*Вы можете помнить Диму по статье на хабре о суффиксном дереве Вейнера.

Read more »

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

By MikhailRubinchik, 2 years ago, translation, In English,

Hi!

You can see presentation and final version of paper.

P.S. Do you know man in photo?

Read more »

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