Morphy's blog

CodeChef November Long Challenge 2019
By Morphy, history, 4 years ago, In English

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
  4. wrong_answer_1
  5. -is-this-fft-

Div 2.

  1. why_no_girlfriend, 61 lines in the challenge problem?
  2. pyBlob
  3. Louhc
  4. beet
  5. adarshagr8
  • Vote: I like it
  • +68
  • Vote: I do not like it

Comments Comments (19)
| Write comment?
»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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??

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

In DDART, what is the reason for this condition?

the first three events are of the first type

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You need 3 circles for a unique intersection point and you might want to use this point in your solution.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +10 Vote: I do not like it

      Any finite number of circles are not sufficient for a unique intersection point.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Even an infinite set is not sufficient, no need for "finite number'. :P

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Whoops. Yeah, that's true. Idk why it was three then.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes, nothing changes if we make it two. However making this to one creates corner cases, which is easy to handle but boring anyway.

          → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Having the point allows you to use convex hull trick or LiChao tree to answer the queries.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you please elaborate on how?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Find the point, offset every coordinate so that the center point becomes (0, 0) and just do some equations.

          → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          There is a thing called “inversive geometry”. Google it.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Sure I'll do that.

            Would you mind expressing your views about my approach using the quad tree.

            Thanks.

            → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain , how to solve PBOXES for 100 points ??

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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).

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply