Сегодня в 16.00 по московскому времени пройдет вторая индивидуальная олимпиада на neerc. Правила, как я понимаю, будут абсолютно такие же как и в прошлый раз.
Всем желаю удачи!
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 27.04.2024 08:08:56 (j3).
Десктопная версия, переключиться на мобильную.
При поддержке
если я зарегестрировался после начала, заявку уже не подтвердят?
Советую отправить просьбу на почту организаторам.
спасибо, это которая [email protected] ?
Подтвердили. Это так мило ^^
Да. Условия ведь открыты, пока что решай. Главное — чтобы в течении 4 часов подтвердили :)
киньте ссыль на задачи плз
http://neerc.ifmo.ru/school/io/today/problems-20121215-individual.pdf
спс
Пожалуйста)
Написал на D какой-то бред с неявными графами на 60 баллов. Как решалось нормально?
Я писал такое же, но оно норм работает и при больших тестах.
а где результаты посмотреть можно? :)
У меня вообще хромают графы. Поэтому реализация некачественная наверное. Максимум 200х200 таблицу за 5 секунд мое решение может посчитать
Где-то есть результаты, или это твои ожидания?
Мои ожидания
Не знаю, верно ли это... Персистентный снм. Построим вначале 1 версию для одинаковых цветов. Теперь идем по матрице. Вот у нас есть 2 соседних различных цвета u и v. Находим в хеш-таблице версию, где мы последний раз объединяли эти 2 цвета, в каких-то компонентах. Теперь по этой версии делаем новую, в которой компоненты, где сейчас эти 2 цвета лежат, объединены. Обновляем версию в хеш-таблице.
Я писал почти то же самое, только брал все ребра с вершинами фиксированных цветов, применял их все, апдейтил ответ, затем откатывался обратно. В этом случае можно просто хранить все изменения СНМ, а не писать честное персистентное.
1) разбиваем ячейки одинакового цвета на компоненты связности
2) между каждыми двумя ячейками с различными цветами проводим ребро. Ребро — это номера двух различных цветов и двух номеров различных компонент связности, которым принадлежат ячейки
3) сортируем ребра по паре цветов ячеек
4) пробегаемся по ребрам и выделяем группы с одинаковой парой цветов ячеек. В каждой группе соединяем компоненты с помощью СНМ с поддержкой весов компонент. После каждого объединения обновляем ответ если вес текущего корня больше найденного ответа
не очень понятна следующая вещь, если у нас есть ребро (1;2) и (2;3) (это пары цветов, которые соединяет), то мы соединим 1 и 2, и 2 и 3, и получим, что 3 компоненты (их цвета 1 2 и 3) войдут в ответ.
если есть ребро (1 2) и (2 3) то это разные группы
т.е. для каждой группы, у нас свой снм?
у нас один СНМ, но после каждой группы (группа — ребра с одинаковой парой цветов ячеек (1 2) == (2 1)) его надо очищать, а для этого запомним номера компонент которые мы "трогали" в текущей группе и потом за О(размера группы) возвращаем затронутым компонентам их начальные значения (p[i] = i)
Как С писать выше 40?
синхронно!
Сначала немного тупил над тем, как писать задачу синхронно.
Осталось тебя плавать хорошо научить.
как решать С?
Пусть в ответе нет 2-х клеток одного цвета, стоящих рядом. Тогда, шахматная раскраска, проверяем руками. Пусть есть, тогда каждая вторая строка/столбец — инвертированная предыдущая. Заметим, что если есть две вертикальные стоящие рядом клетки одного цвета, то горизонтальных нет, иначе наоборот. Ну, переберем эти два случая, сложим их, вычтем шахматные раскраски. Случаи рассматриваются так — точки "проецируются" на вертикаль/горизонталь. Если нет противоречий, ответ — 2 ^ кол-во нефиксированных клеток в вертикали/горизонтали.
Более сложную можно решить с помощью 2-SAT, эту тоже .. Но я думаю, есть более простое решение ..
Кнопку feedback организаторы просто так поставили или ее можно только в определенную фазу луны использовать?
Перед всеросом можно и перед иоип, перед региональным этапом нет.
вроде, можно будет использовать во время туров иоип и подготовки к всеросу
http://neerc.ifmo.ru/school/io/archive/20121215/standings-20121215-individual.html на сайте ссылки еще нет, поэтому вот(:
почему у многих так попадала Б? 500^3 не впихнулось?
Сам не пойму
Кто-нибудь добавит этот контест в тренировки? Мне кажется, что там не ТЛ, а ВА.
Как решать задачу Б?
-
6 же, не?
5 Первая — изначальная
Кто-то может написать полный разбор по задачам B, C, D?
до послезавтра постараюсь сделать
Готово
Добавьте, пожалуйста, данное соревнование в тренировки.
Добавлена тренировка — 2012-2013 Цикл интернет-олимпиад. Вторая личная олимпиада (15 декабря 2012 года) (в режиме ACM-ICPC).
Напишите, пожалуйста, разбор задач B, C, D. Если разбор лень — хотя бы просто идею.
Разбор готов :) смотрите выше)