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

Автор AkshajK, 10 лет назад, По-английски

Topcoder SRM 647 will be held tomorrow (Saturday) at 12:00 Noon EST; details here. Discuss the problems here after the contest!

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

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

a very similar problem to div1 500 discussed here

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

Один я как дурак линии в 500-й пересекал формулками и кучу кода писал из-за этого? :(

Откуда эти магические решения с "/ 3" в десять строчек?

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

    Рассмотрим случай с двумя роботами. Понятно, что роботу с маленьким баком выгодно израсходовать 1/3 часть топлива, на еще 1/3 часть вернуться в начало, а оставшуюся 1/3 отдать второму роботу.

    Если роботов 3, то первый отдает второму 1/3 топлива, как в первом случае, а далее аналогично рассматриваем второго робота и третьего. Ну и т.д.

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

    В точке Х у тебя два ограничения — ты не можешь отдать больше Х топлива (потому что у напарника нету места, чтобы принять больше) и не можешь отдать больше ((Volume - X) - X), потому что тогда тебе самому не хватит на дорогу назад.

    Это как раз две прямые, твое решение — нижняя огибающая этого набора, максимум будет в точке пересечения.

    Volume - 2 * X = X — отсюда X = Volume / 3.

    Так что "магические решения" прямо из пересечения линий и выходят.

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

A как правильно решать hard?

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

    Выкинем все вершины недостижимые из начала, и из которых недостижим конец. Добавим к каждому ребру обратное бесконечное ребро. Найдём maxflow.

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

      Ой, действительно, из-за новых ребер может появится путь через вершины, через которые раньше пути не было. Почему-то на контесте я об этом не подумал:(

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

    Я сдал в практис руме такое:

    В начале сожмем граф по компонентам сильной связности. Если вершины 0 и N — 1 находятся в одной компоненте, то ответ -1. Дальше выбросим все ребра, оба конца которых лежат в одной компоненте. Еще выбросим все вершины, которые не лежат ни на одном пути из старта в финиш.

    Теперь если бы не было ограничения на то, что на каждом пути должен быть ровно один чекпоинт, то задача была бы эквивалентна поиску минимального разреза в графе. Сведем нашу задачу к минимальному разрезу следующим образом. Пусть у нас есть ребро a -> b, тогда добавим ребра вида x -> b и a -> y пропускной способности +inf для всех x, которые достижимы из b и для всех y из которых достижима a. Тогда как раз если ребро a -> b попадет в разрез, то никакое другое ребро на пути содержащем a -> b в разрез уже попасть не сможет. EDIT: исходя из комментария выше вместо всех этих махинаций с дополнительными ребрами можно было просто добавить ребро b -> a пропускной способности +inf, обоснование почему это правильно останется примерно таким же.

    Если в итоге поток вышел бесконечный, то ответ -1, иначе ответ — величина потока.

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

How to solve 1000? I get that it's some kind of modified mincut, but...

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

    I did it this way.

    1. Let's find all strongly connected components. If the start and the end vertex are in the same component, the answer is -1.

    2. Now we can build a graph where the vertices are strongly connected components and there are all edges from the original graph(except those that lie inside the same component, of course).

    3. If there wasn't an additional condition that we can block only one edge on each path, we could have just found the minimum cut in the graph. But we can adjust the graph in such a way that this condition is satisfied. That is, for each pair of edges (A -> B) and (X -> Y), we should add an edge from X to B with cost = INF if and only if A is reachable from the start vertex, the end vertex is reachable from Y and X is reachable from B.

    4. The minimum cut(or the maximum flow) in this graph is the answer(if it is < INF, otherwise the answer is -1).

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

      I probably should've specified what I know better than "modified mincut", since I only needed point 3 :D

      but nice one.

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

      It's enough to add all inversed edges with cost INF, and then find mincut.

      But you should remove vertices, which are not on paths from 1 to n. I lost this.

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

        How can you proof this works? At least what is the idea?

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

          Consider a node v which lies on some path from S to T. One can prove that either 1) there is exactly one marked road on any path from S to v, or 2) exactly one marked road on any path from v to T. And if you know what is the case for each node, then you need to mark every road leading from a node of type 1 to a node of type 2. Also, roads mustn't lead from a node of type 2 to a node of type 1.

          And you just find the optimal partition using mincut.

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

          If you have 2 cut edges a->b and c->d on a path 0--->a->b--->c->d--->(N-1), the only case where you can't just remove one of them from the cut to make a smaller valid cut is when there's a path from vertex 0 to some vertex on the path b--->c and another path from an earlier (in DAG ordering) vertex on b--->c to N - 1.

          If we add an edge c->b that can't be cut, it would stop being a valid cut.

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

    You can't block any edge of a SCC (because cycles), so join all SCCs into a single vertex, and add costs for every edge between SCCs to get new costs.

    Now we still have to enforce "can't go through two blocks" condition. To do this, for every edge in the forward direction, make an edge in the reverse direction with infinite capacity.

    And please remember to delete all SCCs that aren't part of any 0 to N-1 path before the mincut, otherwise the troll test will hunt you at night.

»
10 лет назад, # |
Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится
  1. For each building compute its maximum possible height. For each constraint t[i] on x[i] it gives t[i] + |x[i] - j| constraint on j. The answer is maximum over the computed heights.

  2. If we have robots a0 ≥ a1 ≥ ... ≥ ak then we can reach distance . We use simple dp[budget][prefix] to compute best value.

  3. I thought it was scc and then flow. But many solutions fails. So there are some tricky cases...

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

    can you provide the explanation for 2nd problem?, please

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

      First part is to get this formula for best reachable distance. Just solve it for 2,3 robots and then some induction argument.

      For 2 robots a ≥ b the answer is 0.5(a + b / 3). 2nd robot should turn around in the first moment s such that no fuel will be lost. So first robot should have b - 2s place in his tank (for fuel which is useless for b), so s = b - 2s and s = b / 3.

      If we have more robots then we can compute moments in which they have to turn around in the same way. i.e. Each robot should turn around in the first moment such that no fuel will be lost (next robot has already place for useless fuel of actual robot).

      After careful computations we get the formula 0.5(a0 + a1 / 3 + a2 / 9 + ...).

      The second part is standard dp. We sort robots by increasing capacity. For each prefix of robots k and budget b we compute dp[b][k] which is best distance if we can use only k-first robots and have b dollars. The transition formula is

      dp[b][k] = max(dp[b][k - 1], 0.5ak + dp[b - cost[k]][k - 1] / 3).

      We can take k-th robot or not.

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

I couldn't understand div1-500. In the sample test #0, why 2 robots with capacity 1 must stop at 1/3 first? They can stop at very close 0 point, then robot 1 can donate amount of fuel to robot 2 more than when they stop at 1/3. Hence, the largest distance robot 2 can go will as far as possible.

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

Can someone please explain how to solve the div-1 500?

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

    Sort the robots by their capacity in increasing order , then apply this dp:

    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i]] / 3 + cap[i])

    then the final answer is max(dp[n - 1][i]) / 2

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

I am interested to know about solving Div 2 1000, I got binary search as the only idea which gives wrong answer. Any better ideas?

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

can anyone please comment on this? I have a problem with understanding what is wrong with my solution:

http://codeforces.me/blog/entry/16046