Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы28.05.2016 22:03

Заключительный этап: индивидуальная и командные части

a40b7a97fe04447981693a91fd950afb.jpg
А это школьники, которых неоднократно побеждал в футбол встречал в лагерях GOTO и на хакатоне.

Заключительный этап олимпиады состоит из двух частей: индивидуальное решение задач по предметам (математика, информатика) и командное решение инженерное задачи. На индивидуальное решение задач дается по 2 часа на один предмет. Задачи по математике и информатике общие на параллели 9 и 10–11 класс. Решение каждой задачи дает определенное количество баллов (см. критерии оценки далее). По математике за каждую задачу можно получить от 0 до указанного количества баллов в соответствии с описанными критериями.

Баллы по информатике зачисляются в полном объеме за правильное решение задачи.

Решение задач по информатике подразумевало написание задач на языке Python. Участники получают оценку за решение задач в совокупности по всем предметам данного профиля (математика и информатика) — суммарно от 0 до 24 баллов.

Задание по математике 3.1.1в (2 балла).
Группа граждан страны А эмигрировала в страну Б, а группа граждан Б — в страну В. В результате этого рейтинги каждой страны оказались выше первоначальных. После этого направление миграционных потоков изменилось на противоположное — часть жителей В переехала в Б, а часть жителей Б — в А. Оказалось, что в результате рейтинги всех трех стран опять выросли (по сравнению с теми, которые были после первого переезда, но до начала второго). (Так, во всяком случае, утверждают информационные агентства этих стран.) Может ли такое быть (если да, то как, если нет, то почему)? (Предполагается, что за рассматриваемое время Q граждан не изменилось, никто не умер и не родился.)

Задача по математике 3.1.2 (6 баллов)
Администрация социальной сети ВКонтакте решила создать сообщество «Всех тех, у кого меньше половины друзей состоит в этом сообществе». Для этого им нужно включить в сообщество пользователей так, чтобы в итоге:

  • у всех, кто в этом сообществе, меньше половины друзей были в нем же;
  • у всех, кто не в этом сообществе, не меньше половины друзей были в нем.


Всегда ли им удастся создать такое сообщество?
(Предполагается, что пользователи не сами вступают в сообщество, а распределяются администрацией социальной сети)

Решение есть тут на странице 191.

Задача по информатике 3.2.4 «Итоговая аттестация» (3 балла)
Конец года — беспокойное время не только для школьников, которые готовятся к экзаменам, но и для составителей экзаменационных заданий. Составляя любой тест, необходимо учитывать, насколько сложной будет задача для школьников, и определить, сколько учащихся сдадут тест успешно.

В этом году было решено провести тестовый экзамен, пригласив 100 учеников разных школ решить 5 задач. Каждая задача оценивается в ai баллов. Задача либо решена на полный балл, либо не решена совсем, а значит за нее не начисляются баллы. Частичные решения проверяющие не учитывают. После экзамена составители получили результаты школьников. Для каждого школьника известны результаты проверки всех задач.
Необходимо посчитать, сколько школьников получит не менее K баллов, если экзамен будут сдавать 1000000 школьников.

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

Формат входных данных:
В первой строке дано число K — число баллов, необходимое для успешной сдачи теста. Во второй строке 5 натуральных чисел — баллы за задачи. Первое число соответствует баллам за первую задачу, второе — за вторую и так далее. Далее следует 100 строк. В каждой строке 5 чисел, обозначающих, решена ли соответствующая по номеру задача или нет. На первом месте в строке указано решена ли первая задача, на втором решена ли вторая, и так далее. Если задача решена, то в строке будет указана 1, если нет — 0.

Формат выходных данных:
В единственной строке выведите ожидаемое число людей, которые успешно сдадут тот же тест если решать его будет 1000000 школьников.

Решение есть тут на странице 200.

Командная часть

a306d793b2eb42ffb564e6d33e00706b.jpg

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

Участники должны были писать программы на языке Python. Продолжительность командной части заключительного этапа — 3 дня (всего 18 астрономических часов). Участники имели доступ к сети Интернет и могли пользоваться своими телефонами и ноутбуками.
Всего командам предлагалось 3 задачи — по одной на каждый день. Условие задачи становилось известно участникам утром соответствующего дня. Для каждой задачи было подготовлено два подграфа реальной социальной сети «Одноклассники»:

  • участникам представлялся специально подготовленный, очищенный и анонимизированный подграф;
  • проверка качества решения осуществлялась автоматически на полном графе, в котором присутствовали данные, вычищенные из первого графа.


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

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

Граф пользователей
Граф сохранен в формате разреженной матрицы, где по каждой связи есть информация о ее типе (родственник, друг и т.д.) в виде битовой маски. Каждая строка матрицы соответствует друзьям одного пользователя и имеет формат:
ID_пользователя1 {(ID_друга1, маска1), (ID_друга2, маска2), …}

Матрица партиционирована по ID пользователя на 16 файлов, каждый из которых сжат стандартным протоколом сжатия GZip.
Пары в списке связей отсортированы по ID друга (по возрастанию). Пример записей из графа:
102416
{(5362439,0),(7321627,0),(7345280,0),(9939258,0),(9976393,0),(11260492,0),
(11924364,0),(16498676,0),(16513827,0),(21716731,0),(21826340,0),(23746537,0),
(23751503,0),(24412936,0),(24423533,0),(30287856,0),(32321147,0),(34243036,0),
(37592142,0),(39485706,0),(41505243,0),(42791620,0),(52012206,0),(52671472,0),
(54652307,0),(57293803,0),(59242794,0),(59252048,0),(62535397,0),(62563866,0),
(62567154,0),(64588902,0)}
102608
{(4167808,32784),(6019974,32),(6152844,16),(9570536,64),(10699806,33),
(13290514,0),(15064491,128),(16432948,512),(24473204,0),(24655822,0),
(25833075,256),(28000951,64),(30834507,2048),(34567533,16),(35766667,0),
(37385121,0),(40123805,512),(43134386,1024),(45439608,0),(45484652,0),
(47562525,0),(52378153,256),(52403136,512),(52493894,1024),(53483990,0),
(54048767,0),(54286279,2048),(57401158,0),(57956631,0),(58183281,0),
(61117236,32),(61898065,0),(61936634,0),(64512205,512),(65014849,0),
(65112662,0),(65259449,0)}

