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

Автор Sereja, 13 лет назад, По-русски
Задача А(cAPS lOCK)
 В задаче делаем все что просят в условии, если есть хоть одна строчная буква не считая первую, то оставляем все как есть, иначе меняем все буквы на противоположные. Что-бы поменять значение регистра, нужно в случае большой буквы прибавить к коду 32, иначе отнять 32.
 Посчитаем кол-во каждого числа, пускай кол-во числа i - B[i] тогда ответом будем сумма B[i]*B[-i], i=1..10 + B[0]*(B[0]-1)/2.
 Перебираем сколько мы будем брать мальчиков(пуская будет х) , считаем сколько нужно девочек на оставшиеся места(пускай будет у), если оба параметра удовлетворяют входные данные то к ответу добавим C(N,x)*C(M,y), где C(n,k) - кол-во способов выбора k элементов из n. В данной задаче лучше считать с помощью треугольника паскаля используя свойство: C(n,k) = C(n-1,k-1) + C(n-1,k), C(n,0) = 1. Так-же важно не забыть что если не проверять границы , то-есть допускать M<y, то возможны переполнения или еще какие-то тупые баги.
Задача D(Метро)
 Найдем цикл (например обходом в глубину, Ссылка, еще нужно не забыть что граф неориентированный, и ходить в предка нельзя). Добавим эти вершины в очередь, и пометим расстояние до них как 0, потом запустим обычный волновой алгоритм и получим ответ.
 Посчитаем для каждого ферзя, угрожает-ли он кому-то в каждом направлении. Как это сделать:
Ответы по горизонтали: сортим по X, идем слева на право, если уже встречалась раньше, вершина с таким Y, то ответ для ферзя +1, ну и еще нужно пометить что такой У уже встретился. Аналогично сделаем с проходом с права на лева. 
Для ответов по горизонтали, все так-же, просто меняем местами X и Y во всех местах.
Остались диагонали: каждая диагональ может относиться к двум видам, первый однозначно задается как X+Y, второй как X-Y, то есть снова сортируем все по X, делаем два прохода, слева на право и наоборот, только в данном случае считаем встречались/нет не X, а значение диагонали.
Задача F(Подарок маме)
 Определим где есть и где нету звезд, если она есть то в ячейке матрицы будет 1, иначе 0. Посчитаем частичные суммы таких прямоугольников. Дальше зафиксируем левую и правую границы прямоугольника, а дальше будет идти с двумя указателями, смещать первый вниз и двигать второй вниз пока между ними кол-во звезд больше-равно К. Кол-во звезд в прямоугольнике можно посчитать через частичные суммы: пускай координаты прямоугольника будут (x1,y1,x2,y2), а частичные суммы для позиции (i,j) будут лежать ячейке a[i,j], тогда ответом будет a[x2-1,y2-1]-a[x2-1,y1]-a[x1,y2-1]+a[x1,y1], так-как границы мы не можем включать в ответ. Теперь допустим в какой-то момент левая граница равна l(l = 0, если еще даже взяв все не получим сумму в К), то к ответу нужно прибавить это-же l, то-есть все не меньшие прямоугольники.


