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

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

Закончилась интернет-олимпиада. Скажите, пожалуйста, как решалась в базовой номинации А и F. Мы видимо неправильно поняли условие.

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

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

Я так понимаю, имеется ввиду базовая категория? Обсуждать задачу F еще нельзя, так как она участвует в задачах усложнённой категории (H).

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

А задача A решается за линейное время: перебираем k сверху вниз. Заметим, что оно подходит тогда и только тогда, когда все элементы  ≥ k занимают позиции  ≥ k. Будем поддерживать минимальную позицию среди элементов  ≥ k, на каждом шаге один раз проверили, что она  = k и прорелаксировали.

Да, еще надо, конечно, предподсчитать за линию для каждого элемента его позицию.

Также есть другое решение: скажем, что k подходит, если первые n - k элементов имеют номера  ≤ n - k. Делаем всё то же самое, но в другом порядке и не нужен предподсчёт.

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

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

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

      По смыслу надо выводить те и только те позиции, максимум в которых совпал с номер позиции. Ваше решение выводит что-то непонятное (точнее, непонятно, какое это отношение имеет к решаемой задаче).

      Тест:

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

Как все решали E? Мы писали совсем тупой перебор с передачей вектора состояний мечей и уровня их зарядки и еще текущего времени. На локальной машине это довольно долго работало, но мы решили заслать и получили AC. Это и предполагалось или было что-то более оптимальное?

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

    Мы писали декартово дерево по неявному ключу.

    UPD. извините, перепутал задачу

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

      Это в задаче с Mum!???

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

        Да, в ней. Кстати, интересно, как же она решалась без этой структуры?

        UPD. Уже прочитал про списки.

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

    Ну да, там ведь сложность будет O(3^(1+2+...+n)).

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

Задача F решалась так:

  1. Считаем кол-во клонов, с нечетными координатами
  2. Считаем кол-во клонов, с четными координатами
  3. Умножаем кол-во 1-ых на кол-во 2-ых
»
11 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Подскажите кто-нибудь, как решалась задача "Парад победы" (она была в обоих номинациях)? Верно ли, что при всех n, дающих остаток 2 или 3 при делении на 4, ответ 0? Верно ли, что во всех перестановках, удовлетворяющих условию, количество инверсий равно n * (n - 1) / 4? Заранее спасибо.

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

    Да. Верно. Всего пар n*(n-1)/2. Если сложить инверсии перестановки слева направо, и наоборот, то получим n*(n-1)/2. Значит, количество инверсий в данной перестановке должно быть n*(n-1)/4. Дальше F(i,j) — количество перестановок длины i с количеством инверсий j.

    F(1,0)=1 F(i,k)=f(i-1,k)+f(i-1,k-1)+...+f(i-1,k-i+1)

    Это выводится, если мы будем перебирать куда ставить 1.

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

