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

Автор HolkinPV, 12 лет назад, По-русски

195A - Посмотрим футбол

Полное видео скачается через all = (c·a + b - 1) / b секунд. В этой задаче можно было перебрать величину ответа 1 <  = t <  = all. Чтобы удовлетворить условию задачи, достаточно проверить, что в последний момент времени t0 = all выполняется условие, написанное в тексте задачи, а именно tb >  = (t0 - ta.

195B - После тренировки

В этой задаче нужно было аккуратно реализовать описанный в условии процесс. Вначале заметим, что мяч с номером i > m попадет в одну корзину с мячом под номером i - m. Поэтому достаточно распределить первые m мячей. Это удобно сделать при помощи двух указателей lf, rg, начиная с середины. Поочередно кладем мяч сначала слева, затем справа и двигаем указатели. Единственный раз, когда нужно дважды подвинуть левый указателей, возникает в самый первый момент, если m нечетно.

195C - Попробуй поймай

Данная задача носила реализационный характер. В своем решении я поступал следующим образом. Удалим из текста все пробелы, кроме пробелов в сообщениях try-catch блоков. Затем при появлении слова try, кладем номер нового try-catch блока в стек. При появлени слова throw, запомним его тип, а также текущее состояние стека (то есть какие try-catch блоки открыты). Для этого, например, положим номера открытых блоков в set. При появлении слова catch, если тип блока совпадает с типом оператора throw, а также номер текущего блока находился в стеке при появлении оператора throw (то есть он есть в нашем set-е), то сразу выводим ответ. Иначе удаляем текущий try-catch блок из стека. Если подходящего try-catch блока так и не найдется, в конце выводим фразу "Unhandled Exception".

195D - Исследование ломаной

Разбор от автора Igor_Kudryashov

В данной задаче были заданы по сути прямые в виде yi = ki * x + bi, но в тех точках, где y принимает отрицательное значение, оно заменено нулем. Необходимо было найти количество углов, не равных 180 градусам, в графике функции, равной сумме функций указанного вида.

Во-первых, несложно показать, что сумма прямых является прямой. В самом деле, если y = y1 + y2, то y = k1 * x + b1 + k2 * x + b2 = (k1 + k2) * x + (b1 + b2). Рассмотрим точки, в которых yi = 0, т.е. xi =  - bi / ki. Пока предположим, что ki не равно 0. Тогда i-ая функция разбивается на две прямые, одна из которых тождественно равна 0. Оставим среди xi различные точки и упорядочим их по возрастанию значения. Тогда, очевидно, между двумя соседними точками суммой заданных функций является прямая. Найдем уравнение этой прямой. Предположим, мы рассматриваем i-ую слева точку. Тогда если уравнение прямой между i-ой и (i + 1)-ой точками, отлично от уравнения прямой между (i - 1)-ой и i-ой точками, тогда в i-ой точке образуется угол, не равный 180 градусам.

Таким образом, нам необходимо найти уравнение прямых на отрезках между соседними точками x, т.е. найти коэффициенты k и b. Это можно легко сделать с использованием 2 массивов запросами увеличения на отрезке в оффлайне.

Когда мы обрабатываем очередную функцию, мы смотрим, если ki равно 0, то нужно ко всем отрезкам прибавить одну и ту же величину, но т.к. данное изменение не повлияет на ответ, то можно не обрабатывать функции такого вида. Если ki не равно 0, то найдем индекс j точки xi в упорядоченном списке x. Теперь если ki больше 0, то нужно сделать увеличение на суффиксе, начиная с позиции j, иначе нужно сделать увеличение на префиксе до позиции j (при этом увеличение на префиксе коэффициента k будет производиться на отрицательную величину).

195E - Построение леса

Разбор от автора Fefer_Ivan

В этой задаче самой долгой операцией является поиск корня вершины и длина пути до него. Эту операцию можно выполнять быстро используя эвристику сжатия путей. Такой же метод применяется в структуре данных Disjoint Set Union.

Для каждой вершины v мы будем хранить два числа: c[v] и sum[v]. c[v] = v, если v — корень, иначе c[v] — следующая вершина на пути от v к корню. sum[v] = сумме длин ребер на пути от v до c[v].

Таким образом для того, чтобы добавить ребро из u в v веса w, достаточно c[u] = v, а sum[u] = w. Теперь мы можем за O(n) находить по вершине нужные нам в задаче root(v) и depth(v) просто переходя каждый раз из v в c[v] и суммируя все sum[v] по пути.

Заметим, что мы только добавляем ребра, но не удаляем. Это значит, что если мы для вершины v нашли root(v) и depth(v), то можно присвоить c[v] = root(v), sum[v] = depth(v). Таким образом в следующий раз мы найдем предка вершины v за О(1). В общем реализация этого подхода выглядит следующим образом:

int root(int v){  
   if(c[v] == v){  
       return v;  
   }else{  
       int u = root(c[v]);  
       sum[v] = (sum[c[v]] + sum[v]) % M;  
       c[v] = u;  
       return u;  
   }  
}  

Доказывается, что такая реализация работает в сумме за время, пропроциональное обратной фунции Аккермана http://en.wikipedia.org/wiki/Ackermann_function#Inverse) на запрос при применении ранговой эвристики. Поскольку в этом случае нельзя её применить, то такой запрос обрабатывается за log(n). Итого получаем решение за время O(n * log * (n)).

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

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Альтернативное решение по B: Заметим, что у нас в задаче определен оператор сравнения чисел от 1 до m. Положим их все в вектор a и отсортуруем по этому оператору.

А дальше просто:


for(int i = 0; i < n; ++i) printf("%d", a[i % m]);
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

В C еще можно было идти по блокам в обратном порядке, если команда catch — добавим в стек, если try — достанем из стека соответствующий catch, если throw — ответ — первый в стеке подходящий catch или Unhandled exception, если такого не нашлось.

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Что-то у меня сильно проще решение по D. В массив записываем все числа вида -(b / k), где k != 0, сортируем, ищем количество разных чисел.

»
12 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

На самом деле в D достаточно найти количество различных точек в которых прямые пересекают ось ОХ.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    я так и делаю, но у меня ошибка на 52м тесте. не подскажете, в чем проблема? код:

    int main() { int n; cin >> n; set points; long long k, b; for (int i = 0; i < n; ++i) { cin >> k >> b; if (k == 0) { continue; } points.insert((-b + .0) / k); } cout << points.size() << endl; }

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      мб, ошибка сравнения чисел с плавающей точкой?

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      set какой? float? тогда дело в этом наверное. деление для плавающей точки не такое уж и точное, видимо где-то не совпало.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        сет double, но ответ сильно отличаеться, от нужного

        Вывод 21 Ответ 111

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Если заменить double на long double и соответственно послать под gcc то такое заходит.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Я на всякий случай сравнивал не даблы а сделал сет пар, где пара — несократимая дробь

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

в D можно попроще

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

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

Тоесть, нужно просто посчитать количество несовпадающих изломов добавленных двухзвенных ломанных. Координата излома = -b/k, очень быстро программа пишется на ruby с использованием класса для рац. дробей.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Ахах, все уже отписались. Ну пусть будет поподробнее)

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Точки изломов не пропадают, т.к. производная будет кусочно - постоянной неубывающей функцией с точками разрыва = -b/k. (с точки зрения математика)
»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Здесь, наскольно я понял, в задаче E описана только эвристика сжатия пути в DSU, но без обьединения по рангу. Разве такая реализация работает за время пропроциональное обратной фунции Аккермана или все-же за логарифм, как было доказано тут?

