SHRINES - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Div-2 Contest
Div-1 Contest

Author & Editorialist: Alei Reyes
Tester: Shubham Jain, Aryan Choudhary

DIFFICULTY:

Hard

PREREQUISITES:

median-graphs

PROBLEM:

You are given the edges of a triangle free circle graph.

There is one city in each face of the planar graph, and K of them are special. You can move from one city to another if their respective regions share an edge.

A city is good, if minimizes the sum of distances to each of the K special cities.

In one query you can choose two cities x, y, and the interactor gives you the number of special cities closer to x than y and the number of special cities closer than y to x.

Find all the good cities (medial set).

QUICK EXPLANATION:

Construct the faces from the edges (dual graph). The dual is a median graph, use the majority strategy to find the holy ciites, similar to finding the centroid of a tree

EXPLANATION:

1. Construct the dual

Finding the faces of a general planar graph can be difficult. However our graph is special, each internal vertex has at most degree 4 (because no 3 segments intersect at the same point). Moreover, we are already given the vertices of the unbounded face: the points 1 \ldots 2 \cdot N on the circumference.

Let’s keep a list of the open faces of the graph in clockwise order. Initially the open faces are (1,2), (2,3), \ldots (2 \cdot N, 1). In each step of the algorithm we’ll find one face, ore merge two open faces.

rose

Let f=(x_1, x_2, ..., x_l) be an open face, there are three cases:

  • There is one vertex u that joins the two endoints of f

If there exists a vertex u and edges (x_1,u), (u, x_l), then f is closed and two new open faces (x_1, u), (u,x_l) are created.

In the figure of the left, the face (2,3) is closed and a new region (2,3,14) is discovered.

  • There is one edge that connects the two endpoints of f

If there exists an edge (x_1,x_l) in the graph, then f is closed, and a new open face (x_1, x_l) is created.

In the figure of the right, the open face (14,3,4,13) is closed by the edge (14,13).

  • Two adjacent paths are merged

Whenever one of the endpoints of an open face doesn’t have an outgoing edge, it can be merged with their adjacent open face.

For example, in the figure of the left, after adding the edges (2,14) and (14,3), we can merge the paths (1,2), (2,14), similarly the paths (14,3) and (3,4)

2. Find the medial set

When the graph is a tree, if there are two special vertices u and v, then the medial set is the path connecting those vertices, because if we move one step away from u then we get one step closer to v keeping the sum of distances equal to the length of the path. When there are more special vertices, we can use a similar majority strategy:

  • Start from a vertex u, if there is an edge (u,v) in the graph and at least half of the special cities are closer to v than u, then v is at least as good as u, so we can start again our search starting from v.

If we repeat the previous step without visiting the same vertex twice, we’ll end up in a good vertex x. Then we can start a bfs from x and visit each vertex y that is as good as x. Each vertex is visited at most once, therefore the number of used queries is at most equal to the number of faces.

It turns out that the resulting dual graph of our triangle-free circle graph is a median graph, and the majority strategy also works! Can you prove it?

About SHRINES

Sorry for the long long statement, initially I planned to directly give the dual in the input, however when generating test data I noticed it was kind of interesting to find the faces. After I defined the internal intersection points, and how the cities are numbered it became too long.

SOLUTIONS:

Setter's Solution
2 Likes
2

The last part where the editorial does bfs, my solution is completely different ( I have no strict proofs). My solution goes as follows : Suppose for every edge I know the value of the querying at that edge, then we can simply iterate on all the vertices and then on its adjacency list to check if out current answer is improving by travelling this edges, and if it doesn’t then this is one of the required cities. Now the part is how to get value for all edges since they can be larger than C. But if I am not wrong then the given graph is a combination of 4-length-cycles connected to each other and some bridges between them (I assumed this), now for every square if I know the value of query at its edge E, then I claim that the value of the just opposite edge E’ is exactly same and this way total queries cannot be more than C. I got AC using this approach, if you have any strict proof please do share. Here is my code : Solution

3

Setter’s solution cannot be seen.

4

Unfortunately, my solution got WA. I tried stress-testing it against accepted solution, but found no testcase that breaks my solution. (I did however find a testcase that breaks the accepted solution of lomzom).
For this problem, it seems especially difficult to find out which part of my solution is wrong (interactive problem that gives WA if ‘something’ is wrong, multiple testcases per file). Can you help me to find out my bug? (either providing testcases, or generator used to create them, or testing what kind of error my solution has, or anything?)

5

This is setter’s soln. This is test file 1. You can look at Alei’s soln to see how to parse this test file. Along with normal input. The test file also contains the expected adjacency list and God cities.

6

Thanks for the help. It turned out that a small part of my solution was too slow. Apparently, in such a case the feedback is also ‘WA (-1.000000)’. After speeding it up, my solution got AC.