Магия слов и чисел

Я пропарсил результаты прошлого регионального этапа ВОШ в Московской области, чтобы убедиться, что ФТЛ — лучшее место для падаванов (да). Среди прочих любопытных статистик я решил посчитать, по каким предметам победители региона, проходящие на Всеросс, еще имеют призеров или победителей.

Это можно трактовать как «чтобы выйти на Всеросс по предмету А, поботайте предмет Б». Может показаться, что такое совмещение пойдет не на пользу предмету А. Однако, в то время как только 20% призеров-и-выше выходят на Всеросс, среди совместителей таких уже 30-35%, с незначительным снижением в 11-м классе, когда накал конкуренции достигает максимума.



( Спекуляции под катомСвернуть )

А еще сегодня все прогрессивное человечество поздравляет меня с миллиардом прожитых секунд.

Грядущему Дню знаний посвящается.

Принтер, флэшка (папки с именами "номер семестра. Предмет"), мобильник с хорошей камерой
    стоит фотографировать все сдаваемые работы
А4, файлы, папка с держателем для файлов
одна тетрадь на кольцах с бумагой в точку (или неяркую клетку), лучше А4; запасные блоки; разделители; подписываемые прозрачные цветные клейкие закладки
     как только тетрадей становится ДВЕ, это убивает 2/3 преимуществ
     оптимальнее всего писать строчки высотой в одну клетку, делать кратные клетке отступы outliner-style
     используйте повсюду одни и те же сокращения, матнотацию вместо слов где можно
     подписывайте нумерацию и даты лекций-семинаров
черные гелевые ручки (например, Pilot G-Tec-C 0.4 или тоньше), как можно больше; штрих; красная и зеленая гелевая ручка для акцентов, проверки
степлер+скобки, скрепки
механический карандаш, ластик
     линейка не нужна, длинное подчеркивание это плохо, схемы и чертежи в конспектах гораздо быстрее делать ручкой от руки после небольшой практики

Если учебник есть на либгене, в бумажном виде он вам не нужен

Иногда полезны: ножницы, скотч

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

Это продолжение части 1.

( ПродолжениеСвернуть )

Это теоретический минимум по STL для занимающихся спортивным программированием, подмножество возможностей стандартной библиотеки C++, полезных для решения алгоритмических задач. Группировка преимущественно по заголовку и контексту использования. Почти все упоминаемые имена лежат в пространстве имен std, для него и только для него  следует использовать после #include




<iostream>, <iomanip>
    cout, cin, while (cin >> ...)
    getline, while+getline, getline после cin
    <iomanip>: fixed, setprecision, setw, setfill, hex/dec
    <iomanip>: noskipws/skipws
    cin/cout.tie(0); cin/cout.sync_with_stdio(false); endl vs '\n'
<cstdio>: printf/scanf для жирных инпутов
<vector>
    clean != empty
    begin, end, rbegin, rend
    push_back, pop_back, emplace_back, front, back
    insert
    size, resize, capacity, reserve, swap hack/shrink_to_fit
    vector<bool>
<string>
    string(10, ' '), std::string("a") + "b"
    length/size, substr
    push_back
    to_string, stoi
    find, rfind, find_*_of, string::npos
<sstream>: stringstream ss("str"), ss.str()
<cctype>
    isalpha, isalnum, isblank, isdigit, islower, isupper, isxdigit
    tolower, toupper, использование совместно с transform
<deque>
<queue>: priority_queue
<tuple>: pair, make_pair, .first/.second; tuple, make_tuple, get<#>();
Лексикографическое сравнение
<map>, <set>
    map, сортированность ключей
    [key]= vs at, for (auto kv : mapa) { }
    count, erase
    set, insert
<unordered_set>, <unordered_map>
    std::hash<T>::operator()
<algorithm>
    min, max, minmax, max_element, min_element
    sort, предикат с tie, stable_sort, is_sorted
    sort/iota + next_permutation
    unique/remove/remove_if + .erase
    reverse
    fill, copy, copy_n, <iterator>: back_inserter, istream_iterator
    most vexing parse
    find, find_if, count, count_if
    search
    includes, set_union, set_intersection, set_difference, set_symmetric_difference
    lower_bound/upper_bound
