Hello, codeforces!
Because after Round #507 sad men in suits visited me in my flat, this time I won't write about any task from the future. Instead, this blog will be about my own trick. I said "my own," but probably some of you have already heard about it or even figured it out, but I've developed it by myself, so I consider it as my own.
In particular, it's GEOMETRY TIME!!!. But please, don't escape already. I also don't like this topic so much, that's why I really like this trick. Let me tell you a story from one onsite Polish contest, which took place a few months ago. I was thinking about one of the problems, and I've figured out that I had to do some binary-search (on doubles) and then check if a set of half-planes has a non-empty intersection. The answer would tell me in which direction should I turn in the binary search.
Firstly, I grabbed my head, because I've never written an intersection of half-planes. I had my acm library with Errichto's codes inside, but my knowledge in usage of his part was limited to copy-pasting FFT and Rho-Pollard. Not only I, but also Swistakk figured out the thing about binary search and was trying to intersect half-planes normally, but he failed (we still aren't sure why, probably because of precision issues). Then, I reminded myself a task from eliminations to BubbleCup 2017 (you can find it here), which I solved with the mentioned trick.
So, the trick goes as follows. Imagine a situation when you need to check if an intersection of a set of half-planes is empty or not. For simplicity, let's assume that there are no vertical lines in the input. So each half-plane tells us either "you have to be below this line" or "you have to be above this line." If there is no half-plane which tells us "you have to be below," then for every x we can find some y which is above every line, so the answer is YES (intersection is non-empty). This same applies to no half-plane which tells "you have to be above." From now, at every x we are limited both from down and from up.
Let's consider an upper convex hull of half-planes (this which tells us "you have to be below this"). Don't calculate it, just focus on the fact that it exists. It looks like this:
It might be confusing, but I'll call it "upper convex hull" anyway, mostly because it's above "bottom convex hull." :) The red area is an intersection of half-planes. It has one important property. It is... convex. Yea, it's not a big achievement to notice it. Next great observation: the bottom convex hull is convex. Not a big deal again. So, here comes the next one: the difference between upper and bottom convex hulls in convex. Yea, yea.. wait, what? The situation isn't so trivial this time. It's convex because of some mathematical laws. I'll skip the details, it's easy to notice it/believe in it. Buuuut, what does "difference between upper and bottom convex hulls" mean? For fixed x it means the difference between y of the upper convex hull and y of the bottom convex hull at this x (because we can assume that both convex hulls are graphs of proper functions).
Black and blue lines mean different types of half-planes. The green area denotes their intersection, and the red area denotes... Well, mentioned "difference" doesn't have to be positive. More, if the intersection of half-planes is empty it even has no places where it is positive, so the red area denotes its negative equivalent. The longer the vertical red line at some point is, the less (more negative) the difference is. Here's an example of a test where the intersection is empty:
So, the set of half-planes has non-empty intersection if and only if there is x for which the difference between upper and bottom convex hulls is positive. We want to find such x as a proof that it exists. How to do it? We know that this "difference" function is convex, so it's also bitonic (firstly increases and then decreases). Hmmmmm, bitonic functions, what do we know about them? They have important usage in competitive programming: ternary search! As we want to find x with the positive difference, let's find x with the maximum possible difference and check if this difference is positive.
How to calculate the difference for fixed x? Just find minimum on black lines (according to the picture), maximum on blue lines and subtract them.
"For simplicity, let's assume that there are no vertical lines in the input." Yea, of course, there are vertical lines in the input, as always... What can we do with them? In ternary search, we start with some initial interval, let's say ( - inf, inf). Of course, it's not real infinity. It's infinity like 1018, or something similar. Vertical half-planes should just cut our interval and make it smaller. If the interval is still non-empty after considering all vertical half-planes, we do the ternary search (only in this interval), if it's empty, the answer is NO.
Unfortunately, I'm not an expert in epsilons, but of course, I know basics. That's why I was so happy that I'm doing this trick as "a check" in the binary search. If due to precision I made a wrong decision, then probably I did it close to the border that I am looking for with the binary search, and from now I'll keep getting closer to it.
Anyway, I was forced to use epsilons in my code to make it work. As I'm not so good, I won't write about my intuitions, because they might be incorrect. Using an opportunity: is there anybody who feels that he is really good at handling with doubles precision and wants to write some tutorial about it? I'm sure that it'll be very useful for the community! :P
So, now we know how to check if a set half-planes has an empty intersection or not (with concise and easy code). It might be not so useful because some of you would take the challenge and try to intersect half-planes normally. What if it comes to half-spaces? It's harder to calculate convex hull in 3D than in 2D. What with the described trick? It turns out that it still works! Function f(z) defined as "the longest possible segment (with possibly negative length) parallel to OX with given z and for optimal y" is also bitonic (I'll skip the proof), so we can do two nested ternary searches.
So, this is the end. I hope that you found this blog useful. If you want to try something hard, you can try to solve this Errichto's task. If you'll get stuck, there is a nice Um_nik's code, which (if I understand it correctly) uses this trick. I hope that he won't be mad at me for referring to his code. Also, feel free to discuss this task in the comments. See you next time! :D
Oh, wait, wait, wait, there is one more thing. As this is already my fifth blog and it looks that I won't stop writing them, I want to thank my friends (Errichto, Swistakk, Marcin_smu and mnbvmar) very much, mostly for helping me make my English better, catching typos and of course for their opinions about solutions and tricks. Blogs aren't very short, so you guys should know that I'm really thankful for your patience!
1000 upvotes and Radewoosh will stop using orange lines that are barely visible on red background.
Prepare for images like this one next time.
I wish you could draw like this.
Btw. I guess we both think this is the best drawing ever.
It's from 516D - Drazil and Morning Exercise if somebody is interested.
WoW... Cannot believe still someone remember the picture I draw! Thanks for your admiration :)
We regularly recall it :P
Nice post. Maybe you know it, but test if half-plane intersection is empty con be done in O(n) expected time. Petr explained it here http://codeforces.net/blog/entry/45855.
In this method, there are some geometry besides ternary search (very hard) :((
Well you only need to have segment intersection funcion, and know how to test if a point lies in some half-plane. And the implementation isn't very difficult. Here is some implementation from a former teammate of me. The implementation is not the nicest but is relatively simple.
xd
We were talking about it with Radewoosh when he was writing this blog. Decided that Petr's method is completely different and harder, so isn't worth mentioning here.
It is true that conceptually it is more difficult than the solution explained here. I only mention it, because I think the implementation is not too complicated.
Nice idea!
You can deal with vertical lines quite easily by making them the initial bounds of your ternary search :-)
Yeah, sure, I'm not mad :) Btw, if you need something like 6th opinion (after you and 4 guys you mention in the blog) I will be glad to help. You are doing the best thing in community right now :)
On a side note: it was a team contest, so this could be not really my solution. If I remember correctly, the code was written by me, but the solution was created in collaboration with Merkurev mostly (maybe sivukhin helped too, but less so).
I also don't really remember the actual solution :) There was something about 2-argument functions and two nested ternary searches, I guess. I remember that we were afraid of TL, but there was partial scoring at first, so we decided to submit it anyway. Then in the middle of the contest scoring was changed to binary (either you get all the points or none) and we won the contest mostly because of it.
So, what I think about that
. Turns out I'm wrong again and it's some newly invented meaning for difference which is actually not set of points (which you expect it to be as common sense of difference requires that A - B is same kind of object as A and B) but a function of x. Bravo!
differencething when you mention it. At first I think about Minkowski difference. Then I think it's not really common and assume you're talking aboutP.S. To be mathematically correct here it would be better to say that we consider y = f(x) to be upper envelope and y = g(x) to be lower envelope. Then, obviously, y = f(x) is concave and y = g(x) is convex, thus y = - g(x) is concave and y = f(x) - g(x) is concave as well and it's exactly that difference function you mentioned. Therefore, you can apply your trick to find its maximum point which is positive iff intersection is not empty.
~ deleted ~
Okay, so can you kindly suggest how to turn this code into AC on BubbleCup problem?
This link doesn't work for me, so I guess that it just checks if a set of half-planes has a non-empty intersection.
To solve BubbleCup problem, firstly do a binary search to find the longest prefix that we are asked for. How can we describe each shoot? A good idea is to do it with two values: an angle and a power. Then, imagine a coordinate system, where instead of x and y we have tan(angle) and power. I'm not sure now if it should be tan, maybe it doesn't matter. Now, every target turns into two half-planes and reduces set of possible pairs (angle, power).
You're wrong, I actually use your trick, but the problem is that I presumably have some precision issues. Link is https://code.re/cxG , it my previous message it got embedded like codeforces.com/code.re/cxG
The thing is that in this problem it can be seen in a different way. Since parabola always goes through (0, 0), it has to be of form y = ax2 + bx and since it's pointed upwards from (0, 0) and gravity is pointed downward, parabola has to have b ≥ 0 and a ≤ 0 as well as yi2 ≥ axi2 + bxi and axi2 + bxi ≥ yi1. This is also reduction to half-planes intersection but with coordinates a and b and it has less floating point things here, so it should be better. Somehow I still catch WA.
I propose a new rule in CF. If you need help with your code, you can't use defines. I already started writing here that you have an overflow. Then noticed
#define int int64_t.You have numbers of magnitude 1018 and multiple and divide them by something, then you subtract two numbers of this magnitude and require the precision of result to be 10 - 9. You might need the precision of computations 10 - 27 for that. Start by removing one x[i] from a (because you divide it later by b = x[i] anyway). Experiment with inf and eps. Try to construct a test with n = 2 with big coordinates, where we barely can and barely can't hit both intervals.
Somehow this version (https://code.re/cxO) worked, it has no
#define double long doubleand no eps at all and it makes 130 iterations instead of 115. That seems crazy to me. What would be the rationale to write code like this and use at least 130 iterations on contest? Like, I wouldn't have much time to find feasible version of the implementation during the contest.The more problems like this you solve, the better intuition and understanding you will have. And well, use integers if possible.
You can change
stepin your ternary search to(r - l) * 0.4to converge towards the extremum faster, and thus do fewer iterations. It might make you choose a wrong direction when the remaining interval is small, but that isn't a big issue for smooth functions, e.g. for polynomials. Just don't choose0.499, that's too close to0.5and this issue would hurt you more.I don't think was a need for
b == 1 ? ... : ..., but ofc. you can try things like this and from time to time it will help you. Then you know that you should try it again in the future.I think that the lack of epsilon now isn't a good thing, very small one would be better. My guess is that it's possible to break your current code.
Consider always solving a problem with possible precision issues last. Make sure as much as possible that your logic is correct and then try a few different constants.
Because after Round #507 sad men in suits visited me in my flatis this codeforces secret services?Codeforces police, open up.
cdkrot doesn't wait for an answer. Radewoosh watches in horror through the window as cdkrot swings his mighty battering ram.
Error: Can't find file C:\Contesters\Work\invoker-prod\work\codeforces2\ad0e6c844900677e4cd524577818e74a\check-84552cd290cfea46b8aae8d7bda62c7c\run\output.txtSplinters of the C++ STL are flung throughout the room as the door shatters on test 94.
Radewoosh starts running. But he's quickly snagged by MikeMirzayanov. He turns around, just to see the long hook that only an array of length one million can provide.
Do you know why we're here?
"The contestants are forbidden to talk about subjects, related to the problems, with anybody, including other contestants. It is only allowed to ask questions to the jury via the system (see the 'Questions' section)."
The law is the law.
KAN turns away from the scene and heads to the pantry.
As you have revealed things from the future, so we can take things from the past.
The last thing ever heard is the distinct sound of a jar of Nutella falling to the ground.
I laughed soooooooo hard at the last line my stomach hurts xD
Oh so this is how you actually solve that BubbleCup problem, not by abusing bad test cases like I did :(
https://code.re/cyY
I AK IOI，tourist is my son？
My classmate use my computer and do this。QAQ
FYI, halfplane intersection is not that hard to implement. It can be done with a "circular" set ordered by halfplane angles. Here is a link:
https://github.com/bicsi/kactl/blob/master/content/geometry/HalfplaneSet.h
It's fully dynamic, and does O(log(N)) amortized per operation. If people are interested, I will write a blog post explaining it in more detail, just let me know.