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



    — Вовочка, бросай свои эксперименты с холодным ядерным синтезом, иди к ЕГЭ готовься.
    — Ща, мам.

    Олимпиады — это круто. Они позволили такому раздолбаю свободолюбивому и умном, как я, поступить в университет без экзаменов.

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

    — Что вы сегодня на час опоздали?
    — Да так, в универ поступали.

    Я очень рад, что нашлись инициативные ребята, которым не все равно, что талантливый школьник-инженер тратит свои последние беззаботные годы, судорожно готовясь к сдаче ЕГЭ, вместо того, чтобы строить реактивные ранцы или программировать зародыш искусственного интеллекта.

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

    Недавно в ВДЦ «Орленок» прошел «тест-драйв» Всероссийской инженерной олимпиады. Участвовали 5000 детей со всей России, до финала дошли около 100 человек. Призов много, но самое полезное — по +10 очков к ЕГЭ.

    Я за всем присматривал и готов поделиться своими впечатлениями.

    Олимпиада шла по четырем профилям.

    Про первые два профиля расскажу здесь (чуток задач и фоток), про вторые два — немного попозже на GT.
    (UPDотчет про «Космические системы».)


    Организация


    Олимпиада состояла из двух заочных этапов и двух очных (индивидуальный и командный).

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

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

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

    В общем, после окончания олимпиады организаторы две недели готовили «кирпич» на 1000 страниц с описанием всего, что только можно, отправили в РСОШ и теперь сидят на низком старте, чтобы начать готовить олимпиаду следующего года. Официальный ответ будет 1 сентября, но орги рисковые ребята и начнут писать задачи и готовить лекции с хакатонами уже летом.

    Итоги Олимпиады — nti-contest.ru/results2016
    Мануал на 400 страниц по олимпиаде лежит тут.

    Орленок


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

    Встречают вас «противотанковыми ежами»


    Внутри вот такие штуки, по которым можно полазить и поковырять.

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

    Учебно-боевой самолет




    Рядом с корпусом «Космический»


    Сразу вспомнился Кастанеда




    Big Data



    Немного о том, что было на треке по большим данным и машинному обучению.

    image

    image
    Это Иван. Он большой и добрый. Он читал мастер-класс по питону, рассказывал про числодробилки и о том, какие задачи человек решает лучше чем компьютер (принадлежность точки к группе, например)

    Первый отборочный этап

    Первый отборочный этап


    Первый отборочный тур проводится индивидуально в сети интернет, работы оцениваются автоматически средствами системы онлайн-тестирования. На решение задач первого отборочного этапа участникам давалось 3 недели. Решение каждой задачи дает определенное количество баллов. Для всех участников предлагается общий набор задач, но за решение задач участникам разных уровней (9 класс или 10-11 класс) давались разные баллы. Баллы зачисляются в полном объеме за правильное решение задачи. Участники получают оценку за решение задач в совокупности по всем предметам данного профиля (математика и информатика) — суммарно от 0 до 20 баллов.

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

    Решение
    Изобразим путь космонавта на графике. По вертикальной оси отложим время, а по горизонтальной расстояние. Изначально космонавт находится в точке s=0, а комиссия в точке s=5.

    На рисунке обозначен путь для последовательности ППЛПППП:



    Заметим также, что космонавт может прийти к комиссии только на нечетных шагах.
    Таким образом, нас интересует, сколько существует путей, ведущих к комиссии за 5, 7 и 9 секунд.
    Переформулируем задачу: сколько существует путей, по сетке на рисунке ниже, ведущих к прямой s=5. Ходить можно только двигаясь вверх.



    Посчитаем количество таких путей для каждой точки, начиная от начальной.



    За 5 шагов приводит 1 путь, за 7 — 5 путей, за 9 — 20 путей.

    Значит искомая вероятность равна 1/32+5/128+20/512 = 7/64

    Ответ: 7/64



    Задача по информатике 1.2.2 «Корни» (3 балла)
    У мальчика Пети есть число N. Но оно ему не нужно, в отличие от числа X. Чтобы его получить Петя может брать целочисленный корень, умножать и складывать числа.

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

    Для Пети взятие целочисленного корня — тяжёлая задача, и он хочет минимизировать суммарную степень корней, которые встречаются в формуле получения X.

    А ещё у Пети есть старший брат. Которого зовут Дима. Этот Дима решил добавить интереса задачке Пети, и дать такие ограничения:
    1. Пете нельзя брать корни от чисел, отличных от N.
    2. Можно перемножать только те числа, которые Петя получил с помощью операции взятия корня или умножения других чисел.
    3. Складывать можно числа, которые получены как результат умножения, взятия корня или суммы других чисел.


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

    Формат входных данных:
    В единственной строке даны два целых числа N и X

    Пример ввода:
    100 126

    Формат выходных данных:
    Выведите единственное натуральное число — ответ на задачу.

    Пример вывода:
    9

    Пояснение к примеру:

    Способ оценки работы
    Для генерации уникального условия и проверки результата используется следующий код на языке Python. Функция generate возвращает условие варианта и правильный ответ:
    def generate():
          return [('{} {}\n'.format(n, x), ans) for n, x, ans in [
    (100, 126, 9),
    (10, 10, 1),
    (1000, 1000, 1),
    (1, 1, 1),
    (1, 1000, 1000),
    (1000, 1, 10),
    (1000, 999, 17),
    (722, 966, 16),
    (774, 717, 21),
    (664, 177, 16),
    (655, 657, 7),
    (659, 65, 9),
    (901, 559, 21),
    (813, 314, 18),
    (528, 131, 16),
    (882, 258, 19),
    (516, 583, 12),
    (801, 767, 19),
    (147, 222, 11),
    (67, 743, 13),
    (413, 335, 21),
    (453, 467, 7),
    (600, 104, 9),
    (323, 209, 19),
    (462, 822, 18),
    (126, 743, 16),
    (77, 917, 17),
    (100, 999, 27),
    (1, 999, 999),
    (1000, 894, 29),
    (999, 712, 28),
    (123, 944, 24),
    (432, 277, 24),
    (945, 616, 28),
    (100, 999, 27),
    (1000, 894, 29),
    (999, 712, 28),
    (123, 944, 24),
    (432, 277, 24),
    (945, 616, 28)
    ]]
    
    def check(reply, clue):
          return int(reply.strip()) == int(clue)
    


    Решение
    Решение состоит из трёх этапов. На первом этапе нужно составить набор степеней и корней из N, которые может быть выгодно использовать. Если два корня с разной степенью равны, то нам выгодно использовать тот из них, степень которого меньше. Так как 210 > 1000, то для любого N будет не более 11 различных корней. На втором этапе методом динамического программирования получаем список чисел, которые можно получить перемножением корней с оптимальной суммарной степенью. На третьем этапе используя тот же метод получается список чисел, которые можно получить сложением чисел с предыдущего этапа с оптимальными суммами.

    Пример программы, реализующей данный алгоритм на языке Python:

    1. import sys
    2.
    3. INF = int(1e9)
    4.
    5. def getRoots(n, mx):
    6.       ans = [INF, n]
    7.       for x in range(n, 1, -1):
    8.            while x ** len(ans) <= n:
    9.                  ans.append(x)
    10.                ans.append(1)
    11.                 roots = dict()
    12.                for i in range(len(ans)):
    13.                     if ans[i] != ans[i - 1] and ans[i] <= mx:
    14.                          roots[ans[i]] = i
    15.    return roots
    16.
    17. def getProducts(roots, mx):
    18.       ans = dict()
    19.       ans[1] = 0
    20.       for i in range(2, mx + 1):
    21.            ans[i] = INF
    22.            for k, v in roots.items():
    23.                 if i % k == 0:
    24.                    d = i // k
    25.                    if d in ans and ans[d] + v < ans[i]:
    26.                        ans[i] = ans[d] + v
    27.            if ans[i] == INF:
    28.                ans.pop(i, None)
    29.      ans[1] = roots[1]
    30.      prods = [(k, v) for k, v in sorted(ans.items())]
    31.      return prods
    32.
    33. def getSums(prods, mx):
    34.       ans = [INF] * (mx + 1)
    35.       ans[0] = 0
    36.       for i in range(len(ans)):
    37.            for k, v in prods:
    38.                 if k > i:
    39.                     break
    40.                 if ans[i - k] + v < ans[i]:
    41.                     ans[i] = ans[i - k] + v
    42.       ans[0] = INF
    43.       return ans
    44.
    45. def solve(dataset):
    46.       n, x = list(map(int, dataset.strip().split()))
    47.       roots = getRoots(n, x);
    48.       prods = getProducts(roots, x)
    49.       ans = getSums(prods, x)
    50.       return str(ans[x])
    51.
    52. solve(sys.stdin.read())
    




    Второй отборочный этап

    Второй отборочный этап




    Второй отборочный этап проводится в командном формате в сети интернет, работы оцениваются автоматически средствами системы онлайн-тестирования. Продолжительность второго отборочного этапа составляет 2 недели. Задачи носят междисциплинарный характер
    и в более простой форме воссоздают инженерную задачу заключительного этапа. Решение задач предполагало написание программ, допускалось использовать язык программирования Python. Решение каждой задачи дает определенное количество баллов. В данном этапе можно получить суммарно от 0 до 45 баллов.

    Задачи по анализу данных

    Задача 2.1.1 (10 баллов)
    В летний лагерь приехало 1000 школьников. Когда школьник приезжал, его сразу переписывали (ставили порядковый номер начиная с нуля — каким школьник приехал в лагерь). Школьников сразу разбивали по отрядам с разным количеством человек в отряде:
    первые n1 школьников определили в первый отряд, следующие n2 школьников — во второй отряд, следующие n3 — в третий и так далее.
    Однажды все четные отряды увезли на экскурсию. И в лагерь приехала комиссия и переписала всех школьников, которые остались (каждый школьник назвал номер, каким его записали, когда он приехал в лагерь). По ошибке некоторых школьников переписали несколько раз. Как теперь разобраться, какой школьник в каком отряде?

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

    За успешное решение задачи участники получают 10 баллов.

    Пример ввода:
    790 443 801 518 63 75 491 91… 420 371 89 389 453 488 892 932

    Пример вывода:
    [(0, 92), (93, 343), (344, 521), (522, 772), (773, 999)]

    Ограничение по времени исполнения программы: 15 с

    Ограничение по использованию оперативной памяти: 256 Мб

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

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

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

    За успешное решение задачи участники получают 15 баллов.

    Пример ввода:
    {'find': ('d', 'f'), 'd': ['a', 'b', 'c', 'e', 'f', 'g'], 'b': ['a', 'c',
    'd', 'e', 'f', 'g'], 'q': ['n', 'o', 'p', 'r', 's', 't', 'u'], 'f': ['a', 'b',
    'c', 'd', 'e', 'g'], 'a': ['b', 'c', 'd', 'e', 'f', 'g'], 's': ['n', 'o', 'p',
    'q', 'r', 't', 'u', 'c'], 'e': ['a', 'b', 'c', 'd', 'f', 'g'], 'u': ['n', 'o',
    'p', 'q', 'r', 's', 't'], 'r': ['n', 'o', 'p', 'q', 's', 't', 'u'], 'p': ['n',
    'o', 'q', 'r', 's', 't', 'u'], 'c': ['a', 'b', 'd', 'e', 'f', 'g'], 'g': ['a',
    'b', 'c', 'd', 'e', 'f'], 'o': ['n', 'p', 'q', 'r', 's', 't', 'u'], 'n': ['o',
    'p', 'q', 'r', 's', 't', 'u'], 't': ['n', 'o', 'p', 'q', 'r', 's', 'u']}

    Ограничение по времени исполнения программы: 3000 с
    Ограничение по использованию оперативной памяти: 256 Мб

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

    Задача 2.1.3 (0-20 баллов)
    В задаче фигурирует придуманный нами граф социальной сети (для каждого пользователя указано, какие пользователя добавили его в друзья). Для каждого пользователя вычисляется его популярность, она основана на том, сколько людей дружит с теми пользователями, с которым он дружит.

    Популярность вычисляется как X — суммарное количество людей, которые дружат с его друзьями, считая его самого.
    Необходимо рассчитать два перцентиль 50 и 90, т.е. два наименьших значения популярности такие, что с вероятностью 50% для первого и 90% для второго популярность случайного пользователя будет меньше данного значения.

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

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

    Пример ввода:
    [{0: [5, 8], 1: [7, 2], 2: [8], 3: [10, 0], 4: [0, 10, 2, 1], 5: [1, 5,
    3, 7], 6: [7, 3, 0], 7: [12, 13, 0, 8], 8: [8, 11], 9: [6, 2, 13], 10: [13], 11:
    [2, 0, 8], 12: [0, 13], 13: [4, 11, 8], 14: [0, 4, 12, 2]}, {0: [14, 11], 1: [7,
    14, 1], 2: [0], 3: [10], 4: [13], 5: [8, 0], 6: [5, 3], 7: [2, 11, 8, 10], 8:
    [3, 10, 14, 7], 9: [0, 11, 7, 4], 10: [1, 7], 11: [10, 5, 12, 4], 12: [14, 5],
    13: [7, 6, 3, 1], 14: [10, 6, 0, 8]}]

    Пример вывода:
    [(4, 6), (7, 9)]

    Ограничение по использованию оперативной памяти: 256 Мб
    Время одной попытки: 5 мин

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

    Заключительный этап

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




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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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





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

    Участники должны были писать программы на языке 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 (дату рождения).

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

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

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

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

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

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

    Посчитанные результаты участников принимаются в файле формата 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.


    image
    Как бы мне выстроить непротиворечивую онтологию?


    Победители — команда «Математическое ожидание».
    • Жидков Всеволод, МБОУ «Воткинский лицей» (Воткинск), 8 класс
    • Татосьян Владимир, ГБОУ лицей №1568 им. Пабло Неруды (Москва), 9 класс
    • Шехирин Алексей, МБОУ гимназия №21 (Архангельск), 9 класс



    Интеллектуальные энергетические системы



    «А мы им еще потом неожиданно отключим центральную ЛЭП»
    — организаторы

    image

    Первый отборочный этап

    Первый отборочный этап


    Первый отборочный тур проводится индивидуально в сети интернет, работы оцениваются автоматически средствами системы онлайн-тестирования. Для каждого из параллелей (9 класс или 10-11 класс) предлагается свой набор задач по физике, задачи по математике общие для всех участников. На решение задач первого отборочного этапа участникам давалось 3 недели. Решение каждой задачи дает определенное количество баллов. Баллы зачисляются в полном объеме за правильное решение задачи. Участники получают оценку за решение задач в совокупности по всем предметам данного профиля (математика и физика) — суммарно от 0 до 20 баллов.

    Задача по физике 1.3.4 (5 баллов)
    Сопротивление реостата определяется углом поворота ручки в пределах от 0˚ до 180˚ градусов. При нуле (крайнее правое положение) реостат имеет сопротивление 100 Ом, при максимальном угле поворота (крайнее левое положение) — 500 Ом. Найдите положение ручки реостата, при котором показания амперметра в приведенной схеме будут нулевыми.



    Запишите сопротивление реостата в этом положении, с точностью до сотых.

    Второй отборочный этап

    Второй отборочный этап


    Второй отборочный этап проводится в командном формате в сети интернет, работы оцениваются автоматически средствами системы онлайн-тестирования. Продолжительность второго отборочного этапа — 2 недели. Задачи носят междисциплинарный характер и в более
    простой форме воссоздают инженерную задачу заключительного этапа. Решение каждой задачи дает определенное количество баллов. Баллы зачисляются в полном объеме за правильное решение задачи. В данном этапе можно получить суммарно от 0 до 8 баллов.

    Пример задач:
    Задача по энергетике 2.1.4 (3 балла)
    Вам нужно выбрать оптимальные параметры для некоторой (несуществующей) электростанции. Ее КПД можно весьма точно оценить по формуле:

    Параметрами x и y вы можете управлять. Значения x ограничены от 1 до 3, значения y — от 2 до 5.

    Найдите такие значения параметров x и y, при которых КПД электростанции будет оптимальным при следующих параметрах a и b. Дайте ответ с точностью до третьего знака после запятой.

    Пример входных данных:
    a = 4.03 b = 74.64

    Решение
    КПД условной электростанции желательно должен быть максимально большим, таким образом, при заданных значениях параметров a и b задача сводится к отысканию максимума функции КПД.
    Поскольку при решении задачи можно дать решение с точностью до третьего знака, задача может быть решена численно. Например, в MS Excel или с помощью написания простой программы эта задача может быть решена напрямую построением таблица значений функции КПД на сетке значений дискретных переменных с дальнейшим нахождением наибольшего из значений функции.
    Таким образом можно найти, что КПД максимально при значениях x = 2,082; y = 4,981.


    Заключительный этап

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



    Аппаратная часть задачи

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

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



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


    Командное задание финального этапа состоит из трех этапов:


    Цифро-натурный стенд игры «Энергосистема»

    Серая штука — большой вентилятор, «создает» ветер.

    Элементы стенда

















    Третий этап производится в установленном рядом со стендом диспетчерском центре, представляющим собой подключенный к стенду компьютер с установленной игровой программой, имеющей пользовательский интерфейс (рис. 3, 4). Управляющие воздействия на третьем этапе выполнения задания вводятся в игровую программу при помощи пользовательского интерфейса, при этом команда не имеет доступа к стенду и права производить манипуляции на стенде.


    Интерфейс игровой программы игры «Энергосистема». Страница диспетчерского управления энергосистемой

    Задание содержит открытую часть, известную командам, и закрытую часть, известную только членам жюри и техническим сотрудникам – инженерам стенда.
    Задание включает в себя следующие сведения, сообщаемые командам:
    • Число потребителей с указанием категории надежности их электроснабжения;
    • Число и тип заданных объектов электрических сетей на территории;
    • Географическое положение («геометрию») всех заданных объектов на территории;
    • Климатические условия на территории с точностью до климатической зоны, средних значений скорости ветра и солнечной интенсивности на территории;
    • Правила игры «Энергосистема».

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


    Каждая команда проектирует одну энергосистему, монтирует ее, затем играет в две игры с разными условиями («пресетами»). В каждой игре 10 тактов длительностью 1 минута каждый. «Пресеты» в виде фрагмента программного кода вносятся техническим специалистом перед началом работы команд. Расчет игровых баллов за каждую из игр выполняется программой автоматически. Все действия команд и результаты игр фиксируются автоматически в виде игровых логов.

    Правила игры «Энергосистема»
    Игровое задание
    В вашей энергосистеме вам будут заданы потребители электроэнергии, их тип, число, максимальная потребляемая мощность:


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

    К ГПС с материка подключена магистральная линия, питающая город. Максимальная мощность, приходящая по ЛЭП – 25 МВт.

    Объекты энергосистемы, которые можно ставить на стенд


    Кроме того, для работы дизельных генераторов может быть закуплено дизельное топливо: только один раз перед началом управления энергосистемой, не более 30 тонн с шагом в 1 тонну, цена – 2 балла за тонну.

    Изначально каждая команда получает 15 км ЛЭП (15 метров кабеля) бесплатно, плата за каждый километр сверх выданных 15 км – 2 балла.
    Каждая команда получает в начале игры 500 баллов.

    Дизельные генераторы и накопители можно устанавливать только на ГПС. Можно установить в сумме не более 3-х дизельных генераторов и накопителей.

    Диспетчерское управление энергосистемой
    Диспетчерское управление энергосистемой проводится в течение 10 тактов по 1 минуте на такт. Каждый такт моделирует 6 часов работы энергосистемы.

    На каждом такте вводятся настройки на следующий такт, затем за 5 секунд до конца такта они сохраняются, на следующем такте на все время такта выдается текущая ситуация (включение и отключение линий и т.д.), вводятся настройки на следующий такт.

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

    Действия при управлении
    • Включение и выключение линий электропередач на ГПС или ПС
    • Изменение мощности дизельных генераторов
    • Выдача предписания потребителю 2-й категории о снижении мощности потребления через такт (потребитель снизит мощность до 0,5 МВт на такте N+2)


    Что видит команда при управлении
    • Схему сети (топология – каждый объект, на какой он линии)
    • Текущее потребление по каждому потребителю и по системе в целом
    • Прогноз потребления на такт N+1 по каждому потребителю и по системе в целом
    • Точность прогноза – 95%
    • Какие линии включены/отключены
    • Текущее значение и прогноз мощности по энергомосту
    • Текущее значение и прогноз по скорости ветра и солнечной освещенности
    • Текущее значение генерации по каждой солнечной батарее и по каждому ветрогенератору
    • Текущий заряд каждого накопителя
    • Текущая мощность каждого дизеля
    • Суммарный остаток топлива
    • Предписание заводам
    • Таймер – сколько осталось до конца такт


    Расчет баллов
    За каждый такт, на котором все потребители были снабжены электроэнергией (подключены) без снижения мощности начисляется по 5 баллов.

    Штрафы
    Штрафы начисляются (вычитаются из суммы оставшихся и полученных фишек) за отключение потребителей по следующим правилам:





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


    Ажиотаж на финале.


    Победители — команда «1314».
    • Жиганов Даниил, ГБОУ школа №2090 (Москва), 11 класс
    • Михалин Дмитрий, ГБОУ школа №2090 (Москва), 10 класс
    • Николич Николай, ГБОУ школа №2090 (Москва), 11 класс
    • Рязанов Федор, ГБОУ школа №2090 (Москва), 11 класс


    Итог


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

    Старшеклассники получили дипломы


    И космический сухпаек от ОРКК
    image

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


    Организаторы получили +1500 золота и +1000 опыта


    И еще кое-что


    А я нашел «настоящего» комсомольца и попросил «по-настоящему» завязать пионерский галстук.


    Ну, а в конце «смены» мы все ж сумели разжечь «двухъядерный» костер, послушать легенды «Орленка», спеть «Катюшу».
    image

    Планы на будущее
    «Следующий год мы уже начинаем готовить в июне, т.к. уже сейчас понятно, что заочный этап будет гораздо более продолжительным по времени. За счет этого удастся сильно прокачать образовательную составляющую и выйти на более интересные задачи в финале.
    Думаю, что нужно развиваться в сторону MOOC-курса, поддержанного серией очных мероприятий. Будем проводить хакатоны в разных городах вместе с организациями-партнерами.»

    Юрий Молодых, организатор направления «Большие данные и машинное обучение»

    Вот видео от Sci-one и статья на GT — Я у мамы инженер: финал олимпиады НТИ




    СМИ
    Научная Россия. Олимпиада НТИ: запуск прошел успешно
    АСИ. Победители Всероссийской олимпиады НТИ получат +10 баллов к результатам ЕГЭ
    GT. Я у мамы инженер: финал олимпиады НТИ

    Благодарности
    Лично хочу сказать спасибо Алене Ильиной (за всё), Ксении Макаровой и Юлии Грабовской (за то, что терпели меня), Ирине Абзаловой (за прекрасные фото), сисадмину (за интернет и анимэ), всем космическим инженерам (за баскетбол и Героев 3), а так же компании РВК (говорят, если бы не они, то ничего бы не было).
    Поделиться публикацией
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 20
      +1
      «готовясь к сдачи ЕГЭ»
      Очевидно, не по русскому языку.
      Мне всегда казалось, что логическое мышление у технарей подразумевает способность разобраться в простейших правилах русского языка. Поэтому всегда удивляюсь таким «товаристчам».
        0
        А куда поступили?
          0
          ДВГУ (сейчас ДВФУ)
            0
            Там хороший уровень, или это просто удобнее?

            Просто такие задачи для восьмиклассников это настоящий хардкор, имхо. Решающий такие вещи школьник может претендовать на лучшие ВУЗы страны, нет?
              0

              Лаборатории энергетиков не восстановили/не создали, после переезда электротехнического факультета ДВГТУ (влился в ДВФУ). Но в преподавательском составе сильные и толковые преподы остались. Правда без мат базы тяжко учиться будет новым студентам :(


              У нас выпуск был 10 лет назад, две группы, около 45 человек, почти все устроены в отрасли. Не устроились только те, кто сам не пошёл.

                +1
                Основная хардкорность задач в том что очень мало времени.
                Сам участвовал в Автономных транспортных системах
                Нам за 3.5 дня нужно было сделать
                — Квадрокоптер со стабилизацией по сонарам
                — Корабль с навигацией тоже по сонарам
                — Машину с датчиками линий
                — Спутник в формате CubeSAT

                Конструкторы были на этапе готовых деталей, но нужно было сделать все соединения и собрать всё вместе
                С командой из 3-х человек успели далеко не всё, только 48 баллов из 100
                У победившей команды 4 человека, 71 балл
                Поэтому количество человек в команде во многом решает
                  0
                  На тот момент было удобнее. Если бы пришлось выбирать снова — однозначно подавался бы на физтех.
                  +1
                  Отставить! Я решил, что автор — участник олимпиады. Невнимательность… Вопрос был, конечно, не вам, но диалог забавный вышел.
                +1
                Для задачи по математике 3.1.1в (про рейтинги стран), приведите плз в статье определение рейтинга, а то мне например захотелось попробовать решить эту задачу, но пришлось лезть за полным условием задачи в методичку олимпиады…

                > каждый человек получает оценку – число Q – показатель его умственных способностей (чем больше Q, тем больше способности). За рейтинг страны принимается среднее арифметическое значений Q всех жителей этой страны.
                0
                +10 баллов к ЕГЭ?
                Так может и конкурс возникнуть на участие в олимпиаде, скажем 10 человек на место.

                А вообще молодцы.

                P.S.
                Как думаете, большое количество таких олимпиад «на +10 баллов к ЕГЭ» поможет вырулить системе образования из «подготовки школьников к сдаче тестов» к «подготовке школьников умению думать»?
                  0
                  Если я правильно понимаю, то речь о бонусных не более 10 баллов, которые распределяются по желанию вуза. Могут дать баллы хоть за что (окончил музыкальную школу — получи +5), но сумма обрубается десяткой. И по ссылке сказано об этих +10 в довольно ограниченном списке вузов.

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

                  Единственное чего нет — это уровневых проектных конкурсов. Но тут проблема в объективности, которая обязательна при наличии серьезных бонусов к поступлению, и которую сложно обеспечить при таком формате.
                    0
                    Юрий:
                    «Суть заочного этапа двойная: с одной стороны, через более простые задачи и онлайн-курсы дети готовятся к финальной задаче, но с другой стороны, на финал едут те дети, которые лучше остальных прошли заочный этап.

                    В этом году на заочном этапе было больше 4000 участников, в следующем ждем еще больше.»
                    0
                    Возможно я основательно забыл своё детство, но меня задания не впечатлили. Сложилось впечатление что во времена моей молодости олимпиады были куда серьёзнее, даже в нашем провинциальном городке. Про задачи из журнала «Квант» я уже вообще молчу.
                      0
                      А можно какие-нибудь примеры из ваших детств? Не троллю, реально интересно. Мне молодому кажется, что в ваших олимпиадах (80-ые, судя по профилю) было много ассемблера и радиотехники. Но и думать, что не было куда более серьезной математики тоже не могу. Расскажете?
                        0
                        Вы не троллите, уважаемый, скорее льстите. Мне в этом году стукнул уже полтинник. Я участвовал в олимпиадах по физике и математике. Первые программируемые калькуляторы только-только появились когда я заканчивал школу и стоили больше половины зарплаты моей матери. На младших курсах института мне пришлось даже попрограммировать в машинных кодах, на первом отечественном бытовом компьютере БК 001. Численные методы в школе были практически недоступны, хотя на программируемых калькуляторах что-то делать уже пытались, например считать орбиту и начальные параметры для вывода ракеты на луну.
                        За давностью лет восстановить условия своих заданий на олимпиадах я уже не смогу, но получить примерное представление о них, если реально интересно, можно посмотрев подшивку журнала Квант. Для этого сегодня не надо даже в библиотеку идти.
                        0
                        В мои годы олимпиады были конечно гораздо более академичными, куда ближе к серьёзному вступительному экзамену, чем к молодёжной тусовке. Такого фана в них не было.
                      +1
                      Наша команда в «Больших данных» состояла из людей, которым до поступления еще 2-3 года, т.е. эти 10 баллов нам сейчас ни к чему. Однако радует то, что если олимпиада попадет в перечень олимпиад школьников, за которую будут давать доп. баллы, то у нас, как победителей этого года, есть хорошие шансы, ведь мы проходим в финал следующего без предварительных туров, но и конкуренция будет выше.
                        +2
                        Да на здоровье, дорогой товарищ :)

                        Будет нужно еще аниме — обращайся.

                        Искренне твой,
                        сисадмин олимпиады

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

                        Самое читаемое