Блог пользователя swapnil07

Автор swapnil07, история, 3 года назад, По-английски

Edit: The problems have been opened for practice, the editorials have been published!

Warm greetings,

Newton School cordially invites you to be a part of our monthly coding contest. The challenge will go live on 30th September 2021 at 9 PM IST. We sincerely apologize for the failed servers in the last round and believe that the same problem won't arise again.

Registration Link: Newton's Coding Challenge

You will be given 6 problems and 150 minutes to solve them. The contest will be rated for all!

The problems were written and tested by dnshgyl21, _deactivated_, Sawarnik, Xzirium, and swapnil07.

We would also like to thank gkapatia for co-ordinating the contest.

Highlights of contest:

  1. The Prize Money for the top 5 performers are as follows:
    • First Prize: ₹10,000
    • Second Prize: ₹5,000
    • Third Prize: ₹2,500
    • Fourth Prize: ₹1,500
    • Fifth Prize: ₹1,000
  2. ₹100 Amazon gift vouchers to the top 50 participants.
  3. ₹100 Amazon gift vouchers to 50 randomly selected participants ranked between 51-500.

Note: Top 5 participants from other countries can opt to receive an Amazon Gift voucher in their respective currencies. All other gift vouchers will be sent in INR.

We hope you like the contest! Hope to see you all at the leaderboard! :)

Edit: The registrations closes at 30th September 2021 at 9 PM IST. Do register yourself!

  • Проголосовать: нравится
  • +29
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by swapnil07 (previous revision, new revision, compare).

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by swapnil07 (previous revision, new revision, compare).

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve problem 3 (Max Out Parallelogram) ??

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

    I did brute force in a way. Note that the diagonals of a parallelogram bisect each other. We can use this, and store the middle point of each dioganal candidate. So remove duplicate points, then for each pair of points assume the line segment is one of the dioganals of the parallelogram, and store midpoint of it. Now iterate through all pairs of line segments having same midpoint and calculate the maximum area. At first this might look like O(n^3), but i believe it actually is O(n^3/k), where k is some constant. I couldn't construct a worst case example where k is small. I think i can prove k >= 6.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      Isn't this $$$O(n^4)$$$ ? Since there can be $$$O(n^2)$$$ such diagonals sharing the same midpoint and you are iterating on them.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Consider a line segment l , each one of the n points ( call them x) has at most 1 other point (y ) such that, mid point of l and xy coincide. So worst case you are comparing l to at most n other lines. This can be further elaborated to get bounds on k.

      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        [DELETED]

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          Actually by $$$O(n^4)$$$ I was referring to the time complexity. Is there any efficient way to iterate over all pairs of such lines that share a common midpoint?

          I had a different solution, in which I was calculating all lines possible which will be $$$O(n^2)$$$, and then for the lines with a given slope and length, I sorted them and took two extreme pairs of such lines so that the distance between them is maximum. I thought this was the intended solution.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
          Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

          " and thinking about points having same midpoint at worst we can only have n/2 pairs of point having same midpoint so traversing on them will cost O(n^2/4) " okay i am not sure if this is accurate. You have n/2 pairs of points with same midpoint, but you have O(n^2) pairs of points in total. You can think of it as, n/2 groups of lines each with O(n) lines, so naively analyzing this is O(n^3) comparisons. I think I can construct a degenerate case with O(n^3/12)ish comparisons easily, e.g. all xi's are 1, and yi = i for each i.Tho maybe there is some 2d analysis that tells why the groups will be rather sparse, if not degenerate case, idk.

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
            Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

            Edit : Never mind I understood what you were trying to tell me and I analyzed the time complexity wrongly.

  • »
    »
    3 года назад, # ^ |
    Rev. 4   Проголосовать: нравится +10 Проголосовать: не нравится

    I solved it by representing every pair of points in line form (a*x)+(b*y)=c (without dividing by gcd to store the equal length) then mapped ({a,b})->c and then for each ({a,b}) maximum area will be (c_max-c_min).

    how?
    my submission
»
3 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

how to solve problem 2?

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится
    My Approach
»
3 года назад, # |
  Проголосовать: нравится -40 Проголосовать: не нравится

Missed rank 2 by 3 minutes. Fixed the bug in F, 3 minutes after the contest T-T.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why does the website request this?

How is my gender, exact day of birth, and phone number relevant?

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    You can register with any random phone no. as well . Your account will work with unverified phone no. as well .

»
3 года назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

Auto comment: topic has been updated by swapnil07 (previous revision, new revision, compare).

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Will this contest's editorial would ever be published?

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

How to solve the 4th problem, Funny Tree. Can anyone help?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    If a node is uncolored , it can have maximum of in[i]+1 colors as options. in[i] denotes the number of edges the node has. We can make in[i]+1 possibilities for every node and take the minimum out of them using a recursive dp solution.

    Code