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

Автор asmisha, 10 лет назад, По-русски

Давайте обсуждать задачи. Но прежде давайте сыграем в игру: угадайте, какой вердикт по задаче С получает посылка

cout << "! 1 2 3 4 5 6 7 8 9 10 11" << endl

А также посылка №2

cout << "! 10 9 8 7 6 5 4 3 2 1 а может так?" << endl
  • Проголосовать: нравится
  • +62
  • Проголосовать: не нравится

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

TL?

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

Задача I не блещет оригинальностью. Впрочем, я не против малоизвестных интересных баянов; но не очень хорошо, когда они могут сильно повлиять на топ standings.

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

Как С по-человечески решается? А то у меня уж слишком много рандома в решении.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +27 Проголосовать: не нравится

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

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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Прикольно. А я сразу вставлял бинпоиском и тратил в среднем по 3 операции на вставку. Поэтому запускал эту штуку только после того, как количество элементов становилось меньше ~70, а до этого резал рандомом.

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

      с какой вероятностью нам нужен будет бинпоиск, когда мы добавляем k-ый элемент? .

      Т.е всего нам бинпоиск потребуется в среднем раз. Это вроде около 70.

      Ну и оценка получается если я не туплю n + O(klognlogk), где k из числителя, logn из ряда и logk из бинпоиска.

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

    Ну там для рандомного порядка индексов надо просто искать k минимумов обычным методом вставок. Почему-то сразу верилось, что такое успеется за указанное ограничение. Как-то интуитивно опирался на то, что 700 намного больше корня из n.

    P.S. Редкий случай, когда в div2 задачу сдали быстрее, чем в div1. Пойду возьму с полки пирожок.

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

      Редкий случай:

      Задача D:
      Accepted Div.1 - 4
      Accepted Div.2 - 11
      
      Задача F:
      Accepted Div.1 - 1
      Accepted Div.2 - 7
      
      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +13 Проголосовать: не нравится

        В отличие от задачи С, задачи D и F в двух дивизионах слишком отличались ограничениями.

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится

          Да... Из-за ограничений, мое решение по F двумя тринарниками даже близко бы не прошло тесты.

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Теперь понятно. Я этого не знал, извиняюсь.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +34 Проголосовать: не нравится

    Строим дерево отрезков за n-1. Потом за klogn узнаём минимумы.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Двоичную кучу можно за O(n) построить.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится

    Есть другое решение: Ищем вначале 1, потом 2, ... всего 10 итераций поиска минимума. Все время храним для каждого числа список тех, которых оно оказалось больше в результате сравнения. На каждой итерации берем все числа, которые оказались больше только предыдущих минимумов и устраиваем между ними чемпионат на выбывание. Каждый чемпионат проходит за количество кандидатов-1 сравнений. На первой итерации будет n кандидатов. На каждой следующей логарифм, тк глубина дерева в чемпионате логарифмическая, а кандидатом может быть только тот, кто проиграл лишь предыдущему минимуму

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Расскажите, пожалуйста, решение A и F.

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    В А две динамики:

    D1[k][mask] = наименьшая пара чисел (количество шагов; занятое место на последнем шаге) необходимые для того, чтоб k-тый грузовик вывез все предметы помеченные в битовой маске mask. Пересчитывается перебором последнего предмета, помещенного в грузовик.

    D2[k][mask] — наименьшее количество шагов необходимых для того, чтоб первые k грузовиков вывезли все предметы помеченные в битовой маске mask. Пересчитывается перебором всех подмасок соответствующих грузу, перевезённому последним грузовиком.

    Плюс восстановление ответа.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    А: Найдём ответ для каждого подмножества предметов и для каждого контейнера динамикой по битмаскам (dp[i][bit]). А потом рекурсией с отсечением по ответу переберём контейнер для каждого предмета. Жутковатый код: http://pastebin.com/5VUN0Vds

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Задача F почти идентична задаче поиска описанной окружности минимального радиуса для множества точек.

    Общая схема решения:

    1. Рассмотрим точки в случайном порядке.

    2. Будем наращивать ответ. Если очередная точка уже лежит в ответе, то переходим к следующей, в противном случае говорим, что она обязательно должна входить в новый ответ. Вероятность этого события 3 / i.

    3. После фиксации одной точки, идём сначала и ищем две новые точки для ответа таким же способом. На этот раз вероятность ошибки 2 / i.

    4. Для двух фиксированных точек опять идём сначала и подбираем третью. Итоговая сложность — O(n), так как матожидание сложности каждого шага константное.

    По трём точкам искать подходящую окружность уже скорее техническая задача: строим прямые или окружности Аполлония и пересекаем.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      Я это и написал, и получил бревно. Не очень ясно, что делать дальше :)

      Например, что делать, если из-за точности окружности Аполлония не пересеклись?.. Вы это как-то специально обрабатывали?

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

        Есть еще случай "тупоугольного треугольника". Когда ответ это не персечение окружностей, а один из ответов для пар. Скорее проблема в этом.

        С точностью там конечно грустно. Когда мы увидели твой тест сидели и долго думали. Потом я отошел от ответа на 10^{-9} в случайную сторону и совсем оно не прошло. Собственно клар дальше видели. Но это мы конечно не правы в любом случае.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

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

