Блог пользователя rmn

NEERC 2011 Western Subregional
Автор rmn, 13 лет назад, По-русски

На сайте Яндекс тренировок есть NEERC 2011 Western Subregional Contest.
Кто решал, можете поделиться идеями по задачам B,E, F, I или J? :)

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Е: Считаем вероятность противоположного события (все джентльмены выбрали разные цвета), просто умножая 1 на (2*с-2*i)/(2*c-i), 1<=i<M. Как только вероятность стала меньше eps, выводим 1.

I: Находим компоненты связности. Если хотя бы одна содержит нечетное число вершин - impossible. Иначе строим искомый граф с нуля. В каждой компоненте начального графа пускаем дфс, для каждой вершины: если степень потомка в новом графе четная - добавляем ребро вершина - потомок в новый граф.

Остальные не решил, самому очень интересно)

→ Ответить
13 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
Задача F.
Будем решать следующим образом.
Возьмем какое-то количество различных простых чисел pi, таких что их произведение больше, чем X.
По каждому из этих модулей найдем определитель матрицы и обратную к ней за пробег Гауссом по модулю.
Известно, что обратная матрица обладает следующим свойством - каждый ее элемент - это алгебраическое дополнение, деленное на определитель.
Будем теперь перебирать элемент, который мы собираемся менять, и будем раскладывать определитель матрицы по той строке, где он лежит. Очевидно, что алгебраические дополнения, на которые мы умножаем, не меняются, поэтому это делается ( подсчет определителя) за O(N). Теперь имеем систему модулярных сравнений. Если каждое из них разрешимо, то восстановим ответ по КТО, не забывая, что он может быть отрицательным.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Слушай, а опиши кратко, что на этом сайте Яндекс-тренировок можно делать. И можно ли там зарегистрироваться?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Понял, там виртуальные контесты. Логин, вроде, нужно использовать opencup'овский.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Вчера решали этот контест, интересны задачи B(Pouring water) и Midsummer fires(забыл какая буква).
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

    G (Midsummer Fires):

    Ключевой факт - что каждая тень - это такая бесконечная полоска с константной толщиной (короче, прямоугольную форму имеет).

    Задача свелась к тому, что есть такие бесконечные полоски, и есть точки, и надо для каждой точки узнать, попала она хоть в одну полоску или нет.

    Учитывая, что все эти полоски ориентированы по направлению от одной и той же точки - от точки источника света, можно сделать такое решение: отсортировать всё (и полоски, и точки) по расстоянию от источника света и обрабатывать в этом порядке. Мы поддерживаем все текущие полоски в отсортированном по углу порядке (в виде set, например), и тогда для ответа на запрос нам надо просто взять две полоски, соседние по полярному углу с текущей точкой-запросом (можно понять, что другие полоски, чем ближайшие по углу, нет смысла брать).

    Ну и там у нас проблемы с точностью были, так что стараться как можно больше всего в целых числах делать.

    P.S. Задача B тоже интересует, мы не сдали.

    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А почему константная толщина, ведь источник света - одна точка?
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится +12 Проголосовать: не нравится
        Потому что пирамидки сами имеют наклонную форму.
        Вообще это сложно понять физически, но это можно вывести формулами.
        → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Расскажите пожалуйста решение по J(One-Armed Bandit).
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      А там достаточно тупое решение.

      Дело в том, что даже в худшем случае нам не придётся менять очень уж много элементов, потому что количество различных чисел (пусть даже и с константной суммой цифр) растёт весьма быстро.

      Поэтому решаем так: перебираем, сколько цифр на суффиксе входного числа мы будем менять, и запускаем динамику с двумя состояниями (количество_цифр, сумма_цифр), которая возвращает нам количество таких чисел - и если это количество стало >= T, то мы останавливаемся и выводим ответ, восстанавливая его по динамике.

      Точно асимптотику сложно оценить, но работает быстро.

      → Ответить
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Кстати говоря, эту тему почему-то не показывает в "Прямом эфире", если в настройках поставить галочку "Скрывать блоги с низким рейтингом". Неужели +10 такой низкий рейтинг? Я как-то думал, что скрывает только с отрицательным.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится
Всем, привет. Я один из авторов контеста. Б с радостью расскажу после NEERC, может еще кто-то порешает контест. А пока меня больше интересует ваше впечатление от задач: интересность, сложность, оригинальность.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да ладно, кто захочет порешать, тот просто пусть не читает разбор. Лучше подумай о тех, кто решал контест, думал над задачей и хочет узнать решение. Чтобы случайно не пропалили, спрячь спойлер за новой версией комментария.
    → Ответить