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

Uva World Finals Warmup I
Автор hydrastuff, 13 лет назад, По-русски
Можно здесь обсудить контест. Интересно как решать A, F .
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
F так решал:
сначала разбиваем все на группы <символ, количество>
затем:
1) если у нас первая группа это вопросы, то смотрим какая группа идет за ними и в зависимости от четности делаем либо 1010101... либо 010101.. чтобы последний из вопросов не совпал с первым элементом следующей группы. Например: ???11 меняем вопросы на 010, если ????11 то меняем вопросы на 1010
2) если у нас последняя группы это вопросы, то аналогично 1)
3) если у нас вопросы между группами из нулей 0???0 или 0????0
3.a) если вопросов нечетно, то заменяем на 1010101...1, иначе на 11 010101...01 -- тут у нас появляется группа из единичик состоящая из 2х элементов, но видно, что оптимальней никак, иначе бы нам пришлось поставить рядом с другим ноликом еще один нолик и тоже бы получили группу как минимум из 2х, так что мы ничего не ухудшаем.
4) если у нас вопросы между группами из единиц, то аналогично 3)
5) если у нас вопросы между группами из разных символов, например 0????1 (для 1????0 аналогично), то
5.а) если количество вопросов четно (например 0????1) то заменяем на последовательность чередующихся нулей и единиц начинающую на элемент группы которая стоит после группы вопросов (например для 0????1 это будет 1010)
5.b) количество вопросов нечетно и больше 1, то почти сначала идут два элемента таких же как у следующей группы, а потом чередуются (для 0?????1 будет 0 11010 1)
5.c) если количество вопросов равно 1, то нужно то надо заменить его на цифру той группы, у которой количество элементов в группе меньше, чем у другой (0?11 - тут меняем на 0, если 00?1 то меняем на 1), а при равенстве цифру той группы, которая стоит до вопросов (чтобы не сделать хуже дальше). Только нужно учитывать это потом при просмотре, если мы добавляем цифру к следующей группе. 

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

F решается дихотомией по ответу. А именно так:

Надо научиться за линию проверять можно ли с максимальной группой не более чем x покрыть нашу строку. Заметим пару следующих фактов:

1) Все ? в начале строки можно спокойно отбросить (действительно ведь иначе мы сможем их заменить на 01010... или 10101... в зависимости от того с чего начинается первый не 0 символ).

2) Рассмотрим некоторую позицию. Пусть перед ней было x одинаковых символов подряд, тогда если следующий символ ?, то он обязан быть символом противоположного типа.

3) Если в какой-то позиции нашей строки было менее чем x символов подряд одного типа, то тогда можно выбрать то на что заменить ?, так чтобы перед следующим символом не было одинаковых с ним. (аналогично с группой ?).

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

→ Ответить
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Тоже интересно как решать A.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Вопрос отпадает. Ее можно решить через hook-lenth formula. Неужели все кто ее сдал знали эту формулу?:)
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
По поводу этой записи в блоге и комментам возникла пара вопросов. 1. Давно хочу узнать что такое World Finals Warmup I. 2. Что такое дихотомия?. 3. Что за формула hook-lenth formula?
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    1. На uva традиционно проводят контесты непосредственно перед финалами
    2. Раздвоение; в нашем случае дихотомия=двоичный поиск
    3. Видимо, имеется в виду формула крюков: mmmf.math.msu.su/lect/spivak/kruk.pdf
    → Ответить