<iterator>: begin(cont), end(cont), size(cont)
<numeric>: accumulate, partial_sum, iota
<cmath>
    hypot, atan2, pi = atan(1) * 4
    round, floor, ceil
    abs
<complex>
<limits>: numeric_limits<int>::max()
<random>
<utility>: swap
<bitset>
<chrono>: std::chrono::high_resolution_clock::now()
<functional>
Compiler-specific: __builtin_popcount, __builtin_clz, __builtin_ctz, __gcd, __int128


Объяснения к каждому пункту под катом. Соавтор — udpn. Большинство примеров кода любезно предоставлены Evil_Stivie.

Еще вас могут заинтересовать:
Лексика решений TopCoder
Гримуар C++


( РазвернутоСвернуть )

Продолжение в части 2.

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

Ya.Algo

11 фев 20:00 МСК	Разминочный раунд (1 ч 40 мин), проходят все, решившие хотя бы одну задачу
17 фев 00:00	Квал (1 ч 40 мин виртуально из 48 часов), проходят все, решившие хотя бы одну задачу
3 мар 10:00 13 мар 21:00 8 апр 15:00	Раунды 1, 2, 3 (1 ч 40 мин), по баллам гран-при 30 и минимальному занятому месту: лучшие 256 (в прошлом году было 512) получают футболки, лучшие 25 проходят
5 мар 10:00 2 апр 10:00	Оптимизационный трек, раунды 1, 2 (по 7 дней), одна оптимизационная задача, 128 футболок, призы 100-70-50 круб
16 мар 19:00	Machine Learning трек (31 день), 128 футболок, призы 100-70-50 круб
19 май	Финал (СПб), призы 300-150-90 круб

VK Cup
Для участников 14-23 лет.

24 фев 18:35 МСК 2 мар 18:35 МСК	Квал 1, 2 (сутки), проходят по 500
10 мар 18:35	Раунд 1 (2 ч), проходят 400
17 мар 18:35	Уайлд-кард раунд 1 (2 ч), проходит еще 50
24 мар 18:35	Раунд 2 (2 ч), проходят 100
19 апр 18:35	Уайлд-кард раунд 2 (неделя), проходит еще 20
29 апр 18:35	Раунд 3 (2 ч), проходят 20
TBD	Финал

Google Code Jam
Вместо сабмита выходного файла с этого года в качестве решений принимается код программы на C, C++, Python, Java, Bash или Go.

6 апр 23:00 UTC	Квал (27 часов), проходят все, набравшие некоторое количество баллов
14 апр 01:00 29 апр 16:00 5 май 09:00	Раунд 1A, 1B, 1C (2.5h), проходят по 1500 (было 1000) из каждого
19 май 14:00	Раунд 2, проходит 1000 (было 500) и получают футболки
9 июн 14:00	Раунд 3, проходит 25
10 авг	Финал (Торонто), призы $15k-$2k-$1k

TopCoder Open
Из первых двух раундов убрали субраунд C.

22 апр 04:00 МСК 3 май 14:00 МСК	Квал 1A, 1B, до 2500 участников в каждом, проходит по 750 + топ250 по рейтингу
2 июн 19:00 14 июн 18:00	Раунд 2A, 2B, проходит по 200 (было 40)
7 июл 19:00 20 июл 04:00	Раунд 3A, 3B, проходит по 50 (было 5), футболки всем участникам
28 июл 19:00	Раунд 4, проходит 14
25 авг 19:00	Online Wildcard, проходит 2 Для прохода в Wildcard, надо войти в топ10 на одном из региональных онсайтов, которые TBD
TBD	Финал, призы $10k-$1.5k-$0.5k

Facebook Hacker Cup

6 июл 17:00 UTC	Квал, 72ч, проходят все, решившие хотя бы одну задачу
21 июл 17:00 UTC	Раунд 1, 24ч, проходят все с 35+ баллами
4 авг 17:00 UTC	Раунд 2, 3ч, топ500 получает футболки, топ200 проходит
18 авг 17:00 UTC	Раунд 3, 3ч, топ25 проходит
25-27 окт	Финал

ICFPC: 20 июл 16:00 UTC

Internet Problem Solving Contest: 6 окт 15:00 UTC

