Яндекс.Алгоритм. Розбір торішнього кваліфікаційного раунду і останній шанс взяти участь в чемпіонаті

Як вам відомо, вчора завершився черговий чемпіонат ACM ICPC. Вітаємо студентів МФТІ, ІТМО, УрФУ і ННДУ з відмінним виступом, хлопців з Спбду — з 1-м місцем. Тепер ми запрошуємо всіх бажаючих взяти участь в Яндекс.Алгоритмі 2016. У цьому році фінал чемпіонату пройде в Мінську.

image

В цьому році вперше окрім традиційних призів переможці отримають можливість потрапити на стажування в Яндекс. 22 травня реєстрація закриється і залишиться тільки стежити за іншими учасниками у відбіркових раундах. Кваліфікаційний раунд триватиме в цьому році дві доби — з 21 по 22 травня. Раунди знову будуть оцінюватися по системі TCM/Time. Для тих, кому цікаво, якої складності завдання їх чекають, ми розібрали тур минулорічної кваліфікації. Також у вас є можливість потренуватися на ньому.

A. Помилки
Михайло — звичайний користувач інтернету. Коли Михайло шукає що-небудь в інтернеті за допомогою Яндекса, трапляється, що він допускає помилки в пошуковому запиті. Звичайно ж, у більшості випадків Яндекс може вгадати, що мав на увазі Михайло і виправити запит. Наприклад, якщо Михайло опечатается і напише «дезоксирибонукленовая» (що не дивно), Яндекс виправить запит на «дезоксирибонуклеїнова».

Можливо, ви подумали, що в цій задачі вам потрібно написати програму, исправляющую помилки у запиті користувача. Це не так: крім цієї задачі вам запропоновано ще 5 захоплюючих завдань, а часу до кінця змагання залишилося не так вже багато. Просто перевірте, чи містить черговий запит Михайла помилки.

Вхідні дані
У першому рядку вхідного файлу знаходиться запит Михайла: від 1 до 5 слів, що складаються з малих латинських літер та відокремлених одним пропуском. Другий рядок містить ціле число N (1 ≤ N ≤ 100): кількість слів, що містяться в словнику Яндекса (не хвилюйтеся, в реальності кількість слів, що містяться в словниках Яндекса, набагато більше ста). Третій рядок містить слова зі словника. Кожне слово являє собою рядок, що складається з малих латинських літер. Слова розділені одиночними пробілами. Гарантується, що і слова із запиту, і слова зі словника містять не більше 20 букв.

Вихідні дані
У єдиному рядку вихідного файлу виведіть «Correct» (без лапок), якщо всі слова із запиту Михайла містяться в наявному словнику, і «Misspell» (без лапок), якщо хоча б одного слова в словнику немає.

Рішення задачі
В задачі потрібно визначити, чи входять всі слова з першого безлічі по друге безліч.
З обмеженнями у цій задачі вистачило простого рішення тривіального за O(N·M), N M — розміри першої та другої множини, відповідно. Для його реалізації потрібно безпосередньо перевірити, що кожне слово з першого множини знаходиться у другому.

Досить проста реалізація виходить на мові python:

import sys
words = sys.stdin.readline().split()
_ = sys.stdin.readline()
d = sys.stdin.readline().split()
print "Correct" if all(word in d for word in words) else "Misspell"</i>


B. Оптимальний плейлист
Ганна — звичайний користувач інтернету. Ганна дуже любить слухати музику і користуватися сервісом Яндекс.Музика. Одного разу, слухаючи пісні на Яндекс.Музиці в режимі випадкового перемішування, Ганна була дуже засмучена тим, що після її улюбленої групи «Епідемія» раптово заграв Григорій Лепс. Палаюча від обурення Ганна написала гнівний лист в технічну підтримку сервісу, після чого команда розробників Яндекс.Музики вирішила поліпшити вибір наступної пісні для програвання.

Всього знаходиться на сервісі N пісень, кожну з яких Анна хоче послухати хоча б один раз. При цьому Ганна не заперечує проти повторного прослуховування пісень, проте дуже заперечує проти різкої зміни жанрів. В базі даних Яндекс.Музики крім самої музики міститься інформація про те, наскільки деякі пісні схожі за жанром один на одного. Кожен запис має вигляд (a, b, U) і означає, що якщо включити пісню з номером b відразу після пісні з номером a, користувач відчує U одиниць невдоволення.

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

