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

Автор vovuh, история, 9 лет назад, По-русски

567A - Почта в Лайнландии

Можно сделать очевидный вывод — наибольшей стоимостью отправки письма из i-го города будет являться максимум из расстояний от i-го города до первого и от i-го города до последнего (max(abs(xi - x0), abs(xi - xn - 1)). А минимальной стоимостью отправки будет являться минимум из расстояний до соседних городов (для i-го города соседними являются города с номерами i - 1 и i + 1), то есть (min(abs(xi - xi - 1), abs(xi - xi + 1)). Для всех городов, кроме самого левого и самого правого, это считается нормально. Так как у самого левого нет соседей левее, значит минимальная стоимость определяются однозначно (abs(xi - xi + 1)). Аналогично для самого правого города (abs(xi - xi - 1)).

Авторское решение

567B - Берляндская национальная библиотека

Чтобы корректно обрабатывать события, нам необходимо знать, находится ли в библиотеке на данный момент человек. Для этого будем использовать массив in типа bool. Также заведём две переменные для хранения ответа и "текущего состояния" (в которой будет храниться количество человек, присутствующих в библиотеке на данный момент). Их обозначим ans и state соответственнно.

Итак, если к нам поступает запрос вида " + ai", то мы увеличиваем state на единицу, отмечаем, что этот человек зашёл в читальный зал (in[ai] = true) и пытаемся обновить ответ (ans = max(ans, state)).

Иначе же к нам поступает запрос вида " - ai". В данном случае если человек, который выходит из библиотеки, находился в ней, то нам просто нужно уменьшить state. Иначе мы понимаем, что если этого человека "не было" в библиотеке (in[ai] == false) и он выходит, значит он был в читальном зале ещё до начала рассматриваемого нами промежутка времени. Тогда мы в любом случае должны увеличить ответ на единицу. Также не стоит забывать, что необходимо отметить, что человек вышел из библиотеки (in[ai] = false).

Авторское решение

567C - Геометрическая прогрессия

Давайте будем решать эту задачу относительно фиксированного среднего элемента. Это значит, что если мы фиксируем элемент ai, то наша прогрессия должна состоять из элементов вида ai / k, ai, ai·k. Заметим, что прогрессии со средним элементом ai не будет существовать, когда ai не делится нацело на k ().

При фиксированном среднем члене мы сможем отвечать на запрос вида "сколько существует подпоследовательностей — геометрических прогрессий, средний элемент которых стоит строго в позиции i". Очевидно, что это будет количество элементов слева от i-го, равных ai / k, умноженное на количество элементов, находящихся справа от i-го, равных ai·k. То есть мы можем отвечать на этот вопрос для каждого элемента, если будем знать количества элементов слева и справа от i-го. Для этого можно использовать ассоциативный массив (map). Будем хранить 2 map-a l и r, в l будем поддерживать все элементы строго левее i-го, а в r — строго правее i-го. Если идти по массиву слева направо, то l должен быть пустым, а в r должны быть все элементы. Пройдём циклом по всему изначальному массиву, постепенно обновляя map-ы (очевидно, что перед рассмотрением i-го элемента мы должны удалить его из r, а после рассмотрения — добавить его в l). Если ai будет делиться нацело на k, то добавляем к ответу l[ai / k] * r[ai * k] (стоит заметить, что как при перемножении, так и при обновлении ответа могут случаться переполнения типа int, поэтому проще всего все переменные хранить в long long).

Авторское решение

567D - Одномерный морской бой

Сначала нам необходимо понять, в каком случае мы можем утверждать, что Алиса соврала. Это случится, когда на поле размера n невозможно будет уместить k кораблей размера a. Для отрезка фиксированной длины len мы можем посчитать максимальное количество кораблей размера a, которые могут уместиться на таком поле. Каждый корабль занимает ровно a + 1 клетку, кроме одного крайнего. Поэтому для отрезка длины len формула для подсчёта будет выглядеть так: (чтобы не учитывать корабль, который занимает a клеток, а не a + 1, мы просто добавим одну <<фиктивную>> клетку в наш отрезок). Значит, для отрезка [l..r] наша формула должна выглядеть так: .

Для решения задачи нам надо хранить все отрезки [l..r], внутри которых все клетки "свободны" (то есть ни в одну из клеток отрезка не было произведено выстрела). Для удобства их можно хранить в множестве (std: : set), чтобы можно было легко найти нужный отрезок. Итак, будем обрабатывать выстрелы по очереди. Изначально количесво помещающихся кораблей будет равняться (это значит, что у нас есть один отрезок [1..n]). После каждого выстрела один из отрезков будет либо делиться на два отрезка меньшего размера, либо он будет просто уменьшаться в размере на единицу (если выстрел будет произведён в его край). Таким образом, если выстрел произведён в точку x, относящуюся к отрезку [l..r], то мы должны вычесть из нашего общего количества кораблей их количество на отрезке [l..r], удалить этот отрезок из множества и разделить его на два новых: [l..x - 1] и [x + 1..r] (если выстрел был произведён в край отрезка, тогда добавляется только один новый отрезок) и прибавить к количеству и (соответственно, если появляется только один новый отрезок, то необходимо прибавить только одну величину).

Если после обработки какого-то из выстрелов количество кораблей стало меньше, чем k, то это означает, что Алиса соврала нам, выводим номер этого хода. Если же после обработки всех выстрелов количество кораблей так и осталось не меньше, чем k, выводим  - 1.

Авторское решение

567E - Президент и дороги

Сначала давайте разберёмся, какие рёбра не будут лежать ни на одном кратчайшем пути из s в t. Если запустить два алгоритма поиска кратчайших путей (из вершины s и из вершины t) и сохранить расстояния в массивах d1 и d2 соответственно, можно сделать следующий вывод: если у нас есть ребро (u, v), то оно будет лежать хотя бы на одном кратчайшем пути из s в t тогда и только тогда, когда d1[u] + w(u, v) + d2[v] == d1[t] (где w(u, v) — вес ребра (u, v)).

После того, как мы построили граф кратчайших путей из s в t, мы можем определить, какие из рёбер лежат на всех кратчайших путях. Если представить путь из s в t в виде отрезка [0..D], а расстояния между парами вершин, соединённых рёбрами в этом графе, в виде подотрезков данного отрезка (например, если у нас есть ребро (u, v), тогда данный подотрезок будет иметь вид [d1[u]..d1[v]]), то можно заметить, что все подотрезки каким-то образом касаются других подотрезков (некоторые также могут пересекаться с другими подотрезками). Ребро (u, v) будет лежать на всех кратчайших путях из s в t, если подотрезок [d1[u]..d1[v]] будет только касаться других подотрезков (внутренние пересечения с другими подотрезками недопустимы). Теперь мы можем однозначно отвечать "YES" для этих рёбер.

Остальная часть задачи более простая. Если ребро (u, v) с весом w не лежит на всех кратчайших путях, можно попробовать уменьшить его. Данное ребро будет лежать на всех кратчайших путях только в том случае, если его вес станет равен d1[t] - d1[u] - d2[v] - 1. Итак, если величина d1[t] - d1[u] - d2[v] - 1 (предполагаемый новый вес нашего ребра)строго положительна, тогда мы сможем уменьшить наше ребро так, чтобы оно лежало на всех кратчайших путях, выведем "CAN" и через пробел разность между старым и новым весами ребра. Иначе же выведем "NO".

Авторское решение

567F - Мавзолей

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

Очевидно, вышеописанным способом строится любая корректная последовательность. Попробуем посмотреть на требования к высотам блоков со стороны такого способа построения последовательности. Поскольку блоки мы выставляем в порядке возрастания высот, то неравенства теперь ставят ограничения только на порядок расстановки блоков. Например, требование ''3 >= 5'' теперь означает, что ставить блок в позицию 3 мы можем только лишь если блок в позиции 5 уже поставлен (а значит он имеет меньшую высоту), или же в позициях 3 и 5 блоки нужно ставить одновременно (пара блоков одной высоты).

Для дальнейшего подсчета количества способов воспользуемся идеей динамического программирования. Будем считать dp[l][r] — количество способов поставить блоки, если свободные от блоков места образуют отрезок [l, r]. Высота пары блоков, которая будет ставится в крайние места отрезка однозначно определяется границами этого отрезка. Переберем один из трех вариантов расстановки очередной пары блоков (исключение составляет случай l =  = r + 1). Теперь проверим, что такая расстановка не нарушает требования условия задачи. Будем рассматривать только ограничения, касающиеся позиций, на которые ставятся блоки в фиксированном варианте. Для любой "текущей" позиции должно выполняться "<" для любого еще не занятого места (которое находится внутри отрезка [l, r], но не совпадает с одним из двух "текущих" мест), ">" для любого занятого места (вне [l, r]), а ''='' выполняться только в случае сравнения двух "текущих" мест.

Такое динамическое программирование проще всего считать рекурсивно, "ленивой" динамикой.

Авторское решение

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

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

Can you please provide me test case 61 or help me with this submission getting WA. http://codeforces.com/contest/567/submission/12359031

ct map stores count of numbers from right to left, mapp stores count of x and x * k in right. I changed the order of updating of mapp, ct and ans and got AC. http://codeforces.com/contest/567/submission/12377229

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

    in last cycle ans += mapp[ar[i] * k]; must be first line, else if ar[i]*k == ar[i] you crushing logic of solution. This is possible not only k = 1, this is possible if ar[i] = 0. You can see test#61 is it.

    P.S. after this correction there is no need to separate case k = 1.

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

I spent about one hour trying to find a smart solution to problem B and I failed during the contest. But after the contest ended (of course), I found a beautiful idea. I use a map and a deque. The map is used to verify if a person has already been encountered. The deque keeps track for the "events". When a new "event" occurs it is tested: if ( — x ) is encountered and x doesn't belong to the map we will push_back the (- x) event and push_front the ( + x ) event. For all other cases ( +/- x ) is pushed_back. After that, the deque will be scanned, + increases the current nr and — decreases it. The maximum value for nr is saved and finally printed. I hope this beautiful solution will solve the problem forever.

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

В задаче Е претесты даже не проверяют того, что участник не заметил, что граф ориентированный. Зачем так делать?

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

I solved problem C using DP... let dp[i][j] = the number of geometric progression with common ratio k starting from index i and with length j. now of course dp [i][1]=1. dp[i][j]=sum(dp[v][j-1]) where (v>i and a[v]=k*a[i]). one can use map to do this. the answer will be sum(dp[i][3]) where 1<= i <=n

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

Не могу понять, как в задаче 567D - Одномерный морской бой искать отрезок, которому принадлежит подбитая клетка, использую set?

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

    Через upper_bound/lower_bound.

    Есть сет интервалов, стреляешь в клетку x. Как узнаем, какому интервалу он принадлежит? Ищем первый интервал, гарантированно больший (x x). Это есть операция upper_bound. Что дальше? Мы нашли какой-то отрезок (l r). Возможны случаи: 1) это несуществующий отрезок; 2) l > x; 3) l = x. В первом случае поскольку гарантируется, что такой отрезок существует, то искомый отрезок — последний. Во втором случае искомый отрезок — отрезок, идущий перед (l r). А в третьем — сам отрезок (l r) является искомым.

    Как-то так.

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

      Большое спасибо за развёрнутый ответ.

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

        Вообще говоря, на этапе, когда делаешь insert в set, результат выполнения этой функции — это пара {iterator, bool}. Булевый параметр даётся, чтобы можно было понять, вставился элемент в сет (значение true) или он уже там был (значение false). Соответственно, оптимально было бы выдернуть из этой пары итератор и уже от него отталкиваться. Но написать upper_bound() тупо проще, а уж разница между O(1) и O(logN) не настолько велика, чтобы вызвать таймлимит :)

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

          Вообще-то тут разница не в O(1) и O(logN), а в O(С1*logN) и O(C2*logN). Ведь в любом случае нужно делать insert...

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

    Проще всего хранить в сете пару (r, l) и при проверке клетки x брать lower_bound(make_pair(x, -1)). Скоро выложу авторские решения для лучшего понимания.

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