Даты еще не объявлены:

Russian Code Cup

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

• Почти целый год трудился на благо Музея и мало писал в ЖЖ;
  
• повелевал с товарищами CTFы, почти обеспечив себе топ-500 по итогам года, написал по этому делу гайд; по остальным дисциплинам триатлона хорошей компании не было и уровень снизился;
  
• немного прокачал английский и сдал TOEFL на 102/120;
  
• приняли в EPFL, но без финансирования, так что мой PhD опять откладывается;
  
• обновил ноутбук до зверь-машины MSI Stealth Pro GS73VR 7RF;
  
• побывал на органном концерте Баха;
  
• принял в дар кубик Рубика dayan и, наконец-то, запомнил алгоритм сборки.

фильмы Открытая книга (1977), Пассажиры, Джон Уик
Как «Укрощение огня» программное произведение инженерного пафоса, так «Открытая книга» программное произведение медико-биологического пафоса.
игры Mass Effect Andromeda, Stellaris
книги Уоттс. Эхопраксия, Пратчетт. Плоский мир
контесты IPSC, Ya.Algo, picoCTF, DEF CON CTF Quals, H4ck1t CTF
альбомами порадовали Ayreon, Edenbridge, Amberian Dawn


Всех с Новым Годом! :-)
Что бы вы хотели изучить в наступающем году?

Это продолжение поста об ABCTF.

( Write-upСвернуть )

В этом посте я расскажу про одну из дисциплин триатлона — соревнования по информационной безопасности CTF. CTF расшифровывается как Capture The Flag. Изначально соревнования такого рода представляли собой противоборство двух команд, каждая из которых пыталась взломать сервера другой и не допустить взлома своих, поддерживая, тем не менее, их доступность. Этот формат многим (включая меня) не нравится. Я предпочитаю формат Jeopardy, похожий на одноименную игру («Своя игра»): задачи различной стоимости разделены на несколько категорий, а положение команды вычисляется из суммы стоимостей решённых задач.

Традиционными категориями являются Cryptography, Web hack, Reversing, Forensics. В последнее время всё чаще на соревнованиях встречаются новые категории: Algorithms, похожая на алгоритмическое спортивное программирование, и Reconnaissance, про разведку по открытым источникам в интернете.

В процессе решения задачи, будь то взлом криптоалгоритма, реверсинг какого-нибудь запутанного бинарника или поиск нужного аккаунта в сети, участники находят флаги — короткие опознаваемые строки. Они отправляются автоматическому чекеру в качестве решения. Например, на описываемом контесте флаги имели вид abctf{s0m3th1ng_s1m1l4r}.

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

Если вы заинтересовались темой, почитайте учебник от UFO CTF.
Список предстоящих соревнований


( Write-upСвернуть )

Разбор категорий Reconaissance, Programming, Web Exploitation, Reverse Engineering, Binary Exploitation в следующем посте

Сегодня самый подходящий день, чтобы посмотреть «Укрощение огня», если вы еще не.

Несколько лет назад камраду udpn встретилась на онлайн-тесте из собеседования головоломка типа «Продолжите ряд», на 4.5 минуты. Ко мне только сейчас пришла идея, как она решается, и я хочу проверить свою гипотезу хайвмайндом.

Ко мне пришла замечательная идея. Не секрет, что отечественное кино, лишенное бдительного надзора советских художественных комиссий, в подавляющей массе неотличимо от массы, из которой произошло. Однако любая серьезная страна должна иметь независимый кинематограф, наполняющий культурное пространство произведенными локально смыслами, а значит и вынуждена финансировать этот кинематограф из государственных фондов. Ни для кого не секрет, что две трети Голливуда финансируются из колоссальных бюджетов американской оборонки и шпионов, примером тому хотя бы киновселенная Marvel, спонсируемая ЦРУ, давно переставшая умещаться в голове даже у фанатов. Такая культурная интервенция позволяет серьезно экономить на создании боеспособной армии, пригодной, например, для быстрого отнятия Мосула у своих же бородачей.

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

