Всем добрый день.

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

Интересуют соотношения по категориям:

- среди участников использующих русскоязычный / англоязычный интерфейс;
- среди соревнующихся из Div1 / Div2;
- по всем успешным / по всем отосланным задачам.

Анализы типа http://codeforces.com/blog/entry/1917, а также  вроде "статистика среди учеников нашего препода" или комменты вроде "а я счетаю лутшым езыком Scala патому што это убудущее" не очень интересуют. ;-)

UPD: Попробовал сохранить страничку standings.htm с 85 раунда и постучать по ней egrep-ом. Это (я надеюсь) позволило мне определить количество задач, сдававшихся на тех или иных языках (не обязательно сданных):

Div1: C++ 1372, Java 130, Pascal 94, Python 16, PHP 2

Div2: С++ 2990, Java 370, Pascal 447, Python 123, PHP 3

Вот что-то вроде этого и хочется, только более полно и с учётом остальных категорий... (Pascal = Delphi | FPC)... %)

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

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

Я полагаю что:
- если кому-то нужен второй аккаунт в достойных целях (например для совмещения административной и спортивной деятельности), для него нет проблемы указать связь между аккаунтами;
- а если цели достаточно недостойные и такую связь хочется скрыть - то возможно тогда дополнительные аккаунты этого человека с точки зрения сообщества являются злом которое нужно пресекать?

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

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

Или уже?

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

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

В блоге 20 причин... прозвучало:

Тролли приживаются когда можно создавать бурные обсуждения из ничего. А учитывая то что было например в теме "Брак по расчету", можно сказать что люди здесь любят пообсуждать нетрадиционную ориентацию, и другие щекотливые темы

Уважаемые товарищи!

Буду очень признателен если кто-то более умный чем я подскажет оптимизацию алгоритма.

Постановка задачи

Фрагменты строки сравниваются с фрагментами образца с применением нечёткого сравнения.

Входная строка текста разбивается на фрагменты (например, на отдельные слова) и дальше рассматривается как последовательность таких слов:
[T1, T2, ..., Tn]

Образец (шаблон) для сравнения может содержать элементы 3 типов (возможно, вложенные):
1. "Простой" - представляется как последовательность символов в кавычках - например, "стол" - и сравнивается с одиночным словом, давая результат от 0.0 (совсем непохожи) до 1.0 (идентичны).
2. "Последовательность" - представляется как набор дочерних элементов, разделённых запятыми, например "стол", "стоит", "у", "стены". Сравнивает по порядку следования дочерние элементы со словами входного текста.
3. "Выбор" - представляется как набор дочерних элементов разделённых символом "|", например "стол" | "буфет" | "кровать".

Пример сложного шаблона:
("стол" | "буфет" | "кровать"), "стоит", (("у", "стены") | ("на", "полу"))

Как найти результат сравнения со сложным шаблоном?

Естественным казалось ввести такие правила:
а) Результатом "Последовательности" является среднее геометрическое результатов дочерних элементов.
б) Результатом "Альтернативы" является максимальный из результатов дочерних элементов.

Однако возникает проблема в шаблонах содержащих вложенные "последовательности", например:
( "bla" | ("ola", "gde") ) , "chmoda"
Сравним это с "bla ide chmoda" - тогда "альтернатива" выберет лучшим вариант "bla" т.к. он даёт 1.0 тогда как "ola", "gde" даёт только 0.66, однако после этого остаток строки составит два слова "ide chmoda" и сравнение с просто "chmoda" даст для них 0.0, и общий результат будет 0.0.
В то же время, если был бы выбран для "альтернативы" второй вариант, то остаток строки сравнился бы идеально и общий результат был около 0.76.

Простая идея - перенумеровать все простейшие элементы в шаблоне:
("bla"=E1, "ola"=E2, "gde"=E3, "chmoda"=E4)
И построить все возможные варианты сравнения:
E1:T1, E4:T2
E2:T1, E3:T2, E4:T3
Если теперь вычислить среднее геометрическое результатов, приняв T1=bla, T2=ide, T3=chmoda, то мы конечно найдём оптимальный вариант.