My solution for D is quite similar to described above, however it have got TL. I tried to store intervals in simple ArrayList and had to loop over it for every move to find the interval where target cell belongs. This approach is probably cause of TL. I saw solutions with TreeSet and some others, but i want to ask about my approach. Is there way to store my Intervals somehow to make access faster and avoid TL? http://codeforces.com/contest/567/submission/12377419

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

    Instead of doing a linear search to find your interval, because of the way the set of intervals is structured(a number cant be in more than 1 interval) you can binary search for your desired interval.

    But for these sorts of problems, c++ is much much MUCH better. You almost never need extra optimizations,intervals can be represented as pairs, and the set will automatically sort the pairs without any comparators needed. You can use the set::upper_bound function to find the desired interval(1 line of code whereas you would need to binary search, taking many more lines of code).

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

В задаче С — ошибка в тестах: 0 не может быть элементом геометрической прогрессии — по определению.

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

    В данной задаче дано своё определение геометрической прогрессии, никакой ошибки нет.

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

How to apply binary search to problem C?, please.

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

    By using map. In fact it's already a data structure with the time complexity O(logN)

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

      Python's dict and C++'s STL unordered_map (I think) are O(1).

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

        Wow. Can you give a further explanation?

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

        std::unordered_map is not "ordered" (ie. you cannot do binary search on it).

        On top of that, std::unordered_map is really, really slow (faster than std::map though). I suggest not to think of it as O(1).

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

        It is O(1) on average, but O(n) at worst. For map it is always at worst.

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

          In practice, it is too difficult to construct a test case that can significantly slowdown an unordered_map.

          On codeforces, I see that the unordered_map provides at least 2 times better performance than just a map.

          Even at worst case, you can play with max_load_factor and hash function.

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

            This is all true, but you shouldn't view hash tables as a "magical bullet", the O(n) worst case can still strike. One needs to be aware of this.

            I have encountered this on CF once: I used unordered_map<int, int> as usual (with .reserve() too) and received unexpected TLE. After eliminating other factors, I changed the code to map<int, int> — and the solution passed.

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

    I am the one who added "sortings" and "binary search" tags to C.

    The top-level idea is to enumerate the middle point (call it a[i]),
    then count the total number of a[i] / k (before i) and a[i] * k (after i).
    To do this,

    1. Represent a number in the sequence by (a[i], i) and sort the sequence. You would get something like (1, 0) (1, 3) (2, 1) (5, 2) (5, 4) (7, 5) for a sorted sequence.
    2. To find out how many a[i] / k lies in the sequence, do 2 binary searches using (a[i] / k, 0) and (a[i] / k, i). Let this number be m1.
    3. To find out how many a[i] * k lies in the sequence, do 2 binary searches using (a[i] * k, i) and (a[i] * k, INF). Let this number be m2.
    4. ans = ans + m1 * m2

    Implementation

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

    12584852

    Please ignore my ugly implementation as I am trying to get used to C++11...

    But my concept is just do binary search on a vector<pair<int,int>>, no special data structure is needed :)

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