А поделитесь кто-нибудь, пожалуйста, правильным решение по лабиринту.

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

    Пусть N = max(10, H, W), H, W — максимальные ширина и высота куда мы зашли. Сделаем бфс с нашей клетки до клетки (N, N), но можем использовать квадрат N + 1xN + 1 с учетом найденных стен. N + 1 берем для того, чтоб нормально увеличивать N и до клетки (N, N) всегда можно было дойти.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Именно бфс?

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится

        С клетки идем в следующую так, чтобы уменьшить расстояние до (N, N). То есть на каждом шаге делаем новый бфс. Код

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Не знаю, правильное ли, но зашедшее решение(в дорешку):

    Считаем, что там где еще стен не видели — стен нет. Поддерживаем maxn — максимум встретившейся координаты. Если мы в клетке maxn, maxn, то ++maxn Делаем bfs из клетки (maxn, maxn). Пытаемся перейти из текущей вершины в ее предка в bfs'е (т.е пойти по кратчайшему пути)

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      А кто-то умеет оценивать число ходов в таком bfs'е? Мы, когда это отправляли — не умели:) При больших n из-за большого числа стен маршрут будет почти однозначным и мы не будем делать лишних ходов? 5*N+300 это интуитивно довольно мало — учитывая то, что за ход считаются еще и неудачные удары об стенки.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Ну я бы не сказал, что это так уж мало. Казалось бы, нам нужно 2N ходов + иногда 1 из двух кратчайших ходов закрыт(где-то 2N/3), а вероятность, что нас заставят вернуться хотя бы на 1 клетку назад всего 1/9

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          У меня были подозрения по поводу того, могут ли образоваться длинные тупиковые ветви, в которые мы сначала зайдем, а потом вынуждены будем возвращаться назад. Трудно представить, как выглядит случайный на треть заполненный лабиринт, если честно. Спасибо, с таким объяснением сомнений стало меньше.

          Кстати, по поводу результатов на практике — наше решение падает на 75 тесте при ограничении в 1012 ходов, на 81 тесте при ограничении в 1013 ходов, и проходит при 1014 ходов.

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    В Div2 (за n2 + 1000 шагов) можно было просто устроить обход вдоль стенки. Он на 200 × 200 занимает 2500-3000 шагов без оптимизаций и ~2000, если немного улучшить.

    В Div1 (за 5n + 300 шагов) для 200 × 200 надо было уложиться в 1300 шагов, поэтому такое решение уже не должно было пройти. Тут помогает заметить, что лабиринт квадратный, а значит, нам надо идти примерно вдоль главной диагонали. Будем запоминать, где мы уже видели стены, и искать следующую не посещённую клетку, в которую хочется пойти, каким-нибудь поиском в ширину (я просто на каждом шаге заново просматриваю 100 клеток, достигнутых поиском в ширину из текущей; а можно запускать новый поиск, только когда мы пришли к промежуточной цели или уткнулись в стену). В клетки ближе к главной диагонали и дальше от начала координат больше хочется пойти. У меня весовая функция клетки — это row + col - abs (row - col). Такое решение обычно проходит лабиринт 200 × 200 за 800-1100 шагов.

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

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

      .

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        Есть как минимум четыре способа использовать такие (вероятностные) соображения на соревновании:

        1. Знать по опыту.

        2. Поверить.

        3. Проверить программно.

        4. Доказать аналитически.

        Первое могло помочь любому, кто строил лабиринт алгоритмом Краскала. На соревнованиях задача про такое построение была как минимум на одном из недавних контестов Petr-а в Петрозаводске.

        Второе очень легко использовать, но правильное применение (чему верить? чему не верить?) требует, опять же, опыта.

        Третий способ занимает компьютерное время, но в целом тоже не очень сложен: написать генератор лабиринтов, повыводить их и просто посмотреть глазами (или даже посчитать какие-нибудь метрики). Алгоритм Краскала умеют реализовывать многие. При подготовке задач для меня это основной способ проверки вероятностных соображений.

        Четвёртый способ обычно требует сильной математической подготовки. Можно делать грубые прикидки, как в этом комментари, но не всегда получается правда. В этом самом комментарии, например, оценка в 1/9, судя по результатам программ, получилась довольно сильно заниженной — она не согласуется с тем, что для 200x200 часто требуется ~1000 ходов.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +63 Проголосовать: не нравится

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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +17 Проголосовать: не нравится

      Ахахахах, кто-нибудь так сдал?

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +15 Проголосовать: не нравится

        К сожалению, нет — я нашёл только, что первый тест так разок прошли.

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          Огонь =)

          А как можно пройти первый тест, но не пройти все остальные? Вряд ли даже жюри умеет проходить любой тест за 2n + O(1) шагов =)

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Там какое-то решение со сложной логикой с закомментированными кусками. Вот, один раз ему повезло поплутать и прийти за 149 шагов. Во втором тесте тоже пришли, но плутали 2613 шагов уже.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

      Девиз сегодняшнего раунда: Интерактивные задачи — это проще, чем кажется.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +21 Проголосовать: не нравится

        Ну как сказать. Мы же не знаем, что там в лесу.

