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



— Вовочка, кидай свої експерименти з холодним ядерним синтезом, йди до ЄДІ готуйся.
— Ща, мам.
Олімпіади — це круто. Вони дозволили такого раздолбаю волелюбному і розумному, як я, вступити до університету без іспитів.

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

— Що ви сьогодні на годину спізнилися?
— Та так, в універ надходили.

Я дуже радий, що знайшлися ініціативні хлопці, яким не все одно, що талановитий школяр-інженер витрачає свої останні безтурботні роки, судорожно готуючись до здачі ЄДІ, замість того, щоб будувати реактивні ранці або програмувати зародок штучного інтелекту.

Щоб створити лазівку для молодих талановитих інженерів, вони придумали таку штуковину — давайте замутим інженерну олімпіаду, яка дає можливість вступити до вузу.

Нещодавно в ВДЦ «Орлятко» пройшов «тест-драйв» Всеросійської інженерної олімпіади. Брали участь 5000 дітей з усієї Росії, до фіналу дійшли близько 100 осіб. Призів багато, але найкорисніше — за +10 очок до ЄДІ.

Я за всім доглядав і готовий поділитися своїми враженнями.

Олімпіада йшла за чотирма профілями.
Про перші два профілю розповім тут (трохи завдань і фоток), про другі два — трохи пізніше на GT.


Організація

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

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

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

З цієї причини організатори вирішили, що підуть по шляху рознесення різних завдань на різні етапи: мінімум, визначений Радою в першому заочному етапі і в індивідуальному очному. Життєві завдання, код з гитхаба і командність — у другому заочному і в командному очному.
У підсумку бали — підсумовуються, і всі вимоги дотримані.

Загалом, після закінчення олімпіади організатори два тижні готували «цегла» на 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 громадян не змінилося, ніхто не помер і не народився.)

Завдання з математики 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 країни, зазначеної в профілі
  • ID_Location – ідентифікатор регіону/міста, вказаний в профілі.
  • loginRegion – id регіону, звідки найчастіше авторизуйтесь в даній соціальне мережі користувач (може бути відсутнім!)


Приклад даних:
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. Я у мами інженер: фінал олімпіади НТІ

Подяки
Особисто хочу сказати спасибі Олені Ільїної, Ксенії Макарової, Юлії Грабовської, а так само компанії РВК (кажуть, якщо б не вони, то нічого б не було).
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.