Well, that was a blast, certainly. I hope that you... learned a lot from the contest. I wouldn't say "enjoy the contest", I know most of you hate geometry, I get you. But please do remember that, at least I did try my best to make every problem as high quality as possible. Like, if you don't get familiar with thinking about geometry now, you might never get familiar with it in the future. Though I apologize that E was quite hard, I suggest you to upsolve or read the editorials of the tasks you could not solve. I am telling you, it will be an experience that will make you improve much more from now.
Solution codes will be posted after the open hack phase. They are now added.
Spoiler
2074A - Draw a Square
Editorial
Code
2074B - The Third Side
Editorial
Code
2074C - XOR and Triangle
Editorial
Code
2074D - Counting Points
Editorial
Code
2074E - Empty Triangle
Editorial
Code
2074F - Counting Necessary Nodes
Editorial
Code
2074G - Game With Triangles: Season 2
Editorial
Code
Geometry dash ah contest :p
E :(
Solved E on pure luck, 310074961 The if condition is so stupid from me because earlier I was getting TLE on TC30, and then I mistakenly added the stupid if condition (which queries n-2, n-1, n) repeatedly after 50 queries which somehow got me AC which I do not deserve.
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
Yes thats understandable, with a problem which involves probability, you always have to and unintentionally leave room for a solution which gets AC with no proof. I also take it that thats the reason why hacks are disabled because so many solutions (including mine) are so easily hackable
I'm assuming the reason hacks are disabled is to prevent people from being hacked due seeding their random with a constant or time(0) instead of something unhackable.
also, it is impossible to analyze randomized algorithms without disabling hacks. (sure you can assume "reasonable number of tests" but that isn't a guarantee. There have been problems with upto 1000 tests, and problems with <= 10 tests, the scenarios are very different)
Yeah, I totally understand that, overall it was a nice problem with a good idea, although its placement could have been better
With high probability, I can say that the number of participants who guessed $$$E$$$ without proving the bound of queries on $$$75$$$ is more than $$$75\%$$$
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
I didnt know x+y = x^y + 2(x&y)
how cooked am i chat
Check this blog Some equations using Bitwise Operators
Thanks for sharing this blog! I also didn't know many of these properties.
it's not that complicated, you can prove this by imagining venn diagram, with x and y circles.
I submitted my solution for E just to try (actually, I thought it was wrong), but it got accepted... Why is it correct?
310125203
Same with mine, can someone tell me if there is a proof for this approach or was i just lucky 310070577
if i say in simple words then "probability of this question to be asked in exam is 0.0001% so you don't study that question and that question didn't come in your exams" same is for this question "probability of this question to get wrong answer is very less so you just submit it and get accepted."
I don't think I deserved an AC for my E solution: 310075413
For anyone wondering about the solution of D, the reason why you can compute for all
Ncircles at each value ofxwithout clockingO(N*M)solution, is that you're only computing points on the circumference of the circles which is bounded by2*pi*M.Umm.. Couldn't quite get that, can you please elaborate?
For each circle do this: go from y=0 to y=r[i] and for each y calculate the maximum and minimum x that lies within this circle (this takes logn time as i used sqrt ig) and ding this for n circles each inner loop runs r[0]+r[1]+...r[n] times which is m.
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 ;(
Why does E exist
I couldn't do E because I thought, "What if they use the exact test case where they are chasing my choice?".
With some probability, everything can be done in O(1) ig
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
lol tell that to my 18 WAs
link
this tragedy perhaps the implementation isnt exactly like the editorial. oh well
Yeah you have to swap with the random vertex of the triangle. The point is that either the interactor gives you a good point(for any swap the area will decrease significantly), or a bad point(for some vertex after the swap the area will be almost the same), but notice that for any bad point there is some good vertex, and you have a pretty high probability of picking this vertex, and the interactor can't predict that. In other words the interactor can try to make some swap bad but there will always be some good swap.
Legendary
It is actually possible to solve C in O(1)
https://codeforces.net/contest/2074/submission/310059528
Wow can you please explain the solution? I am so curious.
can anybody tell me what's wrong with my solution of D, https://codeforces.net/contest/2074/submission/310145808
basically tried to fix y coordinate for each circle, to get 2 x coordinates, rest is kinda similar to the original solution.
Geometry wasn't geometrying today -.-
E is a poor question. The problem states that the interactor is adaptive, which led me to mistake it for a proof problem. Because I think that as long as I can't guarantee that there are no points in my triangles, the interactor will definitely beat me.
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.
Yeah someone with similar code like me but he cycled one before like I went from 3-2-1 he went 2-3-1 and he got wa and I got AC
that is unfortunate, but technically an advanced interactor could break both of those
Thank God I am safe due to no hacks XD
If hacking is possible, then no one will be able to pass this problem.
Yeah I believe we can make hacks for every solution that there will always be possible way to cross the 75 queries limit
with good random seeded with time it would be very hard to do
I just noticed that I didn't explicitly mention in the initial version of the comment that it's important to swap with the random vertex, not in some predetermined order, because the interactor can predict this order(but as you mentioned some solutions like this have passed by luck)
then my passed purely by luck XD as I didn't knew about randomisation before this problem tbh.
This problem itself is very creative, but perhaps due to language reasons, I misunderstood some of the hints in the problem statement. I have considered multiple times, as the solution say, using random points to shrink the triangle area to get a solution that might work. But in competitive programming, "might work" usually means "won't work," which made me hesitant to submit.
where to practice questions like E?
Pray to god
dont
On codeforces
Ok sir
GeometryForces
W contest! Nice problems!
anyone know any other questions like E? i want to make sure i avoid them
Mathforces!
I was solving the E question in the last few minutes and I have no idea how this solution got accepted This submission could have much much more than 75 queries in a worst case scenario
How did it get AC?? https://codeforces.net/contest/2074/submission/310144435
you might want to read the other comment for why https://codeforces.net/blog/entry/140540?#comment-1254281
The way author hint on problem D with m bound to solve is true gold. It really saves my contest performance this time.
I wasn't able to solve D. Can you explain how this hint was useful in getting the solution ?
sum(r[i]) = m <= 10 ** 5. It means you can brute force sweep with fixing 1 coordinate and accumulate the other coordinate to the final answer.
My solution is fixing y, find all x fit the circle.
The intended solution is fixing x, finding all y.
got it .thnx
Worst E of all time. Not just because the proof of the question is too hard for a E, but also because a lot of people were able to do it on sheer luck, worsening rank.
310109380 Solution of C. Why Binary search working ? Any proof? Note : suppose x^y = z. z can be x+y-1 maximum and x-y+1 minimum
You mean my 10 WA submissions of E were all unluckily under the 1.8 * 10^-20 probility? I have tried 4 different method to change the triples which ask for. At last AC by srand() and rand()? What a poor problem
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.
In the AC submission I still use “deque”(pop front and push back), just use rand()in query.(? a[rand()+0] a[rand()+1] a[rand()+2])
Very misplaced problems E should be C C should be D D should be F F should be E
On problem E, I ended up testing the 3 triangles formed by the inside point and each pair of the other vertices and continuing with the new triangle formed by these 3 interior points (if solution not found yet). But I'm not yet sure that this is equivalent to the editorial solution minus the probabilistic approach. Mainly because it looks like I use 4 queries to reduce the space by at least a factor of 3. If anyone can explain, I'd appreciate it!
https://codeforces.net/contest/2074/submission/310129128
Is it an AD of Geometry dash? it's a good game by the way ;)
D was nuts.
Can you please help me understand the editorial or your approach (if it's not the same) for D?
here is a solution for C in O(1) //here
Can you please explain your solution?
i really don't have any proof but what I was trying to do is
I have N so I said lets try N-1 and N+1 to make the condition true so lets try N xor N-1 and N xor N+1 check if the answer satisfy the condition
My solution to G passes with $$$O(n^4)$$$, should this happen?
https://codeforces.net/contest/2074/submission/310074015
it shouldn't, but still took lesser time than my $$$O(n^3)$$$ one lol (probably because of the modulo)
https://codeforces.net/contest/2074/submission/310153212
I guess C++ can do $$$10^{10}$$$ operations per sec, lol
It felt more like a Geometry Olympiad than a programming contest.
Fun fact: A very assuring hint about E's solution was that they disabled hacks and guaranteed a fixed number of test cases. This pretty much implies that the intended solution relies on random and they didn't want participants to suffer from their "weak" random solutions being hacked. Of course, even without such restrictions, the intended solution can still be random if the chances to pass are high enough, but we all know that chromate00 is too kind to let such a massacre to happen :)
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.
Whats the point of such problems? what do they teach i found E extremly useless.
It teaches you that randomization is sometimes useful.
Then why are solutions that aren't random also AC? Why keep a question if you can't ensure that only truly random solutions can pass? Why not make a strong interactor that WA'S all solutions that aren't random, if you can't make it dont keep the question, or keep it in the end.
Do you really think every problem can set a constraint that only the very intended solution can pass and others can never? Let me tell you: almost every problem in the world has at least one way to solve that the authors couldn't come up with. Some kinds of problems are much harder to prevent suboptimal/heuristic solutions from passing than others, but it doesn't mean the problem should never exist, nor that it implies that the authors didn't try to prevent them at all.
Yeah right a problem can have many solutions, but it can be proven that those solutions are also right.
But a problem whose intended solution is a randomized solution,if that problem also AC's some non random solutions but WA'S some non random solution, is it a good problem? Doesn't it make it unfair?
Authors don't have responsibility to hack every unintended solutions. If your definition of 'unfairness' is to give WA on every single solution that has some chance to be hacked, then I would say that there are many many problems that are unfair. It just can't always be prevented. You can't and shouldn't expect the authors to invest thousands of hours into a problem to test every possible heuristics just to cut out a few more unintended solutions. It's not productive.
Then why not allow hacking in E and let's how your randomization algorithm helps you there. lol
Too big to admit when someone's wrong.
I dont really know why is it so hard to comprehend that such problems where a lot of "lucky" solutions can pass aren't good problems and yes author can't spend gazillions of minutes making it good, but yeah sure can spend a couple of minutes to not keep that problem at all.
Your initial comment was this:
and I don't understand why a problem has to be rejected because of these 'lucky' solutions when it can definitely teach you something more valuable, if that's what you were looking for. Why do you even care if some other solutions passed or not, if you can learn something good from the intended solution?
... Then you don't care about the time to invent a new problem to replace it at all?
You are right, I was blinded by my rating drop and ignored the actual reason why i am writing contests.
You regret yourself when you could not solve 1008C, while it could have been solved with randomization.
And now you complain about a task teaching you about the whole concept.
I guess you are very ironic.
I think that C has a very nice analytical solution, it was too adhoc for me.
Did you AC it via a random solution? if yes then you are just lucky.
Interesting observation in C:
For x of form 2^k or 2^k-1, there doesn't exist any y which can give you a non-degenerate solution.
For rest of the numbers, getting the leftmost closest 2^k-1 will always result in a degenerate solution.
Solution: https://codeforces.net/contest/2074/submission/310084628
Note: Got the observations by analyzing the patterns generated by brute force
Got no formal way of proving this, please let me know if anyone can help with the proof.
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$$$.
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$$$.
But the bit length is just a logarithm which can be found in a single operation.
Within the constraints, yes. But if we want to measure the complexity when it depends on the number of bits, it's better to assume a generalized solution, and there is no actual way to find it in $$$\mathcal{O}(1)$$$ time for an arbitrary value of $$$x$$$. The 'single operation' you mentioned is possible only because the upper bound of $$$x$$$ is specified.
How is this code? 310027336
I think it should be good , nevertheless could you think of a case failing it?
it is one of the best Div 3 contest..i have ever seen
cant believe the chance of getting wrong answer at e even if you understand the solution is not zero, wasted my time thinking there must be a perfect solution .
somebody from codeforces please change the contest from unrated to rated for me...
Can anyone tell me if its possible to do this? I tried this but I think we can't just keep the maximum x for a given y (the order of processing matters and we don't know exactly what should be processed first or do we?) I'd really appreciate if someone can share the solution if they solved it by fixing y instead
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 310178314
Great! Was too focused on doing it in real time that forgot that I can store this segments and use scanline later as well.
Yeah, when the contest finished I was very angry as you said, but I learnt from you and you enforced me to learn more and be familiar with geometry, so sorry if I was angry or wrote that it was a bad contest maybe I didn't like it in the start coz I wanted to be an Expert, but now I will never forget the lesson that I should be good at geometry as the other things, so thanks so much ^_^
I liked this contest. I solved A-E in contest and E was awesome. Idk why people get triggered at these types of less traditional problems, they care too much about rating.
Div3 is more difficult than Div2 this time.
Could someone can explain the editorial of F more clearly for me,I'm a Chinese and a English noob,so I would appreciate it if someone would give me a better explanation(I can read the editorial,but it's too hard for a specialist to understand).
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
thanks,now I understand it!
Interesting problems ,had to use high school geometry . I liked all the problems even though I wasn't able to solve last 3 problems
I love these ``heuristic'' problems! Really forces one to think outside of the box in terms of how to approach them.
does someone know the proof for the solution failing with probability 1.8e-20 in problem E
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.
For problem C, I think we only need to check all numbers with the binary form 11...11.
Nice Contest
problem G grind me a lot lol, i found that dp range can solve, but after all i can't find the dp transition state:LL
For C, i found a solution which runs in O(1) (or O(k) where k = complexity for builtinclz(), ive heard that its practically constant time):
basically if number has only 1 set bit or all bits are set then its not possible, since xor then is like regular addition there so triangle will always be degenerate there else i just used a slightly smaller number with all set bits, since xorring with that is guaranteed to result in some xor result which will be less than the sum
chromate00 As someone who has tried problem setting before, really curious as to how you made the test cases for E.
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...
Cool, thanks pretty insightful
Who else solved E without random probability! I couldn't prove but this worked https://codeforces.net/contest/2074/submission/310087663
Most concise O(1) solution for C 310203051
That's still O(log(x))
Where's the code?
Added just now
solved E without caring about the limit of 75 queries
Why did my solution passed on Problem C and E
Problem C : 310037314 Problem E : 310096257
For 2074E - Empty Triangle, I don't know why this 310209003 got an AC. Maybe on luck. But it worked :)
Got a question, I finished my first contest ever. Why do i see no rating in my profile?
Got 2/7 right.
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.
Yes, it would be harder .
I think div2 A is as hard as div3 B but you can try it anyway.
failed to solve D but it's really a good problem (I didn't notice that m<=2e5 and i thought calculate each x will get MLE :( )
Can someone tell me why did my C submission works, I feel like it worked by accident
can someone pls help me with this I do not understand why we are looking at probabilities for problem E isn't it obvious after choosing good triangles(with least no. of hidden points) 7 times will get the desired triangle? that is in total of 7*3 queries?
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.
Nice contest to understand triangles in depth and C was really nice for a XOR question
For problem E, i will ask x and i,j,k three triangles formed by three points, and then get three points again, and repeat this process. I think this convergence speed will be very fast, and no heuristic algorithm is used, could someone tell me why? 310067778
This competition has made my rating increase particularly big, thanks to this div3！
My Solution to E is something like a BFS, I have no idea why it works mathematically, someone proving it would be nice, my guess is it might be doing something very close to what the editorial does. Also, for C, I brute-forced the code on my machine to find a pattern that for an x what is the smallest value of y. I noticed that the answer was always of the form (1+ 2^n)< x. If such a n did not exist the answer is -1. I iterated over all valid n's and solved the problem in log2(x).E: 310096412 C: 310115607
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:
The starting condition may not include all 1500 points
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.
Possibly the problem maker did not think of this BFS approach, so it is not hacked.
E is the worst CP problem I have ever seen, nothing beats a problem which depends on luck.
Randomized algorithm is an important topic in adademics and you should be at least aware that good randomization can significantly reduce the running time.
When I solved 6 problems：Great！Yeah！Killed the F in last 5 min before Ended！ System Test：Hello. (Rejected on the test 11 of problem D)