»
10 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

Подскажите, почему в задаче Е (grammar) в 3-ем примере ответ NO?

2 2
1 2 b 2
2 3 a a 1

Потому ли что невозможно написять небезконечного слова?

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

J?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

    Обозначим за x вес на ребре после добавления потенциалов. В каждой компоненте связности (слабой) поставим 0 в одну из вершин. Далее идем по ребру в любом направлении и однозначно восстанавливаем во всех вершинах значения в виде (Ax+b), иногда попутно получая равенства ax+b=cx+d, из которых находим x. Если получили несколько таких значений x(или не разрешимое уравнение) — все плохо. Если ни одного — тогда можно взять x = 0 (или любому другому числу)

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

А какое авторское решение задачи G?

А еще у вас что-то не так с чекером. У нас было два решения, которые выдавали разный ответ на тест 8 (одно из них -1, а другое какую-то конструкцию). Оба решение проходили этот тест и получали WA9.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Сейчас я вижу в системе четыре ваши посылки, и у всех на восьмом тесте ответ -1 — как и у жюри. А на девятом, действительно, WA, причём разные (один раз -1, три раза не -1).

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Ой, действительно, я перепутал. 8-й это видимо тест с нечетным n и a = 1.

      А как все-таки правильно решать задачу? (Я уже получил АС, но решение получилось с разбором кучи случаев, есть ли там красивое решение?)

      • »
        »
        »
        »
        10 лет назад, # ^ |
        Rev. 4   Проголосовать: нравится +16 Проголосовать: не нравится

        Некоторое вдохновение, чтобы решать задачу, можно почерпнуть в статье Константина Кнопа о взвешиваниях без разглашения. Собственно, идея задачи и получена из этой статьи и смежных текстов.

        Описание своего решения я оставлю в правке. Но наверняка есть много более красивых способов.

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +93 Проголосовать: не нравится