Я предлагаю, следуя популярному тренду, возложить непростую задачу оценки отечественных кинолент на роботов! Министерство культуры вполне может заключить договор, например, с Яндексом, о создании нейросетевого или матрикснетического метода оценки фильмов. Робот, получив на вход достаточно качественную полную копию фильма, исследует и выучивает значимые и доступные для выделения фичи вроде ритма произведения, качества спецэффектов, искренности актеров, лексики текстов, калькирования классики, и отдает на выходе предсказание рейтинга на Кинопоиске. Минкульт лишает государственного миллиона режиссеров, чья лента не смогла получить хотя бы 7.0. Уверен, что в обеих организациях найдется масса людей, которых заинтересует такой проект :)

Слава роботам!

Все знакомы с символом ☯, сообщающим о единстве инь и ян, 0 и 1, о знании, составляющем структуру вещей, описываемом в бинарной форме. Долгое время, вплоть до появления теории информации Шеннона философы были в общем удовлетворены этим символом, зачарованные его изгибами и мнимой глубиной. С развитием науки необходимость не только учитывать принципиальную неполноту нашего знания о мироздании, но и понимание того факта, что эта неполнота и является источником информации, которая уже может быть описана нулями и единицами, привело к многочисленным усилиям философов доработать столь узнаваемую схему. До недавнего времени наиболее удачной попыткой, все чаще цитируемой, была такая:



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

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

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

( ВнутриСвернуть )

Facebook Hacker Cup

7-10 янв 0:00 UTC	Qualification Round (72h), проходят все, решившие хотя бы одну задачу
14 янв 18:00 UTC	R1 (24h), проходят все с 30+ баллами
21 янв 18:00 UTC	R2 (3h), топ500 получает футболки, топ200 проходит
28 янв 18:00 UTC	R3 (3h), топ25 проходит
TBD	Onsite Final

Google Code Jam

7 апр 23:00 UTC	Qualification Round (27h)
15 апр 01:00 UTC 22 апр 16:00 UTC 30 апр 09:00 UTC	Online Round 1A, 1B, 1C (2.5h), проходит 1000 из каждого
13 май 14:00 UTC	Online Round 2, топ1000 получает футболки, проходит 500
10 июн 14:00 UTC	Online Round 3, проходит 25
11 авг	Onsite Finals (Дублин), призы $15k-$2k-$1k

TopCoder Open

1 апр 16:00 UTC 8 апр 16:00 UTC 6 май 16:00 UTC	Round 1A, 1B, 1C, проходит по 750 из каждого + топ250 по рейтингу
20 май 15:00 UTC 8 июн 16:00 UTC 22 июл 16:00 UTC	Round 2A, 2B, 2C, проходит по 40 из каждого
5 авг 16:00 UTC 19 авг 16:00 UTC	Round 3A, 3B, участники получают футболки, проходит по 5 из каждого
16 сен 16:00 UTC	Wildcard, проходит 2 Для прохода в Wildcard, надо войти в топ10 на одном из региональных онсайтов: в Остине (Техас), СПб (7 май), Пекине, Варшаве, Питтсбурге (Пенсильвания), Индии
TBD	Onsite Semifinal 1, Semifinal 2, Finals (в городе TBD), призы TBD

Russian Code Cup

2 апр 19:00 МСК 16 апр 12:00 МСК 29 апр 14:00 МСК	Квалификационные раунды (2h), проходит по 200 человек
14 май 13:00 МСК	Отборочный раунд (2h), 200 лучшим футболки, проходит 50 человек
8 сен	Финал, призы снова урезали до 150 круб. - 100 - 65 - 30 - 15

Ya.Algo

22 апр 16:00 МСК	Разминочный раунд (1h40m), проходят все, решившие хотя бы одну задачу
29 апр 00:00 МСК	Квалификационный раунд (1h40m виртуально из 48 часов), проходят все, решившие хотя бы одну задачу
6 май 00:00 МСК	Марафонский раунд (48h), одна оптимизационная задача
14 май 10:00 МСК 27 май 23:00 МСК 4 июн 15:00 МСК	Раунды 1, 2, 3 (1h40m), по баллам гран-при 30 и минимальному занятому месту: лучшие 512 получают футболки, лучшие 25 проходят
17-18 июл	Финал (Москва), призы 300 круб. - 150 - 90

Internet Problem Solving Contest: 8 июл 10:00 UTC
ICFPC: 4-7 авг