For problem D, simply use a map structure to record the free space (a consecutive empty square without shotpoint) on a shotpoint's left and right.

You can use the lower_bound and upper_bound functions (of map/set [IMPORTANT]) to find the nearest shotpoint, and update them.

When a shot happens a free space will be broken into 2, so calculate the sum of max number of ships of those 2 spaces and subtract it from the global sum of max number of ships.

Calculate the maximum number of ships could be placed in the space: (space+1)/(a+1)

(global sum of max number of ships = (n+1)/(a+1) before the 1st shot.)

when the global sum < k just print the current operation number and exit.

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

    With exact same code I am getting TLE : http://codeforces.com/contest/567/submission/12382269

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

      std::lower_bound is O(logn) if and only if you search above container with random-access iterators (you can for O(1) get any item: vector, array) and container is sorted.

      Set has bidirectional iterator (you can for O(1) get only previous and next items) so std::lower_bound is O(n).

      To get complexity O(logn) you need std::set::lower_bound. It is O(logn) in worst-case.

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

Another solution for D which works in O((m + ndsu): 12380878

Just process all shots in reverse order.

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

Can you give us an estimate on when the rest of the editorial will be posted?

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

Can anybody help me check my code of problem E: http://codeforces.com/contest/567/submission/12382102

Thanks!

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

Разбор збс. В основном они отстойные, но здесь все понятно. Спасибо!

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

I got WA in Problem D(i used binary search+Segment tree),i cannot understand where is my wrong.. here is my code http://codeforces.com/contest/567/submission/12385432

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

    The ships cannot touch each other.

    You didn't count it here. c+=(arr[i]-(a))/A; c+=(b-(arr[i]+2))/A; total=total-(t/A)+c;

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

OMG!!!

i had understood the problem C wrongly and it was so hard! but when i understand the corret form of problem i get AC in 10 mins! is it fair that i didn't go to div 1 for my bad English???? is it?

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

can anyone help me with some ideas about problem D ?

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

    You can use binary search : try to put the first (l+r)/2 points and k recetangles without overlapping. If it is possible you try for greater value else you try for smaller. How you check if it is possible: Iterate over all point and check how many recentagles at most you can put between point i and point i+1. Also you should check how many recetangles you can put between 1 and a[1] and a[(l+r)/2] and n.

    The second solution: You can use dsu or set. Start from behind and check if it is possible to put k recetangles when you have the first i points if it isn't possible you merge intervals [left andjacent point, a[i]] and [a[i],right adjacent point] and check it again.

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

      in the first approach , do you mean by a[i] the "shot" number i ??

      if it's the case , I don't agree with ,because "shots" are not given sorted by their position

      thanks!

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

      you don't need to start from behind, just check the decrease of the max number of ship it can place when a shot happens (it's nlgn)

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

      Can you please make me understand where is my solution wrong? Solution I cannot understand why my checker function is wrong??

      I have spent a lot of time and I still cannot understand why this F function works Sol2

      Actually what I am doing is putting the rectangles of length A between the positions.

      Please help ! I am trying since yesterday!

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

        A lot people were talking about it. You should divide with a+1 in check function ( reason- two ships can't touch each other ).

        About F, I didn't read it, but also I don't believe I can help you... I am not on level to understand every solution for some F problem :)

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

      The solution in details is to do a binary search against the array of moves — to find the first move, when it becomes impossible to put m ships on the board. As far as I see — this approach was used by the majority of div1 participants. Makes sense, as it is simple and now complex structures are needed at all.

      So we have to write a function F(p), which returns whether it is possible to place the ships for a situation after move with number "p" .

      The initialization step is to check F(m). If it is "true", then our result is immediately "-1". I.e. after "m" moves we are still able to place all the ships on the board.

      We don't need to check the start of the moves, as according to the problem statement, initially it is possible to place the ships there.

      And so we start the main loop to perform half-division search over moves. The initial interval to check is from 1 to "m". During every iteration we calculate F( (l + r) / 2 ). If it is positive, then out solution is somewhere in the right half of the current interval. If it is negative, then the solution is in the left half of the current interval. And so on.

      The binary search is O(logN). The quite simple F is O(N). Thus the general time complexity is O(N * logN).

      I like submission 12361499, where the concept is shown quite well.

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

      My O(nlognlogn) solution got TLE. :/

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