Однако это неэффективно, т.к. например:
("bla"|("ola","gde")),("xyz"|"pur"|"lti")
здесь будет уже 6 вариантов, но для строки "bla ide xaz" сравнение "pur" или "lti" с "xaz" дало бы 0.0, и если определить это заранее, то 4 из 6 вариантов можно было бы не рассматривать (тк. ср. геометрическое всё равно будет 0.0). Но как такие вещи "определять заранее"?..

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

с уважением,
Родион

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

Всплыла тема. Давайте её пилить отдельно... %)

Для IT-шника(-цы) обсуждаются несколько возможностей по выбору себе невесты (жениха):
- чтобы она (он) тоже был(а) IT-шницей(ком), причём, со схожим направлением деятельности;
- либо то же самое, но с как можно более отличающейся "деятельностью", например, программист(-ка) + тестировщица(-к) это модель идеальной семьи;
- либо профессионал из другой области науки/искусства (правда ряд инженерных профессий непонятно как расценивать - как IT-шные или нет);
- либо непрофессионал (ну их на фиг, людей увлечённых!)

Сам я в своё время над разными вариантами, в основном среди двух последних, размышлял - и теперь с профессиональной точки зрения у нас с супругой общее лишь то, что мы занимаемся преподавательской деятельностью (правда она - профессионально, а для меня это night-job). В остальном же различия капитальны. Я ей помогаю бороться с антивирусами и браузерами - она же меня учит записывать подобранные мною мелодии в Сибелиусе и умеет растолковать "пачиму тут не 3/4 а 6/8"... Ну а то, какие ученики-школьники теперь ленивые (в среднем) мы можем обсуждать вместе... %)

Так что кто в браке состоит или собирается когда-нибудь состоять, вкратце можете приписать свои мысли... Забавнее всего, впрочем, будет лет через 5-10 их перечитать... %)

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

Задан образец некой фразы, состоящей из нескольких слов
p1 p2 ... pN
С ним сравнивается фраза, из такого же количества слов
w1 w2 ... wN
Т.е. слова разделены пробелами или ещё чем нибудь, не важно - и мы просто сравниваем каждое слово w с соответствующим по порядку образцом p. Результатом такого сравнения является, какой-то критерий e, например, количество опечаток (от 0 до length(p)) - или в принципе какая-то "похожесть" в промежутке [0, 1]... или ошибочность (в том же промежутке... или от 1 до +inf... Критериев можно много придумать и их несложно друг из друга получить... В общем, будет у нас N оценок:
e1, e2, ... eN.

Так вот. Вопрос в том - как оценить "похожесть" (или "релевантность") полного образца (из N элементов) и целой фразы (из N элементов).

Например, сначала я использовал для соответсвия слова элементу образца критерий "ошибочность" (от 0.0 до 1.0) и для фразы в целом брал "ошибочность" как max{e}.

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

Тогда я стал считать их среднее геометрическое. Точнее среднее геометрическое величин, дополняющих "ошибочность" до 1 (назовём это "похожестями"):
e_total = 1 - (П(1-e_i))^1/N

С этой оценкой хорошо то, что если одна из "ошибочностей" равна 1.0, то и общая ошибочность тоже будет 1.0, а если все "ошибочности" равны, то общая "ошибочность" равна ошибочности каждого из элементов.

Теперь однако выходит что если, например, сравнивается фраза из 3 слов и из них два безошибочны, то третье может иметь ошибочность около 0.65... Т.е. в общем оно может оказаться почти непохожим на элемент образца.

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

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

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

В кабачке на Марсе зелёные человечки имеют возможность сыграть в простую азартную игру. Крупье бросает 6 одинаковых игральных костей в форме додекаэдров (правильный 12-гранник с 5-угольными гранями). Каждый из играющих перед этим загадывает одно из чисел, присутствующих на гранях (скажем, от 0 до 11). Если загаданное игроком число не выпало ни на одной кости, он платит крупье 1 евро (да-да, и туда добрались!), в противном случае крупье сам платит игроку столько евро, на скольки костях выпало загаданное число (т.е. от 1 до 6).

Определить требуется, конечно, матожидание выигрыша крупье после того как он сыграл, скажем, с миллионом желающих. Кости совершенно честные (т.е. каждая грань выпадает с равной вероятностью 1/12).

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

Провёл опрос среди коллег и учеников. Посмеялся.

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

А вы знаете?

Можете просто ответить - знаете или нет. Объяснение я хотел под катом привести, но он как-то не очень работает.

Однако если вы не знаете объяснения - попробуйте догадаться. Пожалуй стоит намекнуть что область применения - поиск не по массиву значений (вспомните когда ещё нужен двоичный поиск).

Не секрет, что существуют два противоположных взгляда на олимпиадное (спортивное?) программирование:

Первый из них - почёт и уважение лучшим, вплоть до благоговейного трепета.

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

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

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

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

Впрочем обсуждать это всё долго, да и много на эту тему говорилось, даже здесь, по блогам уважаемых людей:
http://codeforces.com/blog/entry/1851
http://codeforces.com/blog/entry/2047
и т.п.

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

- работаете ли вы программистом/тестировщиком, и т.п. (если да, то как часто доводилось заниматься интересными алгоритмическими задачами - мне, скажем, раза 4 за два года, притом больше околоматематическими алгоритмами);
- работаете ли вы "математиком/аналитиком-программистом" (или как называется ваша должность) - т.е. человеком который на практике занят разработкой, модификацией или внедрением достаточно неординарных алгоритмов в проектах;
- работаете ли вы в решительно иной отрасли (в инженерной - или нет?);
- либо не работаете пока вообще, но собираетесь (или не собираетесь) работать в IT, даже с учётом того что "интересных задачек" там отнюдь не так много и достаются они обычно либо лучшим, либо везучим... ;-)

