AEtheReal's blog

By AEtheReal, 6 years ago, In English,

Solution of round #180 Div 1 Problem E -- Mystic carvings

For any three lines, they can intersect in one of the following 5 ways:


The problem is asking for the number of Type 2 or Type 5. Some of these configs are easy to count (e.g. Type 1), some are not. To count the number of Type 1, we can exhaust the middle line with index i, and count the number of lines on the right of the middle line (let it be xi) and on the left of the middle line (let it be yi), then the number of Type 1 with that middle line is given by xiyi. There are several methods to calculate xi efficiently. One of them is to process the endpoints in counter clockwise order (let the current endpoint be k), and use a segment tree or binary indexed tree to keep track of the number of lines (ai, bi), ai < bi with l ≤ ai < bi ≤ k for different l. Let j be the line with bj = k, then to find the number of lines with aj < ai < bi < bj, we just need to query the count at aj, then update the binary indexed tree by adding one to the position aj. In the actual implementation, we need to consider that the endpoints are wrapped circularly as well.

Unfortunately, Type 2 and Type 5 are the difficult ones. But we are only asked to find the total number of Type 2 and Type 5, which is (number of triples of lines) — (number of Type 1, 3 and 4). The problem then reduces to finding the total number of Type 3 and 4 (namely "We cannot give a 囧 without an XD and a HA"). Note that Type 3 and 4 shares a characteristic that two of the lines (the X in Type 3, and the two vertical lines in Type 4) has exactly one intersection with one of the other two lines. Therefore we can find the number of Type 3 and 4 by iterating through the lines, then count the number of lines on the right (xi), on the left (yi), and intersecting the considered line (zi = n - 1 - xi - yi), and give the number of Type 3 and 4 as the sum of zi(xi + yi). After removing double counting, we can get the answer.

Read more »

  • Vote: I like it  
  • +42
  • Vote: I do not like it