WIREL - Pictoric Editorial

PROBLEM LINK:

Practice
Div-2 Contest
Div-1 Contest

Author & Editorialist: Alei Reyes
Tester: Felipe Mota

DIFFICULTY:

Tie-break

PREREQUISITES:

Segment intersection

PROBLEM:

You are given:

  • N cities on a plane, the i-th city with coordinates (x_i, y_i).
  • M wires, the i-th wire is a segment with endpoints (A_i, B_i) and (C_i, D_i)
  • Two sepecial segments, one positive with endpoints (-1,0), (0,-1) and another negative with endpoints (10^6+1, 10^6), (10^6,10^6+1). A wire is positive (negative) if intersects the positive (negative) plate, or another positive (negative) wire.

You can move the wires, the cost of moving the i-th wire h_i units horizontally and v units vertically is h_i^2+v_i^2. After all moves, no wire can be both positive and negative (shortcircuit).

Let d^+_u be the minimum distance between city u and the endpoint of a positive wire. SImilarly let d^-_u be the distance to the nearest negative endpoint.

Your goal is to move the wires and minimize \sum_i (h_i^2+v_i^2) + \sum_u (d^{+2}_u + d^{-2}_u)

EXPLANATION:

The first idea I had was to keep a set of positive (negative) wires, initially the set contains only the plate, then move the nearest wire that is not in the set to intersect with one of the wires that is in the set (like dijikstra). Such process creates a tree, to prevent intersection I kept the tree from the positive wire in the lower half plane, and the negative wires in the upper half.

a0
a2

Such approach is is 10x better than the naive solution. Note that the ciites are uniformly randomly distributed, so is better if each tree covers the whole plane.

fraz_aatif generated similar trees that span larger parts of the plane:
F0
F1

Another idea I had was to distribute the wires as two parallel combs with interleaving teeths, or to sort the wires by slope and make many radial diagonals.

krijgertje distributed the wires as follows:
K0
K1

aatrey07 did a similar distribution, but with the combs in horizontal and in a zig-zag pattern.

r0
r2
The best solution in div2, written by aoligei is a bit simpler, but also follows the combs pattern in vertical:
ao0
ao2

I wrote the following script to draw the segments (You have to install matplotlib)

Plot.py
    import numpy as np
    import pylab as pl
    from matplotlib import collections  as mc
    import matplotlib.pyplot as plt

    import sys

    for tc in range(4):
        inp = open("secret/" + str(tc) + ".in", "r")
        out = open("secret/" + str(tc) + ".out","r")
        n, m = map(int, inp.readline().split())
        circles = []
        for i in range(n):
            x, y = map(int, inp.readline().split())
            circles.append(plt.Circle((x,y),125))

        lines = []
        for i in range(m):
            a, b, c, d = map(int, inp.readline().split())
            dx, dy = map(int, out.readline().split())
            lines.append([(a + dx, b + dy), (c + dx, d + dy)])

        c = np.array([(1, 0, 0, 1), (0, 1, 0, 1), (0, 0, 1, 1)])
        lc = mc.LineCollection(lines, colors=c, linewidths=2)
        cc = mc.PatchCollection(circles, facecolors='black')
        fig, ax = pl.subplots()
        ax.add_collection(lc)
        ax.add_collection(cc)
        ax.autoscale()
        ax.margins(0.1)
        plt.show()

Let us know in the comments what did you tried!

SOLUTIONS:

Setter's Solution

indent whole code by 4 spaces

4 Likes

Hello @alei , could you tell me, what did you use for plotting the data ?

I think this is what your are looking for.

Oh, my bad. Yes, that was it, thanks

1 Like

Could you update this editorial to include the best solutions from div1 and div2?