neal's blog

A brief overview of Round #503 (by SIS, Div. 1)
By neal, 6 years ago, In English

Thanks to the many authors of this contest (all eight of them) for a great set of problems! I'll sketch out the solution ideas for a few of them here:

1019A - Elections

Let's assume our goal is to end the election with v votes and determine the minimum cost to do so.

First, we need to make sure every other party ends up with fewer than v votes. To do this, we should bribe enough people in every party to get them down to v - 1 votes or fewer. We can do this greedily by bribing the cheapest people in the party.

After that if we have v votes (or more), we are done. Otherwise, we should repeatedly bribe the cheapest voters remaining until we get to v. Note that we can do this in O(n) time rather than by using an O(n) selection algorithm such as nth_element, though this wasn't necessary to pass the problem.

Finally, simply loop over all possible values of v and take the minimum cost across all of them for an O(n2) solution.

Code: 41475525

In fact it is even possible to solve the problem in . Here is a solution using ternary search on v: 41534204

1019B - The hat

Let . Let's define the function d(i) = ai - ai + m. We are looking for i such that d(i) = 0. Notice that since |ai - ai + 1| = 1, d(i) - d(i + 1) must be  - 2, 0, or 2.

First query for the value of d(1). If it is odd, then every d(i) is odd due to our property above, so the answer is  - 1. Otherwise every value d(i) is even. Notice that d(m + 1) = am + 1 - a1 =  - d(1). This means that one of d(1) and d(m + 1) is a positive even value, and the other is a negative even value. Since consecutive values can only differ by  - 2, 0, or 2, there must be an index i in between 1 and m + 1 that satisfies d(i) = 0, and we can use binary search to find this index.

Code: 41502076

: 1019D - Large Triangle

The obvious solution for this problem is O(n3), which can actually be squeezed in the time limit if you're careful; e.g., 41488961 and 41491248. However the real solution is , which I'll describe here:

Since the area of a triangle is , if we picked two of the n points as our base, we would know exactly what height we needed in order to make a triangle with the goal area. In particular, if we had our points sorted by distance to this segment, we could use binary search to determine whether or not there was such a point in time.

We can perform a rotational sweep on the set of points, which lets us set up this height-sorted list for every segment in order to solve the problem. (Imagine smoothly rotating the points clockwise, stopping whenever any two points are perfectly lined up horizontally.)

To do this we can take all n2 segments and sort them by angle. We also initialize our sorted list of points by y, breaking ties by x. We then iterate through our sorted segment list, swapping two points each time in order to maintain the height-sorted list. Finally we do two binary searches per segment to find if there are any points at the appropriate height (one above and one below).

Note that we can perform all these computations in integers only by using cross products. See the code below for details. Also, kudos to the problem writers for adding the guarantee that "no three cities lie on the same line," which helps keep the code cleaner without changing the key idea of the problem.

Code: 41502172

Unfortunately I don't know the solutions for C or E. If you do, leave a comment!

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

Comments Comments (30)
| Write comment?
»
6 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

Can you elaborate on the binary search part in Div1 B? What's your binary search function?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Sure. Let's assume d(x) > 0 and d(y) < 0. Now take . If d(m) = 0 we're done. Otherwise if d(m) > 0, we know there is a valid answer between m and y, and if d(m) < 0, we know there is a valid answer between x and m.

    Note that the half of the range we are throwing out could also have a solution, but it doesn't matter since the half we are choosing is guaranteed to have a solution.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Thanks!. I have been stuck on this for like 30 mins. Turns out to be a stupid doubt.

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If we are investigating range [L;R] than we take m = (L + R) / 2 and if d(1) * d(m) > 0 then r:  = m, else l:  = m

    → Reply
»
6 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Kaban-5 provides a nice solution to 1019C - Sergey's problem in his comment here.

Pick some vertex v, delete it and its "positive neighbourhood" (the set of all vertices u such that there exists a v → u edge), recursively find a solution in the remaining graph, add v back if you may do that without breaking independence of the set of the picked vertices. Now you have a solution for the original graph (to verify that, just consider two cases: you added v back or you did not).

You can see my code here for an implementation of this algorithm: 41503956

→ Reply
»
6 years ago, # |
  Vote: I like it +51 Vote: I do not like it

