đŸȘŽ Quartz 4.0

Comes down to the smallest cut.

Mar 18, 20214 min read

Issue List

  • ✅ARC074D F - Lotus Leaves Difficulty: 2208

  • KUPC2016E E - fence Difficulty: unknown

  • ✅ABC193F F - Zebraness Difficulty: 2475 AC

  • ✅ARC085E E - MUL Difficulty: 2571 AC

  • ARC031D D - good shopper Difficulty: 2825 Consideration OK

  • ARC107F F - Sum of Abs Difficulty: 3130 Consideration OK

  • WUPC2019F F - RPG Difficulty: unknown Consideration OK

  • đŸ’»KUPC2017H H - Make a Potion Difficulty: unknown Integer

  • TTPC2015L L - graph coloring Difficulty: unknown

  • The Problem of Finding the Best Choice

    • Typical pattern

      • Paint a 100 x 100 grid in two colors.
      • There are about 100 options for two choices.
        • The cost and rewards will depend on that choice.
        • There is a dependency between choices.

    • Represent the selection with a two-color fill of the vertex.

    • We call these paint colors S and T.

    • Introduce two apex starts and a goal

      • These are painted with S and T, respectively.
      • The vertices themselves are sometimes represented as S and T. I use start and goal in the code, and S and T in the diagram.

    • If it’s a two-choice option, it’s a natural response.

    • Can be expressed in more than three choices ARC107F.

  • The basic form of the minimum cut is “if the color of both ends of a side is different, a cost will be incurred” and “we want to minimize the cost”.

    • If you subtract an edge of weight x from vertex S to vertex v, it means “pay cost x if v is T”.
    • If you subtract an edge of weight x from vertex v to vertex t, it means “pay cost x if v is S”.
    • If it’s a question of maximizing scores, make “score reduction” a cost.
      • Consider the case where all scores are obtained to be the offset, and the decrease from that offset to be the cost
    • If the cost is incurred when both ends of a side are the same color Invert one side of a bipartite graph.
    • I don’t care that the edge values are negative in this phase, because I’ll deal with that later.

  • Express the constraint “if vertex u is S, then vertex v is also S” by making the weight of edge uv sufficiently large

    • If we make it bidirectional, we get the expression u=v.

  • Once the graph is constructed, solve for the maximum flow

    • However, it does not correspond well with negative cost edges.
      • It becomes unintelligible around the negative capacity.
    • So we’ll work on removing the negative edges here.
    • Note the vertex v to which the negative edge -x is connected
      • Vertex v color is either S or T
      • Make it cost an additional x either way.
        • Just add the additional cost of x to the sides Sv and vT
      • Now the negative side disappears.
      • This operation increases the offset by x
      • This “add x” does not have to be exactly x, so if you are not comfortable with exactly x, you can just give a large enough value as you see fit.

  • Once this is done, use an algorithm such as Dinic to find the maximum flow f from the start to the goal.

    • Just read cost as capacity.
    • The answer that offset - f seeks

This page is auto-translated from /nishio/æœ€ć°ă‚«ăƒƒăƒˆă«ćž°ç€ using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.

Graph View

Backlinks