Lewin's blog

By Lewin, 4 years ago, In English

I finally added the div 1 regional to the gym here. You can virtual participate at any time.

Solutions are available on the contest website here. Feel free to discuss problems here anytime.

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem H pivoting point?

Particularly, there's a "p-dk.cc" in the official solution package [1]. Its logic looks much simpler than the editorial, but I don't understand why it works. Meanwhile, a bunch of submissions seem to follow the same logic. Could somebody explain it to me?

[1] http://www.acmicpc-pacnw.org/ProblemSet/2019/editorial.zip

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    The first insight for the problem is that if we consider the current state of our windmill procedure to be described by $$$k$$$, the number of points to the left of the current line (passing through some arbitrary point), then all states with equal values of $$$k$$$ are reachable from each other, and the procedure will pass through all such states once before revisiting any.

    We can see that more intuitively by seeing that if we have a line of slope $$$m$$$, then there are no more than 2 states with a given $$$k$$$. If $$$n$$$ is odd and $$$k$$$ is $$$(n-1)/2$$$, then there's just one solution passing through that point (but really it's two overlapping solutions with flipped orientation). (If that's not obvious, try drawing some vertical lines and sweep them along a bunch of points).

    Another observation is that the windmill motion preserves the value of $$$k$$$, since when we change pivots, we always lose a point from one side (the newly promoted pivot) and gain a pivot on that same side (the demoted pivot). Again, this might take some examples to fully get.

    Since the windmill motion is continuous and monotonically increasing the angle, during the process of spinning through 360º, we must transition only to other states with equal values of $$$k$$$ with lines of increasing angles, so we can't miss any or hit any twice either. (Actually this might not be that rigorous so please correct me if I'm wrong)

    Now, to answer the original problem, we can essentially do the same idea as swapping the order of summation. Instead of simulating the windmill process for all values of $$$k$$$ and finding the maximum promotion count for all points in the process, we can just look from each point's perspective and see how many times it gets promoted for each state of a given $$$k$$$.

    For any pivot point, it can get promoted when a line passing through one of the other $$$n-1$$$ points hits it.

    Now, to cleanly go through all possible lines that hit our pivot, we just do the easiest thing possible! Consider the perspective of the pivot and just rotate through through 360º, treating the pivot as the origin. A line connecting our pivot to another point corresponds to some promotion event. Note, since the line extends from both directions of the pivot, we can rotate points that have angle > 180º by flipping them 180º.

    Now, we just need to go through these points and track how many are on the left side, and any time we see a point that wasn't mirrored, then it gets moved to the right side, and the opposite if it was flipped. Remember every point has two solutions, so we need to go through this process again, but reversing the orientation. Throughout this process, we can track the number of promotions the pivot receives for states of a given $$$k$$$ in $$$promotion[k]$$$, and we maximize our answer over $$$promotion$$$ for all pivots to get the answer.

    Hope that made sense!

    (Also I didn’t really understand the binary search solution so if someone could explain that that’d be great)

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

In problem G, my code got accepted assuming that there can be only one pulse on a wire throughout the time. I wonder how to solve this problem when there can be multiple pulses going through a wire.