UPD. Или все-таки я что-то неправильно понял?

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

По C можно гораздо проще, без стеков и сетов, просто с одним счетчиком (т.к. программа гарантированно правильная).

Все, что до throw, можно игнорировать, потом считать количество встреченных try (чтобы пропустить такое же количество catch). Вывести первый непропущенный catch с совпадающим типом исключения, или Unhandled Exception.

См., например, 1779055 или 1778103.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

A в одну строку: cout << ceil((a*c-b*c)/b);

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    В этой задаче такое заходило, но в общем случае безопаснее делать округление частного вверх целочисленно: ceil(a/b) = (a+b-1) div b.

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

По задаче B можно предложить еще одно решение. Для каждого i-го мяча (1 <= i <= n) делать следующее: если числа (i — 1) mod m и m разной четности, то i-ый мяч класть в корзину с номером (m + (i — 1) mod m + 1) div 2; иначе i-ый мяч класть в корзину с номером (m — (i — 1) mod m) div 2.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

http://mirror.codeforces.com/contest/195/submission/1784693 можете посмотреть почему TL? ведь сортирую бысро

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    В сортировке у вас написано x = a[l + random(l+r-1)]. Но l+random(l+r-1) может получится больше r, т.е элемент разделитель получится больше любого числа из интервала a[l..r], поэтому такой разделитель неудачный. Неудачных разделителей у вас получится довольно много и сортировка будет работать за O(n^2).

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      random(r+l-1) получает больше r, и мы уже не в отрезке [l,r], а значит она вообще не правильная. я только удивляюсь, как она вообще дошла до 10 теста, и раньше не упала!!!

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

    Често говоря, это новый вид сортировки. Ты сортируешь не правильно. Потом eps надо уменьшить, и ты не рассматривал случий когда ответ 0!!!!

    Вот 1785948 исправил!!!

    Про eps спасибо sdryapko !

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      eps надо уменьшить :)...0.0000000000000000001<0.000000001 :)

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        откуда берется эта константа?

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          просто привел пример, что человек немного неправильно выразился. А вообще, ИМХО, эту задачу стоило решать в целых числах.

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Откуда берется эта константа не представляю, мне лень считать количество 0.

          Оценим разность велечин . Можно добиться, чтобы числитель был 1, а знаменатель незначительно меньше 1018.