Маючи такі дані, Яндекс.Музика повинна скласти оптимальний для користувача плейлист, що задовольняє наступним умовам:

  • Кожна пісня міститься в ньому хоча б один раз;
  • Для кожної пари сусідніх пісень є відповідний запис в базі даних (краще не перемикати пісні, не знаючи, чим це може обернутися);
  • Невдоволення від прослуховування плейлиста повинно бути як можна менше.
Ви зможете скласти плейлист, що задовольняє зазначеним умовам?

Вхідні дані
У першому рядку вхідного файлу містить два цілих числа N M (1 ≤ N ≤ 105, 1 ≤ M ≤ 2 × 105), розділені пробілами: кількість пісень, які хоче прослухати Ганна і кількість записів про переходах між цими піснями, відповідно. Наступні M рядків містять по три цілих числа ai, bi, Ui (1 ≤ ai, bi ≤ N, ai ≠ bi, 1 ≤ Ui ≤ 109), розділених пропусками, які говорять про те, що якщо включити пісню з номером bi відразу після пісні з номером ai, користувач відчує Ui одиниць невдоволення. Гарантується, що ніякої перехід від однієї пісні до іншої не зустрічається в записах двічі.

Вихідні дані
Виведіть єдине число: максимальне невдоволення, яке зазнає Ганна в процесі прослуховування оптимально складеного списку, або -1, якщо плейлист скласти неможливо.

Рішення задачі
Навчимося вирішувати завдання без додаткового параметра Ui.
Дан орієнтований граф з N вершинами і M дугами, потрібно визначити, чи можна побудувати таку послідовність вершин графа, що будь-які дві сусідні вершини з'єднані дугою, і всі N різних вершин графа входять в цю послідовність.
Зауважимо, що сильно зв'язну компоненту цього графа можна замінити на одну вершину. Це можна зробити, т. к. для будь-якого сильно зв'язного графа можна побудувати послідовність вершин, в якій всі вершини графа будуть зустрічатися не менше одного разу. Доведемо це твердження. Припустимо, у нас є якась послідовність K різними вершинами, що закінчується вершиною x. Виберемо будь-яку з ще не представлених у ній вершин y, т. к. граф сильно зв'язний, то існує ланцюжок дуг ведуча x y, додамо вершини, через які проходить цей ланцюжок послідовність. У новій отриманої послідовності не менше K + 1 різної вершини.
Після того, як ми стиснули сильно зв'язні компоненти графа в нові вершини, залишиться орієнтований граф без циклів. Нескладно бачити, що для того, щоб можна було побудувати вихідну послідовність вершин, у цього графа повинен бути єдиний спосіб впорядкувати вершини топологічно, причому між будь-якими двома сусідніми вершинами в топологічному подрядке повинна бути дуга.
Додатково зауважимо, що якщо для якогось графа можна побудувати необхідну послідовність вершин, то і після додавання додаткових дуг в нього, це властивість збережеться.
Відповідь на задачу будемо шукати двійковим пошуком по максимальному невдоволення, яке зазнає Ганна в процесі прослуховування оптимально складеного списку відтворення.

Отже, отримуємо наступний алгоритм вирішення задачі:
Двійковим пошуком виберемо значення U, для якого залишимо тільки дуги Ui ≤ U в графі.
Стягуємо сильно зв'язні компоненти отриманого графа в окремі вершини.
В отриманому графі знайдемо топологічний порядок вершин, перевіримо, що між усіма парами сусідніх вершин є дуга.
В залежності від того, вдалося чи ні знайти необхідну послідовність для заданого значення U, визначаємо в яку сторону рухатися двійкового пошуку.

Корисні посилання:
en.wikipedia.org/wiki/Strongly_connected_component
en.wikipedia.org/wiki/Topological_sorting

C. Ранжування документів
Іван — звичайний користувач інтернету. Одна з улюблених ігор Івана — «Капелюх», в якій потрібно швидко пояснювати загадане слово. Для того, щоб грати було цікаво, він шукає незвичайні слова в інтернеті, задаючи різні пошукові запити.

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

В цій задачі ми будемо використовувати спрощену версію формули релевантності — лінійну комбінацію параметрів документа. Формула ранжирування задається N параметрами (a1, a2, ..., aN), а кожен документ описується N числовими параметрами (f1, f2, ..., fN).

Релевантність ж визначається за формулою:
image

Інтернет дуже швидко змінюється, і деякі документи можуть мінятися кілька разів в хвилину. Звичайно, після цього необхідно змінити деякі параметри цього документа.
Ви Можете в умовах змінних параметрів документів знаходити найбільш релевантні?

