### Morphy's blog

By Morphy, history, 5 years ago,

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:

Hope you enjoy the puzzles!

Congrats to the winners!

Div 1.

1. ACRush, 1400 lines of code in the challenge problem!
2. krismaz
3. VivaciousAubergine
5. -is-this-fft-

Div 2.

1. why_no_girlfriend, 61 lines in the challenge problem?
2. pyBlob
3. Louhc
4. beet
• +68

| Write comment?
 » 5 years ago, # |   +7 2nd Nov 2019, 22:18 IST: Unfortunately, a problem similar to SIMGAM was found to be existing in a past contest. Hence, SIMGAM has been removed from this contest, and has been added to the Practice section: https://www.codechef.com/problems/SIMGAM. We will add a replacement problem soon. Apologies for this inconvenience. WTF??
 » 5 years ago, # |   +5 In DDART, what is the reason for this condition? the first three events are of the first type
•  » » 5 years ago, # ^ |   0 You need 3 circles for a unique intersection point and you might want to use this point in your solution.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +10 Any finite number of circles are not sufficient for a unique intersection point.
•  » » » » 5 years ago, # ^ |   0 Even an infinite set is not sufficient, no need for "finite number'. :P
•  » » » » 5 years ago, # ^ |   0 Whoops. Yeah, that's true. Idk why it was three then.
•  » » » » » 5 years ago, # ^ |   0 Yes, nothing changes if we make it two. However making this to one creates corner cases, which is easy to handle but boring anyway.
•  » » 5 years ago, # ^ |   -11 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 information1. 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?
•  » » » 5 years ago, # ^ |   0 Having the point allows you to use convex hull trick or LiChao tree to answer the queries.
•  » » » » 5 years ago, # ^ |   0 Can you please elaborate on how?
•  » » » » » 5 years ago, # ^ |   0 Find the point, offset every coordinate so that the center point becomes (0, 0) and just do some equations.
•  » » » » » 5 years ago, # ^ |   0 There is a thing called “inversive geometry”. Google it.
•  » » » » » » 5 years ago, # ^ |   0 Sure I'll do that. Would you mind expressing your views about my approach using the quad tree.Thanks.
•  » » » » » » » 5 years ago, # ^ |   +13 I think it won’t work.
•  » » » 5 years ago, # ^ |   0 So using these 3 events, we can get this point. 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.
 » 5 years ago, # |   0 Can anyone explain , how to solve PBOXES for 100 points ??
•  » » 5 years ago, # ^ |   0 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).
 » 5 years ago, # |   0 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
•  » » 5 years ago, # ^ |   0 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.