E :(

As a Geometry dash enjoyer, I wasn't able to immediately get what do you mean xD

Worst E ever. I appreciate that the author thought of such a creative idea but still Im not conviced this was a good E

I could not kill all deterministic heuristics. I was simply unable to. And, well, I tried my best, leading to an interactor that is $$$308$$$ lines long. If I want to kill all of them I could put $$$100$$$ inputs, which indeed kills the Codeforces platform before your solution

We are programmers; not mathematicians !! So, I guess it is not necessary to prove our approach during the live contest!! Y'all are free to disagree !!

With high probability, I can say that the percentage of participants who believed their solution was wrong is more than 75%.

I literally guessed it so bad

Check this blog Some equations using Bitwise Operators

Same with mine, can someone tell me if there is a proof for this approach or was i just lucky 310070577

Your method is equivalent to creating a full trinomial tree using BFS. Imagine that each time you take a node out of the queue, you randomly assign the value of that node to three children. - Your probability of success is the probability that no child node of the process has a zero. The higher up the tree you go, the higher your probability of passing. Suppose the height of your tree is x . Then there's a value that keeps getting smaller by x-1, each time randomly changing to [0,x]. And the smaller it is, the higher the probability that the next reduction will result in a 0 in its children. But you chose BFS over DFS, which makes the tree fat and short, which is probably the worst way to do it. But the probability of passing in completely randomized data is still not bad.

Umm.. Couldn't quite get that, can you please elaborate?

You receive a point that's inside your triangle and swap with a random point of your triangle. Even if the interactor tries to ruin your life, you have a very high probability of significantly decreasing the area, after swapping with one of the points

I had a similar O(1) solution that doesn't involve testing values: 310193367 I got this by writing a brute forcer and noticing a pattern no clue why it works

You will eventually have no points inside your triangle, after repeatedly swapping one of the points of the triangle with a point inside the triangle, the more difficult part here is that it will be fast enough(if you swap a point with RANDOM vertex). Well for any point that interactor picks, you might have a "bad swap"(after swapping, the area will be almost the same), but for at least one point of the triangle you have a good swap, and a pretty high probability of picking this point(you have only 3 points), and the interactor has no idea what point you will pick.

I found that to make the randomized more obvious (although to be fair the main thing that helped was the problem having hacks disabled). Might seem counterintuitive but I thought of it in the sense that an adaptive interactor could not adapt if the program made decisions randomly.

Pray to god

dont

On codeforces

you might want to read the other comment for why https://codeforces.me/blog/entry/140540?#comment-1254281

I wasn't able to solve D. Can you explain how this hint was useful in getting the solution ?

Your solution is wrong because it always pops the first point and pushes the point to the back. You have to randomly choose which point to pop.

Can you please help me understand the editorial or your approach (if it's not the same) for D?

it shouldn't, but still took lesser time than my $$$O(n^3)$$$ one lol (probably because of the modulo)

https://codeforces.me/contest/2074/submission/310153212

thanks to him my solution without randomisation passed and will not be hacked XD

He (and I) believe this is the only correct way to set randomized solution problems. But ofcourse it comes at the cost of giving away information.

Proofs:

Let's denote x^y as z.

1.

1) Let x = 2^k for an integer k. y < 2^k implies that y&(2^k) = 0 = y&x. x⊕y = x+y-2*(x&y) = x+y = z. x+y <= z -> There is no y, satisfying the given conditions.

2) Let x = 2^k-1 for an integer k. y < x implies that y&x = y. x⊕y = x+y-2*(x&y) = x+y-2*y = x-y = z. z+y = x-y+y = x <= x -> There is no y, satisfying the given conditions.

2.

Let x != 2^k and x != 2^k-1 for any integer k. Let i denote the most significant bit of x, j denote any other set bit of x, k denote any bit lower than i and being unset (i, j, k always exist). Then, by construction y = 2^i-1. x+y >= 2^i+2^j+2^i-1 >= 2^(i+1), z's most significant bit is i, therefore z < 2^(i+1) <= x+y holds. y < x+z holds because y < x holds by construction. x < 2^(i+1) — 2^k. z >= 2^i and y = 2^i-1 implies that z+y >= 2^(i+1)-1 and z+y > 2^(i+1) >= 2^(i+1) — 2^k > x. All conditions hold -> y = 2^i-1 satisfies the given conditions.

You are right. This leads to an $$$O(\log x)$$$ solution.

The editorial tells us that $$$y$$$ must have at least 2 on bits — one matching $$$x$$$ and one not matching $$$x$$$. Also, $$$y \lt x$$$.

1. If all bits in $$$x$$$ are on, i.e. $$$x=2^k-1$$$, then y cannot exist.
2. If only one bit in $$$x$$$ is on, it must be the MSB and $$$x=2^k$$$. Any $$$y$$$ will end up greater than $$$x$$$, so $$$y$$$ cannot exist.

If you discount these cases, then $$$x$$$ has an on bit in MSB and some on bits and some off bits afterward.

One easy solution for $$$y$$$ is to copy $$$x$$$, turn off the MSB (so now $$$y \lt x$$$), and turn on all the other bits, i.e. $$$y=2^{k-1}-1$$$ where $$$k$$$ is the bit length of $$$x$$$.

The time complexity is determined by counting the bit length of $$$x$$$.

Yes, it's possible to do. Let's begin by considering a solution where we fix $$$x$$$ from the other side. For each $$$x$$$, we have segments $$$[y_i - R; y_i + R]$$$, where $$$R$$$ is the maximum possible value (which can be find by math formula or bin search) such that the considered segment lies within circle $$$i$$$.

Okay, then the number of points for each $$$x$$$ will be the number of points that lie in at least one of those segments. This is a standard problem of finding the length of the intersection of segments, which can be solved using a scanline algorithm. However, it is harder to do for $$$x$$$ than for $$$y$$$, because the range of $$$x$$$ is $$$[-10^9; 10^9]$$$.

In the case of $$$y$$$, its range is $$$[-m; m]$$$. Analogously, for each $$$y$$$, we have segments $$$[x_i - R; x_i + R]$$$, where $$$R$$$ is the maximum possible value such that the considered segment lies within circle $$$i$$$. Similarly, let's find the length of the intersections of such segments for each $$$y$$$. The final asymptotic complexity is $$$O(m \log m)$$$.

Code 310266037