Посылка с текста блога получает ОК, и вообще можно вывести любые 10 чисел и получает OK. Интересно, как жюри допустило такую ошибку?

И еще, как объяснить то, что контест на яндексе начался на 15 минут быстрее?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +34 Проголосовать: не нравится

    Это --ц, господа.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    На yandex или где?

    Не слишком удивелен если честно. Там интерактивы работают никак. Призывается lperovskaya. В ejudge и на онсайте работало нормально.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Раз упомянули онсайт — когда ждать размороженную таблицу? :)

      И еще, кто-то может объяснить, почему всегда после подобных соревнований монитор opencup никак не отображает тот факт, что он еще далеко не окончательный? Например, можно сабмиты за последний час с онсайта отобразить хотя бы желтыми квадратиками. С этим есть какие-то технические трудности, или так специально делают?

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Это вопрос к снарку, а не ко мне. Размороженный монитор вот. Олег его почему-то еще не смерджил. Вопросики в заморозку там тоже есть. Почему их не экспортит не знаю. Вообще онсайт начинается не слишком синхронно с кубком обычно.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Несколько минут назад: http://acm.math.spbu.ru/cgi-bin/monitor.pl/m141214.dat .

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +42 Проголосовать: не нравится

      Слушайте, я опять вот нагнетаю, но зачем тогда этот Яндекс.Контест нужен вообще?

      Интерактивки не работают, время рантайма он нормально замерять не умеет, нужно на опенкапе две системы поддерживать, какие-то непонятные различные времена старта из-за этого

      Как-то много проблем с непонятной целью в итоге.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +14 Проголосовать: не нравится

        Он нужен яндексу. Можно воспринимать это так — яндекс спонсирует студентам поездки, а студенты тестируют ЯК. Желающим никто не запрещает писать в ejudge, так что все честно. Проблемы с мерджингом standings рано или поздно пофиксятся я думаю.

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

        Еще там вроде с подсчетом МЛя были проблемы (что-то типа размер входного файла к нему добавлялся), если я ничего не путаю.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Контест начался на яндексе раньше из-за проблем с ejudge я так понимаю. Почему не отложили синхронно — не знаю. По поводу задачи C — это бага дорешки или на контесте тоже был кривой чекер? Будет ли rejudge?

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      Бага yandex.contest Чекер был и есть нормальный. Остальное решать snarknews.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится

        Я думаю, Олегу по меньшей мере надо протестировать сабмиты по интерактивкам в еджадже, чтобы мы знали реальные результаты сабмитов. А дальше по тому, кого и как заффектило, принимать решение о том, как именно пойдут результаты в зачёт.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится -10 Проголосовать: не нравится

        Павел, а поясни в чем было дело. Вот я уже сто раз нарывался на сложности из-за того, что все по-разному поддерживают интерактивки. Палевно это, надо унифицировать!

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится

          Проблемы в системе вида "никогда не смотрим на результат работы чекера" и "никогда не смотрим на результат работы интерактора" — это просто ошибки, которые надо исправить, а не нюансы поддержки интеракторов. Обсуждаемая система ещё не в той стадии, чтобы надо было унифицировать нюансы, к сожалению: чтобы унифицировать, надо сначала поддержать.

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

            А мне кажется надо выработать общий стандарт как должно быть, а тех кто не поддержит (из основных игроков: Codeforces, ИТМО, СПбГУ, Яндекс.Контест, ejudge) укорять и называть недоразвитыми. Тогда быстренько поддержат и будет счастье :-)

            • »
              »
              »
              »
              »
              »
              »
              10 лет назад, # ^ |
                Проголосовать: нравится +16 Проголосовать: не нравится

              Ну, есть несколько постов на CF о состоянии интерактивных задач на ~2012 год. Системы ejudge (версия Снарка) и testsys (СПбГУ) с этим более-менее справляются. С тех пор точно произошёл прогресс у Паши Абизяева, повлиявший на ejudge Снарка, но я не знаю деталей. Было бы здорово, если бы об этом кто-то написал пост.

              • »
                »
                »
                »
                »
                »
                »
                »
                10 лет назад, # ^ |
                  Проголосовать: нравится +22 Проголосовать: не нравится

                По-моему там остались какие-то открытые вопросы (типа что произошло интерактор вернул PE так как упало решение или решение упало по RE так как интерактор сказал PE и неожиданно закрыл пайп). Плюс ИТМО только поддерживает как-то не так. Короче, имеет смысл оживить дискуссию.

                Кроме того, я думаю отличная идея сделать модельную задачу (с кучей решений), которая будет демонстрировать все случаи разных вердиктов и ситуаций. Типа правильно система все вердикты выдает по задаче — значит ОК.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 лет назад, # ^ |
                    Проголосовать: нравится +12 Проголосовать: не нравится

                  Да, сделать модельную задачу — это отличная мысль.

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится +8 Проголосовать: не нравится

            Хм, а можно больше конкретики? Я видел прекрасно работающие интерактивные задачи на я.контесте, значит, он их в каком-то виде таки поддерживает.

            И да, что такое "результат работы интерактора"? stdout? stderr? созданные файлы? отправленные сетевые пакеты? Или имеется в виду код возврата?

            чтобы унифицировать, надо сначала поддержать

            Странное утверждение. Казалось бы, сначала должен появиться стандарт, а потом уже все должны его поддерживать, а не городить страшные велосипеды.

            • »
              »
              »
              »
              »
              »
              »
              10 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Из моего небольшого опыта с интеракторами на яндекс-контесте:

              (1) Перед предыдущим чемпионатом университета выяснилось, что новая версия, в которой была улучшена поддержка школьных задач, почему-то проверяет мою интерактивную задачу только на первом тесте. Получившееся решение — откатить на предыдущую версию.

              (2) На этом чемпионате университета было, видимо, несколько проблем (видимо — потому что я не уверен, что понял всё правильно). Во-первых, чекеры в интерактивных задачах, видимо, вообще не запускались (на предыдущем чемпионате с чекером return 0 это было неважно). Это выражалось в строчках лога типа

              ...
              solution executed with errors, don't run checker
              result: OK
              ok (got to destination)
              

              Здесь ok (got to destination) — это комментарий интерактора. По плану интерактор выводил в выходной файл количество шагов, чекер читал его и сравнивал с лимитом, после чего выдавал ok/wa со своим комментарием вида wrong answer 31 x 31, steps 479, limit 455. Вообще, лог приведённого выше вида вызывает больше одного вопроса.

              Помогло встроить чекер в интерактор, это изменение делалось всего в пару строк. После чего, видимо, оказалось, что работает только один из вариантов testlib-exitcode-interactor и ejudge-exitcode-interactor в настройках интерактора.

              Поскольку общее впечатление было, что в задаче D всё вообще не работает — настолько, что первые несколько посылок в яконтест я проверял перепосылкой в testsys — сообразить, что в задаче C может быть та же проблема с чекером, не сложилось.

      • »
        »
        »
        »
        10 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится +29 Проголосовать: не нравится

        В результате исследования свойств реализации интерактивных задач на платформе Яндекс.Контест выяснено, что в данный момент интерактивные задачи реализованы следующим образом:

        1. Даже в случае кода возврата интерактора 0 чекер не запускается.

        2. При завершении интерактора решение участника всегда убивается (то есть варианта "завершить интерактор и подождать, не случится ли TL/RT" нет).

        3. Результат проверки посылки определяется кодом возврата интерактора, при этом используются только "testsys exitcodes" (то есть 0 = Accepted, 1 = WA, 2 = PE, остальное — Fail aka JE aka Crash).

        Таким образом, реализовать интерактивную задачу на данный момент можно в случае, когда вся проверка делегирована интерактору. В случае наличия чекера его придётся интегрировать в интерактор, поставив в качестве чекера заглушку return 0; (чтобы работало и после предполагаемых исправлений).

        Информация до разработчиков доведена; через какое-то время, скорее всего, ситуация с незапуском чекера будет исправлена.

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

      К сожалению, OK не снимаются.

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится +8 Проголосовать: не нравится

      Задержка была со стартом D2, из-за чего условия были открыты только в 11-55 (практика показала, что если открывать на раздачу только Div1 условия, их раздают и Div2 и случается путаница). D1 был готов там и там.

      Что касается интерактора по C. Сейчас ситуация проверяется, но результаты Гран-При вряд ли будут изменены — снятие OK после контеста, увы, не является допустимым действием. Единственный возможный вариант изменения результатов — снятие заведомо неверных решений типа того, что приведено в тексте сообщения.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +9 Проголосовать: не нравится

        Считать раунд зачётным, если в нём из столбца плюсов по C большое количество окажется нечестными, так же едва ли является допустимым действием.

        В любом случае, хочется знать реальные резльутаты сабмитов по задачами.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +25 Проголосовать: не нравится

        Хотя бы для статистики можно будет узнать, какие решения по С на самом деле прошли, а какие — нет? Или, на худой конец, сколько — не указывая конкретные команды.

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

          Не прошло у двух команд за пределами Top30, включая топикстартера. У остальных все сданные на контесте сабмиты прошли на ejudge. Отправленные для прикола в upsolving не прошли.

          Так что на распределение очков как обычного, так и спонсорского зачёта сбой повлиять не должен никак.

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

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Было немного неочевидно, что делать, если получаешь PE на втором тесте. А когда стало понятно, что заходит любая чушь — интерес отлаживать решение пропал.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Расскажите пожалуйста K.