Вхідні дані
У першому рядку вхідних даних записано одне ціле число N (1 ≤ N ≤ 100) — кількість параметрів у формулі ранжирування. Другий рядок містить N цілих чисел ai (0 ≤ ai ≤ 108).

У третьому рядку вхідних даних записано одне ціле числа D (10 ≤ D ≤ 100 000, N·D ≤ 100 000) — кількість документів для ранжирування. Далі в D рядках записано по N цілих чисел fi,j (0 ≤ fi, j ≤ 108) — числові параметри i-го документа.

Наступний рядок містить одне ціле число Q (1 ≤ Q ≤ 100 000) — кількість запитів до системи ранжирування. Наступні Q рядків описують запити. Запит на видачу найбільш релевантних документів задається парою 1 K (1 ≤ K ≤ 10). Запит на зміну параметра документа задається четвіркою 2 d j v (1 ≤ d ≤ D, 1 ≤ j ≤ N, 0 ≤ v ≤ 108) і означає, що j-ий параметр у d-го документа стає рівним v.

Вихідні дані
Після кожного запиту першого типу виведіть в один рядок порядкові номери K найбільш релевантних документів у порядку убування релевантності (числа слід розділяти одиночними пробілами). Гарантується, що всі документи в будь-який момент часу мають різні значення релевантності.

Рішення задачі
Почнемо з аналізу запитів другого типу. Зауважимо, що при виконанні таких запитів релевантність змінюється тільки в одного документа, і більш того, нову релевантність можна обчислити за O(1).
Для виконання запитів першого типу потрібно знаходити K максимальних елементів в списку релевантності. Для цього можна використовувати збалансоване дерево пошуку.
При реалізації на мові C++ можна використовувати стандартний контейнер std::map, а при використанні Java —
TreeMap. При використанні цих контейнерів можна видаляти старі значення релевантності документів по ключу, і після цього додавати документ вже з новим значенням, а максимальні шукати частковим проходом ітератора від максимального ключа.
Операції другого типу будуть оброблятися за image(видалення і додавання по ключу), а операції знаходження K максимальних за image(як мінімум для C++).

D. Обмежувач частоти
Роман — звичайний користувач інтернету. Як і багато інші звичайні користувачі, Роман дуже нетерплячий. Наприклад, зараз Роман чекає оновлення новин на головній сторінці Яндекса і постійно тисне «Оновити» в браузері. Для того, щоб не перевантажити Яндекс величезною кількістю запитів (Роман дуже нетерплячий!), всі запити Романа складаються в чергу, звідки відправляються на сервіс новин таким чином, щоб запити йшли не частіше, ніж деяка задана в конфігурації частота.

Обмеження на частоту може бути задано двома способами: X запитів в секунду або 1 запит не частіше, ніж в Y секунд. Кожен запит Романа буде оброблений в той момент часу, в який його обробка не призведе до порушення обмеження на частоту, але, природно, не раніше того моменту, як запит був відправлений. Для більш докладного пояснення дивіться приклади.

Чи зможете ви написати програму, яка моделює роботу сервісу з обмеження частоти запитів і повідомляє, у який момент оброблений кожний запит?

Вхідні дані
У першому рядку записано обмеження частоти в форматі X / Y, X Y — два цілих числа (1 ≤ X, Y ≤ 104), хоча б один з яких дорівнює 1. Якщо Y = 1, то сервіс не повинен обробляти більше X запитів в секунду. Якщо X = 1, то сервіс не повинен обробляти більше, ніж один запит Y секунд.

У другому рядку міститься число N (1 ≤ N ≤ 105) — кількість запитів оновлення сторінки, які Роман відіслав на сервер, натискаючи кнопку «Оновити» в браузері.

Наступний рядок містить N цілих чисел ti (1 ≤ ti ≤ 1018), розділених пробілами — часи надсилання запитів, задані в наносекундах (в одній секунді 109 наносекунд). Гарантується, що числа ti розташовані по неубыванию.

Вихідні дані
Виведіть N чисел, розділених пробілами — час обробки кожного запиту. Дивіться приклади для пояснення.

Рішення задачі
Для вирішення завдання досить зчитувати по черзі часи всіх запитів та записувати в масив часи, коли вони були оброблені. Для того, щоб отримати час обробки i-го запиту, достатньо взяти мінімум з часу його надходження і часу обробки (i — X)-го запиту, збільшеного на Y·109 (у випадку, якщо i ≤ X, запит буде оброблений відразу ж при надходженні).

