Блог пользователя ivan.popelyshev

Автор ivan.popelyshev, 13 лет назад, По-русски

Поздравляю Петра Митричева с потрясающим результатом и победой! Сегодняшнее выступление Петра сильно подняло моё настроение, я теперь гораздо быстрее победю вирусную инфекцию.

Каждому из 14 квадратов надо присвоить какую-то цифру от 0 до 6, каждая цифра должна соответствовать паре квадратов. Сразу заметим, что если взять корректное решение и применить перестановку ко всем цифрам на поле, мы опять получим корректное решение. Следовательно, решение характеризуется разбиением 14 квадратов на пары. Если мы имеем такое разбиение, то по нему можно сгенерировать 7! решений. Возможных разбиений всего 13!! = 13·11·9·7·5·3 = 135135 . Первому квадрату соответствует один из 13-и, следующему без пары - 11, и.т.д. Сотню тысяч вариантов легко перебрать и проверить корректность.

С точностью до поворотов, всего конфигураций поля, которые имеют решения, около 6 тысяч. Наибольшее число решений - 22·7!.


Подколки:
1) Если не оптимизировать решение в 7! раз , можно получить TL. В комментариях уже указали что хватит оптимизации и в 7 раз.
2) Можно подумать что квадратики делятся на два класса - 7 квадратиков в которых есть доминошка дубль, и 7 в которых ее нету. Если говорить в терминах графов, 7 вершин со степенью 2, и 7 со степенью 4. Понятно, что две вершины степени 2 не могут соответствовть одной цифре, иначе получаем два дубля одной цифры. При таком делении достаточно перебрать 7! возможных соответствий вершин второго типа вершинам первого типа.

А теперь рассмотрим второй претест:

Дубль 4-4 поделен между двумя квадратиками. Имеем 6 вершин степени 2 и 8 степени 4. Challenge Succeeded.
Более того:

Здесь целых два дубля появляются на стыках квадратиков!

И бонус,одна из красивых конфигураций с несколькими дырками:

Очень жаль, но несвязных конфигураций c решениями не существует :(

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

13 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится
Хороший разбор.

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

Да и вообще. Может быть, у всех с этим всё хорошо, но мне с некоторых пор на CodeForces удобнее начинать с задач C, D, E, чем с A или B.
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Да, это ошибка. Я считал задачу очень простой, несмотря на то что у других членов жюри она изначально TL-илась. Про тестирование для разбалловки как-то не подумал :(
    • 13 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      Ну если относиться к разбалловке не как к подсказке (зная, что она субьективна), а как к параметру задачи (насколько выгодно её решать и когда), то всё нормально :) .
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
>Сегодняшнее выступление Петра сильно подняло моё настроение.
Хм. Который сделал пять неверных посылок по вашей задаче...
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Он очень быстро расщёлкал остальные решаемые. А тут была интрига до самого конца, сдаст или нет, думаю многим было интересно.

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



13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
>При таком делении достаточно перебрать 7! возможных соответствий вершин второго типа вершинам первого типа.

Спасибо за второй претест!

На самом деле можно найти количество "хороших" квадратов пусть их будет А (а не 7). И тогда перебрать все (14-A)!/27-A вариантов, ответ умножить на C из 7 по А и на А!.