E is easy, just centroids and interval tree of convex hulls, nothing special :D

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    This kind of task should appear more often :P

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -37 Vote: I do not like it

      How dare you saying easy :(

      Benq couldn't solve it so please chill out!!!

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

        Now this is lame and pathetic. Please stop. You are not 'encouraging' Benq, you just annoy all of us.

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Number of BBST operations used is n log n, right?

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it +8 Vote: I do not like it

    So examining your code I figured out that you create query for each i = 0..m - 1 in some vertex that has biggest value if you take path from root to this vertex. I don't understand why we should check only this vertex. Can you explain it please.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it +8 Vote: I do not like it

      Oh, so I got this. This is because one of the ends of diameter of the tree is the farthest vertex from any. This is so smart. But time complexity is O(M * log(N)3) as for each query you make operations. So it seems like it should be TL.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Yea, I also was afraid so I was writing this in a way so I'd be able to squeeze it and add breaks, but it turned out to be fast enough. It is O(m·log3(n)), but consider the fact that there isn't exactly log of n every time, the sizes of hulls are kind of summing up to n, so constant isn't so big.

        → Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Link on problem 1019A with larger constraints (n ≤ 105), do not lose it

→ Reply
»
6 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Thanks neal, for providing great insights after every round! I also want to write my additional notes on this round.

Doing D without the "no three cities lie on the same line" condition : If there is a parallel segment, break ties by pair of (minimum point index, maximum point index). You can just add one more line for this. And this is enough! Code

My idea on E, which can be wrong as I didn't coded : Naively we can maintain an upper hull on every lines induced by a path. This is obviously too slow to fit in time, but hopefully we can reduce the path candidate by .

Do centroid decomposition on the given tree. For each centroid c find all lines that have its endpoint in c. We want to merge all pair candidates that comes from different subtree of c. We put all subtrees on heap and proceed like a Huffman coding (Work on two smallest subtree, and merge them as a single one)

For working on two smallest subtree we can generate their upper hull and do merge sort, which will generate all relevant candidate. Doing this for each centroid — now we have line segment candidate. We can now process all of these in , which is kinda scary but I bet it'll run on time.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Nice, makes sense on D. We just need to make sure that every segment we get in order will swap two consecutive points in the height-sorted list. I still think it's better that the authors didn't require this, since I wouldn't want someone to figure out the key idea of the problem but fail due to messing up this part.

    As for E, maybe Radewoosh can tell you whether his solution is or .

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Now being serious: standard algorithm to find a diameter of the tree goes as follows: find vetted as far as possible from vertex 1, and then vertex as far as possible from this vertex. So firstly let’s calculate distances (by distance I mean sum of linear functions) from 1 to every other vertex, take convex hull of this function and for every i find one of vertices which will be an endpoint of a diameter in i-th day using binary search. Now for every vertex we know in which days it will be an endpoint.

      Now let’s do centroid decomposition: with fixed centroid we can calculate distances from centroid to every vertex and then build interval tree over centroid’s subtrees, where in each vertex of interval tree we keep a convex hull of distances to vertices in subtrees which lie in this interval. Then, for each day (O(m)) for each centroid (O(log(n))) we want to check every other subtree (so O(log(n)) intervals) by doing a binary search (O(log(n))), so total complexity is O(m·log3(n)).

      I think that m can be replaced with n by some tricks. For example I was using the fact that for each vertex the set of days when it’s the first endpoint is an interval and when doing k binary searches on some convex hull, where k is length of this interval, I was starting next binary search from the place when I’ve found last optimum. I think that with “if” “check if optimum stays in this same place” just by looking at neighbors, then it would magically amortize to O(n·log3(n)), but I’m not sure of that.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 3   Vote: I like it +3 Vote: I do not like it

        You can transfer the given tree into a tree where the degree of each node is at most 3. Then for each day, get one endpoint x, and for each centroid u, get the node with maximum distance to u for each of u's subtrees and update the answer. This can be done by keep a convex hull using a deque in O(1). So it would be O(n log2 n + m log n).

        code here

        Slower than yours.

        → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        To me, E is one of those boring implementation problems where you know what to do, but there are enough things to do that you're going to make a bunch of silly mistakes. (I just solved it after fixing 3 bugs. 2 of them were TLE, easy to fix in-contest, and one was WA in very rare cases because I forgot that ax ≤ b, a > 0 doesn't convert to integer division x ≤ b / a for negative b with |b| < a, nearly impossible to catch by testing.)

        • problem: convex hull of paths on a tree
        • centroid decomposition — standard problem => subproblem: you have convex hulls of paths crossing through centroids, merge them; subproblem: you have groups of lines, make all pairs of lines from different groups and find their convex hull
        • subproblem: merging convex hulls — take all lines from all these hulls, create their convex hull — standard problem
        • subproblem: chull of sums of pairs — D&C, split all groups into 2 halves, recursively get the chull of pairwise sums and merged chull from each half, get the merged chull of the whole, get the sum of merged chulls from the two halves (sum of chulls = chull of pairwise sums of lines from the original chulls), merge this with the chulls of pairwise sums from each half => subproblem: find sum of convex hulls
        • subproblem: find sum of convex hulls — similar to "merge 2 arrays" if you store a chull as a sequence of line segments

        Merging 2 already existing convex hulls can be done in O(number of segments in both), same with adding them. The resulting complexity is for construction of the final convex hull — one log comes from centroid decomposition, the other from making chulls and then the D&C. Finding the answer is just printing M values on the hull.

        There are almost no clever ideas required for this — centroid decomposition, constructing convex hulls and the D&C approach are obvious, the only interesting part is doing sum of convex hulls instead of convex hull of pairwise sums. It's a garden variety "centroid decomposition with something" where that something is convex hull of pairs. (In fact, I think I solved something very similar this year.)

        → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

For the "Large Triangle" , how does swapping the points keep the points height-sorted ?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    If we imagine taking all the points and rotating them slowly clockwise, the only times that the height-sorted list changes are when two points are lined up horizontally with each other. This is why we produce an angle-sorted list of segments, to simulate this rotation.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Do we always rotate all the points with respect to the center ?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        It actually doesn't matter what point you're rotating around, since any segment will eventually rotate to being perfectly horizontal, regardless of the choice of point.

        In terms of visualizing it though, I like to think of drawing every point on a giant sheet of paper and spinning the paper.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thank you , finally got it.

          → Reply
»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Really helping, as the official editorial is a bit late. Thank you!

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I believe your solution is actually O(n^2log(n^2)) for 1019D — Large Triangle as you are actually sorting all segments.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    although it's just a constant factor — in Java it is probably why it gets TLE.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      .

      I was actually somewhat close to the time limit before realizing I could cut my number of segments in half and making other constant factor optimizations, so I could see a Java solution timing out. However it was an unfortunate situation where a few O(n3) solutions were already getting through, so they couldn't afford to make the time limit much bigger. (Maybe n ≤ 3000 and 7-8 seconds?)

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, probably increasing n would make more sense.

        Anyway, randomly discarding 20% segments makes my solution 42268118 passes. Probably because those are already covered by other segments.

        → Reply