E. Розмір карт
Олексій — звичайний користувач інтернету. Одного разу, користуючись сервісом Яндекс.Карти, Олексій задумався: адже напевно підсумкове зображення на екрані формується з декількох прямокутних зображень меншого розміру, одержуваних з сервера. Олексію стало цікаво: скільки існує можливих розмірів зображень таких, що з них можна скласти картинку, видиму на екрані.

Видима область карти займає N × M пікселів на екрані Олексія. Його цікавить кількість пар (A, B) (1 ≤ A ≤ N, 1 ≤ B ≤ M) таких, що прямокутниками A × B можна викласти прямокутник N × M, розміщуючи їх впритул один з одним, без накладываний і поворотів. При цьому Олексій упевнений, що посилати великі картинки з сервера дуже накладно, і тому його не цікавлять пари (A, B), для яких A·B > R. Також Олексій розуміє, що посилати велику кількість маленьких картинок теж невигідно, тому його не цікавлять пари (A, B), для яких A·B < L.

Допоможіть Олексію відповісти на питання, що його цікавить.

Вхідні дані
Єдиний рядок вхідного файлу містить чотири цілих числа N, M, L, R (1 ≤ N, M ≤ 109, 1 ≤ L ≤ R ≤ N·M), розділених пробілами.

Вихідні дані
Виведіть єдине число: кількість можливих пар, які відповідають вимогам Олексія.

Рішення задачі
З умови, що прямокутниками A × B можна викласти прямокутник N × M випливає, що N ділиться на A, M ділиться на B. Сформуємо список Dn, що складається з дільників N список Dm з дільників M. Як відомо, знайти всі дільники якого-небудь числа X за image. Маючи два таких списку, можна двома вкладеними циклами перебрати всіх пари-кандидати (A, B) і перевірити виконання умови L ≤ A·B ≤ R. Якщо умова виконується, відповідь потрібно збільшити на 1.
image
Бонус: найбільша кількість дільників у кількості до 109 — 1344.

F. Завантаженість доріг
Юра — звичайний користувач інтернету. Він дуже любить читати історію міст світу, а ще більше він любить подорожувати і під час цих подорожей розповідати друзям про те, що відбувалося в тому чи іншому місці в X або XVI столітті. Коли Юра приїжджає в нове місто, у нього вже готовий список пам'яток цієї місцевості, і залишається тільки правильно прокласти маршрут до цих місць.

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

В цій задачі ми використовуємо спрощену версію визначення завантаженості доріг. Всі дороги в сервісі карт пронумеровані цілими числами від 1 M. Про кожну дорогу відомі два числа Li Ri. Якщо в поточний момент часу на дорозі знаходиться менше Li автомобілів, то дорога вважається вільною, і на карті вона малюється зеленим кольором. Якщо ж у поточний момент часу на дорозі знаходиться більше Ri автомобілів, то дорога вважається завантаженої, і на карті вона малюється червоним кольором. Якщо дорога не є ні вільною, ні завантаженої, то вона малюється на сервісі помаранчевим кольором.

Вам дано опис доріг з сервісу карт і інформація про те, де розташовані N автомобілів. Чи Можете ви визначити, яким кольором мають бути намальовані ці дороги на карті?

Вхідні дані
У першому рядку вхідних даних записано ціле число M (1 ≤ M ≤ 1000) — кількість доріг. Далі слідують M рядків по два цілих числа Li Ri (1 ≤ Li ≤ Ri ≤ 10) у кожній — параметри i-ї дороги. У наступному рядку записано одне ціле число N (1 ≤ N ≤ 1000) — кількість автомобілів, що перебувають на дорогах в даний момент. Наступний рядок містить N цілих чисел rj (1 ≤ rj ≤ M) — номери доріг, де розташовані автомобілі.

Вихідні дані
Виведіть M рядків, по одному для кожної дороги з вхідних даних. Якщо i-а дорога має бути намальований червоним, то в i-ой рядку виведіть «Red», якщо помаранчевим — «Orange», інакше виведіть «Green».

Рішення задачі
Для початку в задачі потрібно для кожної дороги підрахувати кількість автомобілів, що знаходяться на ній. А потім для кожної дороги за її параметрами легко визначити ступінь її завантаження.
Також досить проста реалізація виходить на мові python:
import sys
M = int(sys.stdin.readline())
LR = []
C = [0] * M
for i in xrange(M):
LR.append(map(int, sys.stdin.readline().split()))
N = int(sys.stdin.readline())
for r in map(int, sys.stdin.readline().split()):
C[r - 1] += 1
for i in xrange(M):
print "Green" if C[i] < LR[i][0] else 
("Red" if C[i] > LR[i][1] else "Orange")

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

0 коментарів

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