Разбор задач Codeforces Beta Round 95 (Div. 2)
  • Проголосовать: нравится
  • +38
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Несколько замечаний по разбору:
-Разбор приводится для всех участников, поэтому про задачу A можно расписать, какими функциями можно воспользоваться ( например tolower(), toupper() в с++).
-Про задачу С. Одна из фишек в задаче - правильно посчитать C(N,k) (т.е. количество сочетаний из N по k) не вылезая за пределы типа. Я делал очень криво, сокращая каждый раз на nod(fact,k), и хотел бы услышать более оптимальное решение.
-Задача D. Хотелось бы услышать более подробное описания алгоритма поиска цикла на почти-дереве. Я нашел интересные в коде, но перебирать все решения не хотелось бы.
  • 13 лет назад, # ^ |
      Проголосовать: нравится -12 Проголосовать: не нравится
    В задаче С можно было считать C(N,k) квадратной динамикой, либо при подсчете факториала за один шаг и делить и умножать - это позволит избежать переполнения.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Об задаче C.
    Я решал динамикой:
    C[i][j] = C[i-1][j] + C[i-1][j-1];
    Об етом можна прочитать на википедии об биноминальніх коефициентах.

    Об задаче D. Цикл легко находиться посколько он всегла один. Мой способ:
    Пускаем DFS. Если ми попадаем в вершину в которой уже біли то значит нашли цикл и рекурсивно возвращаемся к нему.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Разбор на то и разбор, что он объясняет идеи, которые нужно было использовать для решения задач, в Delfi и Pascal, например, нет функций toLowerCase() и toUpperCase(), дык и зачем тогда о них  вообще говорить. Тем более задача простейшая (хоть кто-то условие с первого раза и не смог нормально понять -_-').

    В задаче C я считал все через BigInteger, считаю свое решение ужасным и предпочел бы сказать, что оно не мое, но на контесте ничего более доходчивого не пришло на ум. А что должно было придти - открываем Википедию и читаем: "В общем случае число, показывающее, сколькими способами можно выбрать k элементов из множества, содержащего n различных элементов, стоит на пересечении k-й диагонали и n-й строки треугольника Паскаля." Вот и все дела, собственно.

    А в D, не знаю, как надо было, но я искал цикл алгоритмом окрашиваний вершин, как он точно называется не знаю, но суть в этом. Жаль, не успел сдать, какая-то непонятная ошибка атаковала код, из-за чего он выдавал неверный ответ..
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    "Про задачу С."
    Ну, не проблема, наверное, записать C(N,k)=(N(N-1)(N-2)...(n-k+1))/(1*2*...k).
    Произведение t последовательных чисел делится на t!, так что можно просто последовательно умножать на n-k+1, делить на 1, умножать на n-k+2, делить на 2, умножать на n-k+3, делить на 3 и т. д.
    Как  легко оценить, в тип влезает.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ну, или через треугольник, да.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Вот и хотелось услышать про треугольник. А я делал с умножением и делением на nod().
      Если бы не забыл поставить одно условие, то решение зашло.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Я к тому, что НОД при этом решении искать не нужно.
        Произведение последовательных чисел заведомо делится на факориал их количества.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Хотя, конечно, классическим является решение с треугольником.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Как уже сказали не во всех языках есть такие функции, написал как это можно сделать в любом языке.
    По поводу цикла и биномиальных коэффициентов можно прочитать на все известном e-maxx.ru/algo.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    не особ здесь toupper и поможет, все равно ручками проверять первую буквуа уже можно но старым дедовским методом +'a'-'A'
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Задача А.
Полагаю, опечатка:
"если есть хоть одна строчная буква не считая первую".
Наверное, подразумевалось:
"если есть хоть одна прописная буква не считая первую"
Хотя вряд ли кто-то вообще внимательно читает решение задач А...
  • 13 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    Да, вы правы.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Меня B поставила в ступор, минуты 3 не мог понять, почему в первом тесте пара (1;3) шла в ответ, думал, что я вообще не соображаю, раз не могу понять условии, и ушел сразу на C. Потом уже прилетела мессага об ошибке..
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А я в B поспешил и не глянув ограничения тупой квадрат написал и сдал: "Поспешишь - людей насмешишь"
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да вроде всё правильно...
    cApS
    p-строчная - строку оставляем.
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Насчет задачи D и нахождения цикла... собственно искал методом, который указан в разборе и получалось, что цикл 1 - 3.

У нас же есть петли (1 - 3, 3 - 1) вот и цикл.
На этом ступорнул очень... так как корректно решить этим методом? Решения не хочу смотреть пока.

Спасибо.


  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Так вроде-бы кратные ребра не существуют, или я не понял ваш вопрос?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Например при dfs'e не ходить в ту вершину, из которой только что пришли, 
    e.g. dfs(int v,int parent){..}
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Алгоритм по ссылке для орграфа.
    Чтобы стало работать с обычными нужно запретить ходить в предка.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      По ссылке рассмотрен случай неориентированного графа.
      • 13 лет назад, # ^ |
          Проголосовать: нравится -20 Проголосовать: не нравится

        Реализация

        Здесь приведена реализация для случая ориентированного графа.

      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Думаю стоит отметить эту особенность в разборе.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          "например обходом в глубину, Ссылка, еще нужно не забыть что граф неориентированный, и ходить в предка нельзя"
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

"Дальше зафиксируем левую и правую границы прямоугольника, а дальше будет идти с двумя указателями, смещать первый вниз и двигать второй вниз пока между ними кол-во звезд больше-равно К." - можно немного поподробнее, заранее спасибо.

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

    Можно сделать также как и с левой/правой границей - перебрать все верхние/нижние границы, т.е. получится полный перебор прямоугольников, что будет работать, но не уложится в TL... Будем оптимизировать наш brute force:

    1. Можно заметить, что если мы нашли удовлетворяющий условию прямоугольник, то все большие тоже нам подойдут. Потому нет смысла проходить самый вложенный цикл всегда до конца — если нашли прямоугольник с количеством звёзд >=k, то количество оставшихся итераций можно просто прибавить, не выполняя их. Это не повлияет на ответ.

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

    Т.о. мы получили решение типа «два указателя», что и описано у ув. Sereja.