Greetings Codeforces!
Starting from 1st November gear up for 10 days of non-stop coding in the November Long Challenge 2019.
This is a perfect opportunity for you to foster your learning while competing with the best. All the problems will be available in English, Hindi, Bengali, Russian, Mandarin and Vietnamese.
Also, if you have any original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here: www.codechef.com/problemsetting/new-ideas.
Joining me on the setting panel are:
- Setters: Akil Vohra, Vlad VladProg Zavodnik, Anay anay_07 Loya, Mohammadreza mrm_196 Mohseni, Erfan Erfan.aa Alimohammadi, Bohdan BohdanPastuschak Pastuschak, Kasra KMAASZRAA Mazaheri, Md upobir Sabbir Rahman, Hritik invincibel31 Aggarwal, Mayank mynk322.0 Padia, Harris gamegame Leung, Ojas [usr:ojas_bansal] Bansai, Alei Morphy Reyes.
- Tester: Yash yashChandnani Chandnani
- Editorialist: Mohammad Deemo Nematollahi
- Statement Verifier: Jakub Xellos Safin
- Admin: Alei Morphy Reyes
- Translators: Fedor Mediocrity Korobeinikov (Russian), Team VNOI (Vietnamese), Mohammad solaimanope Solaiman (Bengali), Akash Shrivastava (Hindi), Hanlin Ioser Ren (mandarin)
Hope you enjoy the puzzles!
Congrats to the winners!
Div 1.
- ACRush, 1400 lines of code in the challenge problem!
- krismaz
- VivaciousAubergine
- wrong_answer_1
- -is-this-fft-
Div 2.
- why_no_girlfriend, 61 lines in the challenge problem?
- pyBlob
- Louhc
- beet
- adarshagr8
WTF??
In DDART, what is the reason for this condition?
You need 3 circles for a unique intersection point and you might want to use this point in your solution.
Any finite number of circles are not sufficient for a unique intersection point.
Even an infinite set is not sufficient, no need for "finite number'. :P
Whoops. Yeah, that's true. Idk why it was three then.
Yes, nothing changes if we make it two. However making this to one creates corner cases, which is easy to handle but boring anyway.
The question talks about a point through which all the circles must pass. So using these 3 events, we can get this point.
I don't know how that point is useful in answering the queries though.
BTW I have an interesting idea about the solution but I am quite confused about it's memory usage.
I think we can maintain an implicit quad tree kind of structure. Each node of quad tree stores following information
1. left-up boundary 2. left-down boundary 3. right-up boundary 4. right-down boundary 5. count of circles that covers the rectangle represented by above (1-4) coordinates.
Now to handle event of type 1 Add 1 to all those quads which lie completely inside the new circle (2-D range update of adding 1 to all the nodes)
and for event of type 2 just count number of circles in that point if it is equal to number of events of type 1 encountered so far, then the answer is 1 otherwise 0.( a point query on certain coordinate)
Since we are maintaining implicit structure, I guess we should not face memory issues, but I would like to know if we can generate some case where this idea faces memory issues?
Time Complexity for each query would be in terms of $$$O(log)$$$ so that shouldn't be a problem.or Is it?
Having the point allows you to use convex hull trick or LiChao tree to answer the queries.
Can you please elaborate on how?
Find the point, offset every coordinate so that the center point becomes (0, 0) and just do some equations.
There is a thing called “inversive geometry”. Google it.
Sure I'll do that.
Would you mind expressing your views about my approach using the quad tree.
Thanks.
I think it won’t work.
You can't get this point from the first 3 events; look at the discussion above. It may be that all of those first 3 circles pass through the same two points.
Can anyone explain , how to solve PBOXES for 100 points ??
My AC idea was: Find the shortest path for mcmf algorithm (in 50 points solution) with segment tree (because the graph is just a line).
If someone could help me on Winning Ways, I'd really appreciate it! https://discuss.codechef.com/t/november-long-challenge-2019-winning-ways/44258
I replied. The key insight you're missing is that ACed solutions extend the field of integers modulo $$$10^9 + 7$$$ to have three different cube roots of 1.