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

Автор yaro, 14 лет назад, По-русски
А. Провинился — на кухню.
В задаче нужно было понять, какое максимальное x, упомянутое в условии, можно взять, чтобы каждого из ингредиентов хватило. Ясно, что это x = min(b_i / a_i). Осталось взять минимум из двух объемов — получившегося объема супа и объема кастрюли.

В. Незаконченная партия.
В этой задаче нужно было проверить ровно то, что сказано в условии: позиция короля и все позиции на доске, в которые он может пойти находятся под ударом, — значит, мат. Таким образом, нужно было правильно определить на доске позиции под ударом. Для этого поставим на доску только белые ладьи и белого короля, клетки, в которые может пойти король, отметим как битые, клетки, на которых стоят ладьи, оставим небитыми (чтобы черный король мог есть ладей), а клетки, до которых могут добраться ладьи, — тоже отметим как битые.

С. Взлом сейфа.
Ответ в этой задаче всегда положительный, то есть четыре единицы получить можно всегда. Действуя жадно (то есть делая операциями соседние числа четными и деля их на два), легко за логарифмическое (и получающееся, конечно, меньше 1000) количество операций добиться того, что сумма чисел будет не больше шести и дальше справиться со случаями, как многие и поступили. В чистом виде жадность не проходила, например, на тесте (1 1 1 2).
Есть и другие подходы, позволяющие избавиться от возни с "маленькими" случаями.

D. Странный город.
Расставим в вершины некоторые числа a_i. Тогда если ребру присвоить цену, равную сумме чисел на его концах, то сумма цен ребер вдоль любого гамильтонова цикла будет равна удвоенной сумме a_i. Осталось придумать такие числа a_i, чтобы их попарные суммы были различны (т.к. цены ребер должны быть различны). Причем такие варианты, как степени двойки или числа Фибоначчи, не годятся из ограничения 1000 на цену ребер. Тогда будем набирать a_i жадно, то есть новое a_i не должно быть равно (a_p + a_q - a_k) для любых уже выбранных чисел a_p, a_q, a_k. Такой выбор чисел в вершинах уже проходит. Причем, как несложно видеть, a_n = O(n^3), т.к. "блокирующих" троек (p, q, k) — O(n^3).
Другая идея заключается в том, что должно выполняться равенство AB+CD=AC+BD для любых различных вершин A,B,C,D (в сумме — стоимости соответствующих ребер), так как гамильтонов цикл с ребрами AB и CD "перестраивается" в цикл с ребрами AC и BD, а суммы у этих циклов должны быть равны.
Из этого, если хотите, можете понять, каким образом жюри точно и быстро проверяло ваши ответы.
Разбор задач Codeforces Beta Round 41
  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Странно что в задаче А, не было подвоха с тем, что числа Аi нужно сократить на их НОД.(на каком-то контесте див2 это было)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Числа a_i и b_i вполне могли быть и вещественными, суть от этого не поменялась бы. А НОДа у вещественных чисел нет. =)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Если кому-то интересно в какой задаче: раунд 16, задача С
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Придумал на контесте идею в D про AB+CD=AC+BD, но там получается около 9000 равенств в наихудшем случае. Что дальше с ними делать, чтобы решение получить нормальное, тоже жадно как-то?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    находим веса для 3 вершин, потом жадно вес для четвёртой (так чтобы ничего не нарушилось), потом для пятой...
  • 14 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    Я строил граф итеративно. На итерации i для графа из вершин 1..i-1 выполняется требование из условия.

    Когда мы добавим вершину i у нас должно выполняться c(i,j)-c(i,k)=c(z,j)-c(z,k) для всех z от 1 до i-1. Возьмем, например, z=1. Тогда получаем что c(i,j)-c(i,k)=c(1,j)-c(1,k). Выберем случайным образом c(i,1) из чисел, которые еще не были выбраны в качестве весов ребер. В таком случае мы можем расставить c(i,j) для всех j от 2 до i-1. Если теперь выполняется условие того что все веса лежат в промежутке 1..1000, а так же используются по 1 разу, то переходим на итерацию i+1, иначе заново выбираем c(i,1).

    Если после определенного количества таких попыток нам не удается выбрать c(i,1), то начинаем с самого начала. На контесте я сдал такое решение, правда не пытался начинать с начала в случае неудачи и задача у меня упала, но добавив это в дорешивании получил АС.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Всем привет.
Я немного запутался пр решении задачи D. Разве матрица следующего вида не решает задачу (размерность задается числом N)?


  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    представь что проходим из второй вершины в пятую через третью и четвертую
    2-3-4-5: 3+6+10 = 19 длина пути
    2-4-3-5: 5+6+9 = 18 длина пути
    Получается, что любой гамильтонов путь содержащий 2-3-4-5 по длине отличается от того же пути содержащего 2-4-3-5, а по условию все гамильтоновы пути имеют одинаковую длину.
    Для соблюдения этого условия необходимо расставить веса на вершинах, а вес рёбер брать как сумму весов вершин которое оно соединяет.
14 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
На задачу C жадник проходил вот так:
1) Найти наибольшое число.
2) Еслу можно поделить его на 2 - поделить.
3) Иначе - увеличить (один или 2 раза) и поделить.
Если наибольшое число больше 4, очевидно работает потому, сумма чисел уменшается после каждое деление. Иначе я не могу доказать, на контесте просто запустил на все малинкие тестов и увидел, что работает.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
http://www.codeforces.com/blog/entry/887
just to keep at one place..