E :(

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

hahaha

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

it's not that complicated, you can prove this by imagining venn diagram, with x and y circles.

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?

That's what got me stuck a lot. I tried hard to determine the exact rectangle to choose for any point on the axis. I believe if a jth point lies inside $$$k_j$$$ rectangles, then the number of points is bound by $$$m \over avg(k_1, k_2, ...)$$$, so the total number of rectangles to check is $$$O(m)$$$.

I dont know my dumb a** thought the hint about M "is it really useful??" part and thought the answer is all about finding through M so i thought the max range would be is from -M to +M and I would iterate over array to find the answer, and here is where i lost the question ;(

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

Wow can you please explain the solution? I am so curious.

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

https://mirror.codeforces.com/contest/2074/submission/310105677

You are not handling some x as this would reduce the total number of points

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://mirror.codeforces.com/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?

Can you please explain your solution?

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

https://mirror.codeforces.com/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.

This is what I came up with as well.

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 < 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<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

i have an alternate solution that is much simpler

for each $$$k$$$, count how many of those $$$2^{k}$$$ squares that can fit inside the range

for $$$k = 0$$$ this is just $$$(q-p)(s-r)$$$

for every other value of $$$k$$$:

we must find the number of pairs $$$(u,v)$$$ so that $$$[u.2^{k};(u+1).2^{k}] × [v.2^{k};(v+1).2^{k}]$$$ fits inside $$$[p;q] × [r;s]$$$ $$$(u,v \ge 0)$$$

which means it has to satisfy:

$$$p \le u.2^{k}$$$ and $$$(u+1)2^{k} \le q \Leftrightarrow \frac{p}{2^{k}} \le u \le \frac{q}{2^{k}}-1$$$

$$$r \le v.2^{k}$$$ and $$$(v+1)2^{k} \le s \Leftrightarrow \frac{r}{2^{k}} \le v \le \frac{s}{2^{k}}-1$$$

from there finding the number of $$$(u,v)$$$ is trivial, and for each square, it would "overlap" with $$$4$$$ squares of size $$$2^{k-1}$$$, which means $$$4$$$ of them are replaced by $$$1$$$ square of this size, thus the result will be subtracted by $$$3$$$ times the number of squares

code: 310097100

I believe it has to do with the fact that even if you don't choose the "good" triangle you are still likely to cut off some points. And the existence of a "bad" triangle containing almost all of the remaining points means that the "good" triangle contains very few points.

Experimenting with multiple points on the same parabola helped create decent test cases. Some other test cases include points forming spirals, rounded to integer coordinates. It was a nightmare trying to make tests strong enough while keeping the non-collinear condition. We almost considered removing that condition...

That's still O(log(x))

Added just now

For Div. 3 and Edu. Round, there will be a system test after the open hacking phase. After that, your rating will be updated.

for div4 and div3, it usually takes time .

Thanks @kakoujt and @karim__2

I will wait for my rating. I have completed Div 3 A,B,C(TLE). Can i try Div 2? Or would it be harder.

It actually is an accident but high probability that you will find a number at random that satisfies the condition

We don't know which triangle is good and therefore choose a new triangle randomly. Otherwise, it might be the case we choose the worst triangle at each step, which will result in asking more than 75 queries. But when randomising choices, probability of such cases are very low.

For E, I came up with the same approach 310209003, surprised by it. I cannot prove it mathematically either. I now think that it is a coincidence because:

1. The starting condition may not include all 1500 points

2. The initial triangle is split up into about 50 small triangles when reaching 75 queries. For random data, the probability of getting a triangle with no point inside it is considerable.

3. Possibly the problem maker did not think of this BFS approach, so it is not hacked.