Ant_Man's blog

XXI Open Cup (GP of China)
By Ant_Man, history, 4 years ago, In English

How to solve C, G, I, J?

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

»
4 years ago, # |
← Rev. 3   Vote: I like it +17 Vote: I do not like it

C: At each point, each bit of rand() is the xor of some bits of the initial value of x. For each i, you know the (count of trailing zeroes in the binary representation of i) least significant bits of rand(), each of which gives an equation about the initial bits of x. In the worst case($$$n=50$$$), you get 47 equations, so you just need to test $$$2^{17}$$$ options of x.

I: The pea shooter will attack zombies in increasing order of $$$(t_i, i)$$$, so process zombies in that order, maintain how many peas have been shot before the current zombie became the target and binary search for the time at which that zombie dies. Using __int128 can be pretty useful.

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

There is an editorial written in Chinese here

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

    Any chance we can have copyable chinese text?

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

Do you guys have better complexity for G, how did everyone who submitted pass so easily? We have a lazy segment tree with 2-vectors in nodes and matrices of size $$$2 \times 3$$$ in lazy updates, update merging is matrix multiplication. The solution should have $$$O(q \log n)$$$ complexity.

Is it possible to get rid of matrix multiplication and do updates more efficiently, or do you have a different solution altogether?

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

    I passed storing historic sums in a lazy segment tree. No idea how you even use matrices here.

    Here's my code for reference. The complexity is the same $$$\mathcal{O}(q \log n)$$$, but I guess the constants are better.

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

    For us, the matrices were always of the form $$$[[1, a, b], [0, 1, 0], [0, 0, 1]]$$$ or $$$[[1, a, b], [0, 0, 1], [0, 1, 0]]$$$, so we just specialized it down to 2 integers and a boolean.

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

    Segment tuple: $$$(cnt_0, cnt_1, acc)$$$ (number of zeros in segment, number of ones in segment, accumulator)

    Update tuple: $$$(add_0, add_1, flip)$$$ ($$$add$$$ s are numbers to multiply $$$cnt_0$$$ and $$$cnt_1$$$ with before adding to $$$acc$$$. $$$flip$$$ (whether to swap $$$cnt_0$$$ and $$$cnt_1$$$) is always treated as happening after the addition, so when composing two updates, if the newer update has $$$flip = true$$$, the $$$add$$$ s in the older update should be swapped)

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

Where was this GP announced? I can't see it in the schedule.

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

J: Let's fix some vertex $$$A$$$ and look at all circles that cover the polygon and have vertex $$$A$$$ on the border. I claim that centers of such circles will form an arc of a circle with radius $$$r$$$ and center in $$$A$$$. This is easy to see if you start rotating the circle around point $$$A$$$. Also you will need to find two border points — two points on the left and on the right of $$$A$$$ which stop movement of the circle further. In the end you will have a border of the needed figure, consisting of such arcs (it's easy to see that this border will have no self-intersections). You can easily build this in $$$O(n)$$$ for each vertex, so $$$O(n^2)$$$ total, but that's not enough.

Let's get back to rotating a circle around point $$$A$$$. Eventually this circle will stuck on some vertex $$$B$$$. Now start rotating around point $$$B$$$ and so on, until you return to $$$A$$$. You will get some set of points along the way and actually for each vertex, two needed border points for the arc are exactly neighbours of this point in the set. So we just need to find this set efficiently. And actually this is a set of points $$$P$$$ such that there exists a circle, which covers polygon and has $$$P$$$ on the border. If you look at it's neighbours $$$A$$$ and $$$B$$$, you can apply some geometry and write down an inequality, which depends on $$$|AB|$$$ and $$$\angle APB$$$ and using it you can determine if this point can belong to the set or not. So the algorithm is as follows: maintain a queue of points, initially it has all points of polygon. When you look at new vertex, there are two options for the inequality with neighbours. If it says that the point definitely doesn't belong to a set, remove it from the polygon and add it's neibours to the queue. Otherwise just continue with other points. In the end the set of remaining vertices is exactly what you were looking for. Notice that we completely remove a point, so the neighbours of other points may change in the process and you have to maintain a cyclic list.

One of the easiest ways to calculate the area of this figure is to use Green's formula. Also if you got negative area, this means that the answer is 0.

→ Reply