### Alekhine's blog

By Alekhine, history, 6 weeks 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. peehs_moorhsum
5. thuustalu

Div 2.

1. xuanyiming, 61 lines in the challenge problem?
2. pyblob
3. louhc
4. beet

• +68

 » 6 weeks 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??
•  » » 6 weeks ago, # ^ |   -7 In the last CC Long Challenge Chef disliked TANDON and now SIMGAM ! .
 » 5 weeks ago, # |   +5 In DDART, what is the reason for this condition? the first three events are of the first type
•  » » 5 weeks ago, # ^ |   0 You need 3 circles for a unique intersection point and you might want to use this point in your solution.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +10 Any finite number of circles are not sufficient for a unique intersection point.
•  » » » » 5 weeks ago, # ^ |   0 Even an infinite set is not sufficient, no need for "finite number'. :P
•  » » » » 5 weeks ago, # ^ |   0 Whoops. Yeah, that's true. Idk why it was three then.
•  » » » » » 5 weeks 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 weeks 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 weeks ago, # ^ |   0 Having the point allows you to use convex hull trick or LiChao tree to answer the queries.
•  » » » » 5 weeks ago, # ^ |   0 Can you please elaborate on how?
•  » » » » » 5 weeks ago, # ^ |   0 Find the point, offset every coordinate so that the center point becomes (0, 0) and just do some equations.
•  » » » » » 5 weeks ago, # ^ |   0 There is a thing called “inversive geometry”. Google it.
•  » » » » » » 5 weeks ago, # ^ |   0 Sure I'll do that. Would you mind expressing your views about my approach using the quad tree.Thanks.
•  » » » » » » » 5 weeks ago, # ^ |   +13 I think it won’t work.
•  » » » 5 weeks 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 weeks ago, # |   0 Can anyone explain , how to solve PBOXES for 100 points ??
•  » » 5 weeks 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 weeks 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 weeks 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.