Следующий матч SRM состоится в субботу 01.12.2012 в довольно необычное время: 4:00 AM EET. Но что-то мне слабо верится, что так и будет.
Тем не менее, удачи всем!
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
5 дней
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
5 дней
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 26.11.2024 03:46:40 (h2).
Десктопная версия, переключиться на мобильную.
При поддержке
Слабо верится во что? Топкодер относительно часто в это время бывает.
Отличный способ не проспать открытие NEERC, чо
Всем привет! Как решать 500 и 1000?
И есть ли эффективный алгоритм подсчета числа перестановок 1, ..., n, удовлетворяющих данным линейным неравенствам, в духе bij ≤ xi - xj? (1000 можно переформулировать, как число перестановок с a – b = > |a - b| < k, a – b означает наличие ребра)
500 можно решать так:
Возьмем одну точку (например, белую) и объявим ее левой нижней точкой многоугольника. Назовем эту точку O. Отсортируем все точки, которые правее ее (если абсцисса такая же, то берем те что выше) по полярному углу. Теперь фиксируем одну точку противоположного цвета (назовем ее A).
Начинаем идти еще одним вложенным циклом от зафиксированной точки. Будем поддерживать вспомогательный вектор R, который если приложить к A, будет указывать на самую "правую" в смысле векторного произведения белую точку из тех, что мы уже обработали. Если текущая точка (назовем ее B) — белая, то обновляем R, иначе проверяем, лежит ли точка A + R снаружи текущего треугольника OAB. Если лежит, то мы нашли плохое подмножество.
Суммарная сложность O(N^3).
Правда ли, что: Ответ YES == можно провести прямую, по одну сторону белые, по другую чёрные ?
Нет, например треугольник из черных, вложенный в треугольник из белых.