В маске связи могут быть установлены следующие биты:

  • Любовь
  • Супруг или Супруга
  • Родитель
  • Ребенок
  • Брат или сестра
  • Дядя или тетя
  • Родственники
  • Близкие друзья
  • Коллеги
  • Одноклассники
  • Племянник
  • Дед или бабушка
  • Внук или внучка
  • Однокурсник
  • Дружба в армии
  • Приемный родитель
  • Приемный ребенок
  • Крестный отец
  • Крестный сын
  • Совместная игра в спортивные игры


Помимо перечисленных битов в маске отношений может быть установлен, а может и не быть установлен нулевой бит. Этот бит играет чисто техническую роль и не имеет физического смысла. В итоге, например, отношение типа Ребенок может кодироваться числами 16 или 17.

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

Демография пользователей
Данные о демографии предоставлены для того же миллиона пользователей, что и информация о социальных связях в формате списка атрибутов:
userId create_date birth_date gender ID_country ID_Location loginRegion
где:

  • userId — идентификатор пользователя
  • create_date — дата создания пользовательского аккаунта (количество миллисекунд от 01.01.1970)
  • birth_date — дата рождения пользователя (количество дней от 01.01.1970, может быть отрицательным!)
  • gender — пол пользователя (1 — мужчины, 2 — женщины)
  • ID_country — идентификатор страны, указанной в профиле
  • ID_Location — идентификатор региона/города, указанный в профиле.
  • loginRegion — идентификатор региона, откуда чаще всего авторизуются в данной социальную сети пользователь (может отсутствовать!)

Пример данных:
44053078 1166032023073 3067 1 10414533690 2423601 99
12495764 1177932393270 1138
2 10405172143 188081
25646929 1165304175170 3756 2 10414533690 3953941 22
25646999 1160728984480 3884 2 10414533690 241372 120
12495833 1176909723643 3363 2 10414533690 2724941 11

Демография партиционирована по той же схеме, что и граф, но не сжата (передается в виде открытых текстов). Так же может быть обработана с помощью стандартного инструмента хранения больших данных Apache Pig или любого другого инструмента, поддерживающего CSV.

Задачи


Задача 4.2.1 «Дата рождения»
Представленный для анализа фрагмент социального графа включает информацию о связях 100 тысяч пользователей, попавших в двухшаговую окрестность сотни случайно выбранных пользователей. Участникам предоставляются файлы графа социальной сети со всеми связями и файл демографии, в котором указан данные по пользователям, включая возраст, однако возраст указан не для всех пользователей.

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

Данные записываются в файл в формате:
(\t (знак табуляции))

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

Базовое решение задачи на стр 208.

Задача 4.2.2 «Регион»
Представленный для анализа фрагмент социального графа включает информацию о связях 100 тысяч пользователей, попавших в двухшаговую окрестность сотни случайно выбранных пользователей. Участникам предоставляются файлы графа социальной сети со всеми связями и файл демографии, в котором указан данные по пользователям, включая регион, однако регион указан не для всех пользователей.

По пользователям которые присутствуют в графе, но не присутствуют в демографии необходимо установить их аттрибут ID_Location (регион).

Ответ записывается в текстовый файл в формате:
(\t (знак табуляции))

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

Базовое решение задачи на стр 213.

Задача 4.2.3 «Поиск связей»
Представленный для анализа фрагмент социального графа включает информацию о связях 1 миллиона пользователей, попавших в двухшаговую окрестность сотни случайно выбранных пользователей. Участникам предоставляются файлы графа и демографии по пользователям. Часть связей в предоставленном социальном графе скрыта и задачей участников является максимально полно и точно раскрыть их.

Сокрытие связей коснулось только пользователей из исходного миллиона, остаток от деления аттрибут ID которых на 11 равен 7 (id % 11 == 7), сокрытию подверглось порядка 10% связей для каждого из этих пользователей. Были скрыты только ведущие в исходный миллион связи.

В прогнозе достаточно восстановить наличие связи, ее тип не важен. Результаты прогноза нужно представить в формате CSV файла вида:
ID_пользователя1 ID_кандидата1.1 ID_кандидата1.2 ID_кандидата1.3
ID_пользователя2 ID_кандидата2.1 ID_кандидата2.2

Записи в файле отсортированы по ID пользователя (по возрастанию), а затем по предсказанной релевантности кандидатов (по убыванию, саму релевантность при этом в файл писать не надо). Пример результатов:
5111 178542 78754
18807 982346 1346 57243

Результаты участников оцениваются с помощью метрики Нормализованной скидочной совокупной выгоды (Normalized Discounted Cumulative Gain, NDCG), используемой в индустрии для оценки точности работы алгоритма для этой и аналогичных ей задач. Метрика рассчитывается отдельно по каждому из пользователей, для которых есть скрытые связи, а затем усредняться. Записи в файле результата, не имеющие отношения к
пользователям со скрытыми связями, при оценке результата учитываться не будут. Если по какому-то пользователю не будет предложено ни одного кандидата, то значение метрики для него будет считаться за 0.

Базовое решение задачи на стр 216.

© Habrahabr.ru