Since E and F editorials aren't up yet, could anyone explain the approach?

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

    Problem E

    Problem F

    I think Problem E needs more explanation.
    In case you don't understand the discussion, reply below and I'll explain :)
    It needs some graph theory facts.

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

      PLease explain Problem E. I have been struggling hard since an hour to understand the editorial

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

        I have explained his ideas in my other comment below.

        My solution is based on this fact (This should be easier if you have some graph theory knowledge):

        An edge exists in all shortest paths iff. it is a bridge in the shortest path graph

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

    Very nice problems, vovuh, especially C, E and F which I liked very much, looking forward to your next round! :)

    For E, let dist_s[i] be the distance from s to i and cnt_s[i] be the number of shortest paths from s to i. These values can be computed using Dijkstra's algorithm, check my submission for more details. Then, let dist_t[i] be the distance from i to t and cnt_t[i] be the number of shortest paths from i to t. Those values can be computed by reversing the edges and running Dijkstra's algorithm from t.

    After that, there are some cases to be considered for each edge (from[i], to[i], length[i]), let's assume that shortest is the distance between s and t, which is dist_s[t] and dist_t[s] and current is equal to the current length which is length[i]+dist_s[from[i]]+dist_t[to[i]]:

    1) If current is equal to shortest, then the edge will be used for sure only if all shortest paths from s to t pass through this edge. So if cnt_s[t] is equal to cnt_s[from[i]]*cnt_t[to[i]], then the answer is YES. Otherwise, we need to decrease it's length by 1, so if length[i]>1, then the answer is CAN 1. Otherwise, the answer is NO.

    2) If current is greater than shortest, then we need to make current equal to shortest-1 so if current-(shortest-1)<length[i], then the answer is CAN (current-(shortest-1)). Otherwise, the answer is NO.

    Note that the cnt_s and cnt_t values may be really really big so in the topic I read about taking them modulo some number, and maybe taking them modulo two different numbers is a better idea, it makes the chance of collision lower. By the way, when I used 10^9+7 as MOD, I got WA and when I changed it, the verdict became accepted. However, I doubt the author solution uses MOD so it will be good to see it soon.

    For F the best I found is this comment by Errichtohttp://codeforces.com/blog/entry/19590?#comment-244086

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

      can anyone helps me in Problem E ... i think my approach is right but im getting a WA on case 37 : 12402935 any help is appreciated :)

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

      Am I supposed to do Dijkstra with priority queue? I get TLE on the first test case with N=100000 & M=100000 otherwise.

      [submission:1000776999]

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

        Yes.

        I took a look. Your submission runs in O(V2).
        Reason: V Extract-Min & Relaxations, and Each iteration runs in O(V)
        => V * O(V) = O(V2)

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