Как Б решалась? Мне почему-то кажется, что там должно быть что-то проще, чем декартово дерево. Ведь можно как-то использовать, что там будут меняться лишь циклический сдвиг при операции "мум!"?

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

    Мне кажется списки, но очень неприятно писать!

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

    Мы решали двумя связными списками. Первый — первая половина (с округлением вниз), второй — вторая. При добавлении/удалении иногда нужно было перекинуть один элемент в другой список. При операции "мум!" просто меняем списки (указатели на начало/конец) местами..

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

      Этот неловкий момент...

      Зато довольно красиво получается)

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

    Решал одним списком. При добавлении/удалении элемента считал средний за O(1). При mum! менял начало и конец списка также за O(1), зная средний элемент.

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

    Один связный список + сохранение первого меча и центрального

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

    Мы писали просто два deque`а, также перекидывали 1 элемент в другой список. Была еще переменная bool, которая отвечала за то, какой список из двух левый, а какой правый. Вот код http://pastebin.com/q4gJSuXy

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

Как решалась Е? Очень долго думал, но так и не придумал...

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

    Надо было аккуратно написать перебор, разве нет?

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

      Объясни более обширно

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

        Код. Например можно делать так. Храним массив "сколько осталось времени работать i-му мечу", а также массив времен, которое мы могли измерить. На каждом этапе мы можем с каждым из мечей совершить три действия. Перебираем все возможности. Для каждой из них находим время, через которое разрядится какой-нибудь меч. Рекурсивно вызываемся для новых "оставшихся времен работы", и добавив новое время.

        Если ни одного мяча не осталось, то время, которое мы можем измерить это разность каких-нибудь из времен, которые есть у нас в массиве. И еще понятно, что если назначить начальное время работы каждому мечу 2^N, то оно всегда останется целым.

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

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

В задаче С в формате вывода сказано, что ответы должны быть даны с точностью не менее 3 знаков после запятой. Соответственно с этим я подумал, что можно просто все на 10^5 домножать (что в худшем 10^19 — влезает в unsigned long long), чтобы не писать мультисет с даблами. Как раз получится точность 1e-4. Отправив решение сюда, получаю WA на 23 тесте.

Немного помучавшись, скачиваю тест и сраниваю ответы таким вот кодом. Локально он ничего не выдает. Поставив же точность 1e-5, такие отрезки находятся. Переписываю сет на даблы, ставлю вывод 6 знаков — решение заходит.

UPD
Порадовала строчка в чекере официальном
if (diff > 1e-5) return new Outcome(Type.WA, "Participant's answer differ more than 1e-3");

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

    Бывает, жюри тоже люди. Олимпиада все-таки была скорее тренировочная.

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

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

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

Расскажите как решать Покраску забора. Вот такое решение дает TL 23 http://pastebin.com/GUbLcHnd

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

    А у тебя решение за O(n^2)? Решение жюри за O(n*log n). Используем любую структуру данных, которая позволяет добавлять/искать/удалять элементы за логарифм. В ней храним "отрезки". Для каждого отрезка храним его "цвет" (в даблах) и кол-во отрезков, из которых он был получен. При добавлении нового отрезка, смотрим с кем он пересекается, удаляем их, и пересчитываем цвет и размер нового отрезка (можно доказать что в сумме все выполнится за N*logN).

    Ну и еще храним отрезки каких цветов сейчас есть в структуре, которая позволяет получать максимум "за быстро".

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

      А как при добавлении отрезка смотреть, какие он пересекает?

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

        можно добавить концы отрезка — то что между ними, то и пересекает.

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

          А как найти те, что между ними?

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

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

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

        В Java, например, в TreeSet'e (где мы храним уже добавленные отрезки) есть стандартные функции higher/lower. Если у нас компаратор сортирует отрезки по левому краю, нужно проверить, что "самый большой отрезок, меньший текущего" пересекает / не пересекает наш. А потом, пока есть отрезок, больший нашего, но пересекающийся с текущим, объединять их.

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

Как делать первую и третью?

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

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

    будем поддерживать количество площадей и обновлять после каждого разрушения стены, изначально nm. количество новых площадей будет зависеть от того, принадлежали ли соединяемые клетки корректным площадям, и образовалась ли в результате разрушения новая площадь. т.е. если мы соединили две "неплощади" и образовалось площадь — количество площадей+1.

    как узнавать, корректная ли площадь? будем знать минимальную/максимальную x/у — координату лежащую в данной компоненте снм, чтобы проверить хорошая ли площадь, нужно проверить, равно ли количество операций проделанных над данной площадью количеству стен в компоненте — (maxx - minx + 1)(maxy - miny) + (maxy - miny + 1)(maxx - minx). код

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

Может кто-нибудь растолковать, почему не проходит java_solution (time limit test 19) Но проходит C_solution
PS Задача A

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

    Попробуй заменить:

    1. Integer n, cnt; Integer[] place, answer; на int n, cnt; int[] place, answer;
    2. Integer.decode на Integer.parseInt
    3. out.printf("%d ", answer[i] + 1); на out.print(answer[i] + 1);out.print(' ');