Запрошую на чемпіонат з програмування

Привіт!

Ми з 2012 року проводимо всеросійські чемпіонати з програмування разом з Codeforces. Брати участь можна з 18 років. Громадянство в цілому не важливо, у нас завжди були гості з Казахстану, України, РБ та інших країн, але мова турніру – українська. Наприклад, у 2013 році було 3500 чоловік, і перше місце взяв «термінатор» tourist, а п'яте – ось цей хлопець rng_58 з Японії:

image

Правила – «олімпіадні завдання, які потрібно вирішити, плюс «зломи» чужих рішень за рахунок підбору своїх нестандартних наборів даних. Індивідуальний залік, в призах 100 тисяч рублів за перше місце, 70 тисяч і 50 тисяч — за друге і третє. Як зазвичай, буде окремий ігровий раунд у фіналі – потрібно буде написати AI для битви з AI інших учасників (у минулому році був хокей, до цього – битва магів). Приз ігрового раунду – ноутбук.


Термін
Кваліфікація 16 березня, відбірковий раунд 18 березня, фінал на 50 учасників – 15 квітня в нашому офісі в Москві. У минулому році градація кількості учасників у міру відбору до фіналу була така: 3500, 2000, 400 і 50 на фінал. Середній вік фіналіста – 24 роки.

Для фіналістів з РФ передбачені компенсація квитків в Москву (до 10 тисяч рублів).

Складність
Складність буде зростати в міру наближення до фіналу, але правила раундів залишаються однаковими.

Хід турніру
Відбіркові проходять на платформі Codeforces віддалено, як зазвичай всі турніри там. Фінал передбачає фізичне участь: всі гравці зберуться в одному залі. Там є Wi-Fi, розетки і локальні машини з набором середовищ розробки, які покривають всі мови, передбачені правилами. Практика показує, що ми розгортаємо всього пару таких машин – зазвичай учасники прибувають зі своїми ноутбуками.

image

Звідти ви заходите на сайт під своїм акаунтом (як зазвичай), отримуєте завдання, вирішуйте їх. Закривши завдання (після цього працювати з нею вже не можна), можна дивитися чужі исходники вже відправлених рішень і «ламати» їх, фактично, виявленням помилок на автотесте, тобто підстановкою складних наборів вхідних даних. За вдалий злом – бонус, за невдалий – штраф.

Приклад завдання з 2013 року:



Задано n ділянок пам'яті, для кожної ділянки відома його довжина в байтах a[i]. Вам треба розмістити в пам'яті як можна більше структур даних з можливих m, для кожної структури відомий її розмір b[j] в байтах. Тобто в оптимістичному випадку вийде розмістити все m структур, а в песимістичному — не одного. Відомо, що всі b[j] — це ступені двійки. Кожна структура повинна знаходитися в одній ділянці пам'яті, але ділянка може вміщувати кілька структур. Звичайно, кожен байт може належати не більш ніж одній структурі.

Ваша програма повинна швидко працювати (вкластися в пару секунд, для будь-яких n і m не перевищують 10^6. Все a[i] і b[j] — цілі числа від 1 до 10^9. Серед значень a[i] і b[j] можуть бути однакові значення (хоч все).

Ось тут є більше завдань.

Варіанти рішення:

Спочатку розглянемо окремий випадок, коли серед значень b[j] немає одиниць. Значить всі значення b[j] — парні (раз вже це ступені двійки). У такому разі непарні ділянки пам'яті не зможуть бути витрачені повністю (сума парних — парна). Тому ми нічого не втратимо, якщо з кожного непарного a[i] віднімемо одиницю. Таким чином, отримуємо ситуацію, в якій усі b[j] і a[i] четны. Але значить всі ці значення можна поділити на 2 та це не змінить відповідь! При такому розподілі можуть з'явитися одиничні структури, і цей випадок ми зараз розглянемо (а якщо вони не з'явилися, то можна ділити все на два знову).

Якщо ж деякі b[j] дорівнюють 1, то немає причин не спробувати їх кудись розмістити. Звичайно, в першу чергу їх треба визначити у всі ділянки пам'яті непарної довжини (адже їх ніяк не можна використовувати повністю без одиничних структур). Якщо і після цього залишилися одиничні структури, то помітимо, що якщо ми одну одиничну структуру визначимо парний ділянку, то він стане непарних. Тому туди обов'язково буде вигідно визначати і ще одну одиничну структуру. Таким чином, можна з пар одиничних структур назбирати структури розміру 2 і продовжувати працювати з ними, розглядаючи їх як єдине ціле. Якщо залишилася одна без пари, то треба її визначити мінімальний позитивний a[i].

Так ми домоглися, що тепер у нас немає структур розміру 1, а значить прийшли до першого випадку. Єдине, що треба пам'ятати з скількох початкових структур полягає поточна і розміщувати одиничні структури жадібно за цим параметром.

Питання-відповідь

— Скільки людей зареєструвалося на момент публікації топіка?
Можна подивитися ось тут: codeforces.com/croc2016/registrants

— Де точні правила і реєстрація?
Ось — codeforces.com/blog/entry/43229

— Завдання пройшла 19 наборів даних з 20: я отримаю за неї хоч одне очко?
Ні, не отримаєте. Треба пройти всі.

— Я не громадянин Росії. Можна брати участь?
Так. Але варто враховувати, що дорогу до Москви ми оплачуємо тільки фіналістам — громадянам РФ.

— Мені 45 років, я бородатий, студент і живу в Африці. Мені можна?
Брати участь і проходити у фінал — так.

— Є звіти?
Фото і звіт учасника.
І відео:


— Є можливість взяти участь хоча б в кваліфікаційних та відбіркових раундах, якщо мені немає 18?
Так, ви зможете битися за рейтинг CF, але у фінал ви не пройдете. Принаймні, якщо вам не виповниться 18 повних років до 15 квітня 2016.

— Що писати у формі реєстрації, якщо я не можу заповнити поле «ВУЗ»?
Пишіть «null» або просто заповнюйте по ситуації. Це не накладає обмежень.

— Круто, але я не можу. Коли наступний чемпіонат?
Спробуйте взяти участь поза конкурсом. Якщо не вийде — Чемпіонат проходить далеко не останній раз, плюс є ще маса конкурсів і контестів. Наприклад, пару років тому у нас був конкурс літаючих роботів з призом в 1 мільйон рублів. Також можна стежити за нашим корпоративним блогом тут на Хабре — великі заходи будуть анонсуватися.

Джерело: Хабрахабр

0 коментарів

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