Tried solving the C problem using two binary searches per index for find the number of terms a/k on left and a*k on the right. Ofcourse over a sorted sequence of the input data, sorted by size then by id if values are equal. Wondering why it timed out. http://codeforces.com/contest/567/submission/12399316

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

Oh btw I really enjoyed the problemset.

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

    later possible any means for example 2 hours later , 2 months later , 2 years later and 2 centuries and now what do you think?

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

Thanks for upd!

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

can any body help please, what is the bug in my solution for E ,does number of ways fit in long long? here

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

    No. The number of ways can be something like 250000.

    The more correct way to do this is to module the number by one or several(just to be safe) big prime number(s). This is still incorrect nonetheless, but has a very small error rate.

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

someone please explain this part of problem E. How to find whether a given edge is visited for sure by the president vs may or may not case.

"Let's build shortest path graph, leaving only edges described above. If we consider shortest path from s to t as segment [0..D] and any edge (u, v) in shortest path graph as its subsegment [d1[u]..d1[v]], then if such subsegment do not share any common point with any other edge subsegment, except its leftest and rightest point (d1[u] and d1[v]), this edge belongs to every shortest path from s to t."

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

    His idea is pretty interesting.
    I am not sure if I understood it correctly, but here it goes:

    1. Consider any valid shortest paths (Suppose the length of which is D).
    2. As we traverse through the edges,
      The distance traversed starts from 0 (Starting vertex) to D (Terminal).
    3. Now we consider an edge (u, v) on the shortest path graph.
      Suppose the shortest distance to u is d(u) and the shortest distance to v is d(v)
      This edge essentially allows us to go from d(u) to d(v).
    4. For each edge, treat "d(u) to d(v)" as an interval [d(u), d(v)]
    5. Recall (2) the distance traversed starts from 0 to D.
      If an interval doesn't overlap w ith other intervals (from other edges),
      then this means that if we would like to "pass through" any value of distance ,
      this edge is the only way to go, which means this edge always exists in the shortest paths.

    Hope this helps.

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

      Hey thanks for replying. Couldn't understand the 5th point in your explanation. For example in the first test case: going from Node 1 to node 2 has cost 2. Then d(1) =0 , d(2)= 2, so the interval is [0,2], which is present no where else. But d(2)= 2, d(3)=7 , so interval is [2,7], which is also no where else present. So how do we make d(2),d(3) edge as an edge which is not always mandatorily visited vs only the d(1),d(2) as mandatorily visited by the president ?

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

        d(3) = 9 actually.

        [2, 9] overlaps with the interval [d(2), d(4)] = [2, 10]

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

          Hey, thank you for the reply.

          But if we search every edge with every other edge to find whether it is getting overlapped or not then wouldn't it cause a E^2 complexity , which is greater than E*log(V).

          Also can u please suggest a method and the data structure for such verification ?

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

            I think Sweep Line Algorithm should work here.

            Basic idea is sort the intervals, first by starting point then by ending point.
            Then scan the edges from left to right.
            Complexity would be O(ElogE) = O(ElogV).

            I didn't solve the problem this way, so I cannot really go into details on this. In case I made a mistake, let me know :)

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

              my soln: http://codeforces.com/contest/567/submission/12425879

              I submitted solution to E by checking each edge with every other edge. As we discussed, it is giving time limit exceeded for 19th case , which has 10^5 size of n.

              I think, I am almost close to getting an AC. Just need a little help to cross the time limit barrier. Can u please explain how you solved, this interval verfication phase of the problem ?

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

                Like I said, I didn't solve the problem this way.

                You can perhaps look at the author's solution.

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