В дорешку зашёл 600-строчный код от e-maxx. Но мне почему-то кажется что кто-нибудь писал что-нибудь проще.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Первые степени простых не влияют. Поэтому можно искать только простые делители до 10^6. То, что осталось достаточно провеирть на квадрат, если не квадрат, то можно считать одним большим простым числом.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Спасибо. Вот именно этой проверки на квадрат мне и не хватило до акцептеда. Глядя на табличку в Div2, думаю не мне одному.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А E решается без симплекс-метода/метода эллипсоидов?

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

    Прелположим, что все правила в грамматике имели бы в правой части не более одного нетерминала. Тогда для правила A —  > Baa..abb..b проведем ребро из A в B веса, равного разности количества букв "b" и букв "a" в правой части, а для правила A —  > aa..abb..b проведем ребро из A в специальную вершину-сток T с понятным весом. Получилась задача о поиске кратчайшего пути из стартового нетерминала S в T с отрицательными весами. На помощь приходит алгоритм Форда-Беллмана.

    Теперь обобщим. Для каждого нетерминала X будем считать его "расстояние" — минимальную разность числа букв "b" и "a" среди конечных слов, выводимых из нетерминала X. Инициализация простая: если из нетерминала X выводится какая-то строка только из терминалов, то это и будет начальное "расстояние". Теперь будем n раз делать релаксацию: будем бежать по всем правилам и если оказалось, что во-первых, для всех нетерминалов в правой части правила уже посчитаны какие-то "расстояния" (то есть можно вывести хоть какое-то конечное слово), а во-вторых, суммарные "расстояния" в правой части плюс разность числа букв "b" числа букв "a" в правой части меньше, чем текущее "расстояние", то обновляем "расстояние" до нетерминала в левой части.

    В конце проверяем, есть ли отрицательный цикл, и достижим ли он из стартового нетерминала. Сами расстояния храним в длинном числе.

    Вопрос в том, сколько же итераций нужно сделать "Форду-Беллману". Точно не больше n + m, и есть идея (подтвержденная на контесте Accepted-ом), почему n: предположим, что ответ конечен. Построим вспомогательный граф, в котором проведем ребро между нетерминалами X и Y, если мы в какой-то момент при выводе оптимального ответа воспользовались правилом, где X в левой части, а Y — в правой. Может быть, используя этот ацикличный граф, можно доказать, что итераций надо n.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Часть про один нетерминал в правой части понятно. А как потом вы ищете отрицательные циклы — неясно, там же какой-то мультиграф. Или имеется ввиду, что если после m+n (ну или n, если удастся доказать) итераций что-то продожает релаксировать, то есть отрицательный цикл? Кстати, я даже m+n не умею доказывать, что хватит

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Да, если после n итераций что-то прорелаксировалось, то считаем, что есть отрицательный цикл. Говорим, что из A достижимо B, если существует последовательность правил, которую можно применить к A такую, что в какой-то момент появится нетерминал B, и при этом вывод можно будет довести до строки из терминалов.

        Про n + m итераций: построим полное дерево вывода. Утверждается, что на пути от корня до любого из листьев мы не воспользуемся одним и тем же правилом вывода (опять же, все в предположении, что ответ — конечный, т.е. нельзя получить строку со сколь угодно маленькой разностью).

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        Кстати, по поводу n итераций.

        Пусть существует конечная оптимальная строка (т.е. та, которая минимизирует разность числа букв "b" и числа букв "a"). Рассмотрим дерево вывода этой строки, причем выберем то, в котором число переходов минимально. Докажем, что в этом дереве нет пути от корня до листа, в котором какой-то нетерминал встречается дважды.

        Действительно, пусть такой путь нашелся, то есть в оптимальном дереве встретился нетерминал A (_нетерминал-отец_), и в его поддереве нетерминал A встретился снова (_нетерминал-сын_). Тогда посмотрим на окончательную строку, получаемую из нетерминала-отца, пусть в ней разность b и a равна x, а для нетерминла-сына она равна y.

        • если x > y, то мы можем заменить все поддерево нетерминала-отца на поддерево нетерминала-сына, при этом уменьшив итоговую разность. Это противоречит оптимальности строки.
        • если x = y, то мы можем сделать то же самое, при этом уменьшится размер вывода (а мы выбирали минимальное).
        • если x < y, то мы можем заменить поддерево нетерминала-сына на копию поддерева нетерминала-отца, и снова уменьшить итоговую разность.

        То есть, если существует конечный ответ, то в дереве вывода на пути от корня до листа все нетерминалы различны, а значит каждый путь от корня до листа имеет длину не больше n, а значит n итераций релаксации достаточно.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Хм, вот что непонятно. С ограничениями в условии задачи можно построить такую грамматику, что "расстояния" будут огромными, т.е. надо использовать BigInteger. Но тогда непонятно, как n итераций успевают с такими огромными BigInteger'ами.

      Мы написали примерно такие же итерации на контесте (в int'ах), но получили WA42, и, подумав про переполнение и BigInteger, забили на задачу.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Мы понадеялись на лучшее:) И немножко пооптимизили длинку (от которой, кстати, нужно только сложение и вычитание).

        Плюс стоит заметить, что у нас "расстояние" не может быть сильно положительным (нет смысла генерировать кучу букв b), а если оно сильно отрицательное, то оно уже  - inf.

        К тому же, есть ограничение на размер инпута (5МБ).

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Странно, что никто из Div.2 нерешил. Ведь ограничения совсем маленькие: 1 <= n, m <= 2, 0 <= k <= 3.