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

Автор wistful23, 14 лет назад, По-русски
Возможно, здесь я смогу получить некоторые ответы на вопросы по сайту contests.snarknews.info.

Будет ли когда-нибудь возможность создавать виртуальные контесы?
Как видно, на сайте есть страница Past Contests, где напротив каждого контеста есть линка на Traing Room, но к сожалению, везде попадаем на Service not available.
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Думаю, это временные трудности. Я участвовал в старых контестах в Training Room.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как решать D и E с 3-го раунда?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    D-перебираем бинарным поиском ответ, проверяем наличие решения при таком ответе с помощью максимального паросочетания(дуги от истока к каждому человеку с пропускной способностью равной ответу, от человека к компании с пропускной способностью 1 и только в случае если компания есть в его списке предпочтений, ну и от компаний к стоку естественно)

    E--количество разбиений выпуклого многоугольника на треугольники диагоналями без пересечений равно числу Каталана(об этом в википедии можно почитать), а посмотрев на первые числа Каталана можно вывести формулу для i-того нечетного числа:
    res[i]=res[i-1]*2+1;
    res[1]=1;
    • 14 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      В D не нужен бинарный поиск (как и во многих похожих случаях):). Просто постепенно увеличивать пропускные способности. (сложность будет как у 1 макс потока)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А я не могу решить задачу про монеты четвертого раунда(задача F)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      не знаю поможет ли ето, но если взять a[0]=2, a[1]=2, a[i]=a[i-1]+a[i-2]. И результатом взять a[n], то получяется "Wrong Answer on Test 8".

      Возможно просто надо добавить что если N>P(некорое число ), то ответом будет -1.

      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Там вроде ответ 2 4 8 20 -1 -1 .....
        Можно нагуглить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Путем рисования я дошел только до 2 4 8 -1 -1 .... Обидно.
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Если кому-нибудь интересно, то эта игра называется Conway's soldiers
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Во время контеста в слепую отправил 2 4 8 21 -1 -1.... )
          Еще интересно, что выводить для нуля, т.к. по условию он может быть (но в тестах видимо нет)? Я вывел 1, т.к для n < 4 выводил 1 << n.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А как решается B из пятого раунда?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Она решается методом meet-in-the-middle. Перебираем все возможные строчки, которые можно получить из первой строки применением не более 5 перестановок, а также которые можно получить из второй строки применением не более 5 обратных перестановок. Ищем в двух полученных множествах одинаковые.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А задача А?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Переменных всего 3 (a, b, c), поэтому существует только 2^8 классов эквивалентности функций.
    Можно для каждого из классов найти самую короткую формулу. Это делается примерно так: добавляем в некоторое множество формулы "a", "b" и "c". Потом, применяя &, | и !, пытаемся строить новые формулы. Так до тех пор, пока происходят апдейты. 
    Осталось написать разбор выражений и вычислить значение данной функции при всех возможных наборах значений переменных. 
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Интересно, а методом Блейка можно решить?
      Т.е. сначала получить СДНФ, а потом сокращать ее этим методом.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Не уверена. Дело в том, что методы минимизации булевых функций направлены на минимизацию количества вхождений переменных, а в задаче требуется также учитывать &, |, ! и скобки. Кроме того, метод Блейка работает с ДНФ, а минимальная формула (по задаче) может не быть ДНФ. Например: !(a&b).
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
а как Е решается из пятого раунда? если можно подробнее. спасибо
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Динамикой, используя формулу

    f(k,m)=

    1) 1, если m=0.

    2) 0, если k=0 и m!=0.

    3) f(k-1,m)*0.7+f(k-1,m-1)*0.2+f(k,m-1)*0.1 - если предыдущие условия не выполняются.

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как решали D 4-го раунда (Translation)?
Я решил так: эмулировал действия до определенного MAX_STEP, если не все страницы переведены, то пытался найти цикл со смещением в последовательности (длина которой не превосходит MAX_LEN) из кол-ва переведенных страниц в день.
Мне кажется есть более простое и быстрое решение.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Бинарным поиском закрепляешь ответ. Теперь тебе надо проверить переведут ли за закрепленное количество дней все условия. Пусть у тебя есть вектор из N+1 значения (где N - количество вирусов), где первые N значений говорят о том, сколько есть вирусов соответствующего вида, а последнее - сколько страниц переведено. Создай матрицу, которая задает переход от одного дня в другой, возведи ее в степень, равную закрепленному количеству дней, и умножь стартовый вектор на получившуюся матрицу, в последнем элементе будет храниться сколько страниц переведено на этот день. Сравниваешь с нужным количеством, улучшаешь бинарный поиск.