Problem E: can some one please help me understand how to improve the performance of my code ? I have used dijkstra's algo two times, 2nd time to get shortest dist from destination to other vertices,which takes 2*E*logV.

Now finding the interval that overlaps is taking E*E=E^2. How can i improve it better to reduce the time taken to identify whether a particular edge is for sure visited by the president vs not for sure case?

http://codeforces.com/contest/567/submission/12426802

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

    You are checking overlap intervals online, while I did it offline, as said in the editorial, given a set of segments [l,r], we want to see if there is any other segments intersect it.

    One way to do this is as follow:

    1. Store all edges which are part of shortest path

    2. Convert them into segments [l,r] as said in the editorial

    3. Sort the segments O(E lg E)

    4. Loop through segment, keep track the rightmost distance R you get so far, for each segment [l,r] check if l < R, it is being intersected if it's true O(E)

    After this, the remaining segments are those without intersecting, which you must pass through it, total with O(E lg E)

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

Пора бы уже прикрепить его к раунду.

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

can anyone explain this line in the editorial of problem D

Each ship occupies a + 1 cells, except the last ship. Thus, for segment with length len the formula will look like (we add "fictive" cell to len cells to consider the last ship cell). This way, for [l..r] segment the formula should be http://codeforces.com/predownloaded/da/ab/daabfbc41456dfe3fc74f8b0eba284b1893a8abd.png .

why we have to use n+1 / (a+1) instead of (n/a). And also each ship occupies only a cells right..why it is a+1.

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

can anyone explain how this code works? (author's D solution)

auto it = xs.lower_bound(mp(x, -1));

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

At the problem F! Which sequences are answer for the first test case

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

From problem E after building the shortest path graph, we could simply find all bridges in that graph assuming it is undirected. Those would be the edges that would be "YES". My accepted solution doing the same: http://codeforces.com/contest/567/submission/27506292

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

The shortest path graph (call it G) would be a directed acyclic graph. We need to find all edges such that their removal would lead to no path from S to T. If we consider the undirected version of the G (call it U) then a bridge in U would also be a bridge in G. Further a bridge in U would always lead to two components that seperate out the nodes S and T. Hence a bridge in U would be a YES.

We need to prove the reverse i.e. an edge marked YES in G would be a bridge in U. Say in U we remove an edge marked YES. This should lead to two components, for if it didn't then there should be a back edge connecting the two components containing S and T, but since G is a DAG this isn't possible

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

Getting TLE for C. I have used DP, I dont know if I can optimize more using recursive DP. Please help me out:

http://codeforces.com/contest/567/submission/38002243