Заранее спасибо.

По просьбе freopen.

В селе живут девушки-пастушки. В рамках здоровой конкуренции они подкладывают друг другу свиней. Подложенную свинью девушка должна распознать, при этом распознавание каждой следующей свиньи происходит за время на q процентов меньшее, чем предыдущей. Время распознавания 1-й свиньи девушкой будем называть профессионализмом девушки p (чем меньше, тем лучше).

(Если девушке подкладывают свинью, геометрически идентичную одной из предшествующих, то она распознаётся за время 0. Т.о. задача рассматривает только геометрически различных свиней. Свиньи похожие с точностью до отражения/поворота - идентичны.)

Итак, есть набор K девушек с разным количеством измерений. Размерность каждой девушки - целочисленная, при этом наименьшая 2, наибольшая K+1.

N-мерной девушке нужно подкладывать только N-мерную свинью. Такая свинья состоит из N+1 органов, которые мы в рамках задачи не различаем. Органы имеют форму N-мерного куба со стороной 1 и в составе свиньи они соединены N-1-мерными гранями. Если у свиньи есть хотя бы одна ширина меньшая 2, то такая свинья дефектная и не участвует в задаче т.к. не может считаться полностью N-мерной.

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

Входная строка содержит числа K и q (int и double). Выходная должна содержать K чисел (double) показывающих, какой профессионализм должна иметь каждая из девушек (по порядку возрастания размерности девушки) чтобы победила дружба.

Выдать любое решение с точностью до 1e-9. K меньше 15, q меньше 100 и кратно 10.

Пример:
2 50
15 10

Вариант: выдать решение с точностью до 1e-3.

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

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

На поле девушки пасут свиней. При этом всего насчитывается 106 ножек и 336 сисек. Сколько голов?

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

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

Решение подписывать не стоит т.к. оно очевидно. Ответ тоже... Просто проверьте себя при желании (и наличии чувства юмора)... ;-)

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

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

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

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

(я не имею в виду что topcoder добился высот в борьбе с мошенничеством - там свои проблемы есть, но от этого не лучше, ведь так?)

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