swapnil07's blog

By swapnil07, history, 3 years ago, In English

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!

  • Vote: I like it
  • +29
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it -8 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        [DELETED]

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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 years ago, # ^ |
          Rev. 3   Vote: I like it +1 Vote: I do not like it

          " 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 years ago, # ^ |
            Rev. 3   Vote: I like it 0 Vote: I do not like it

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

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

    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 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

how to solve problem 2?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it
    My Approach
»
3 years ago, # |
  Vote: I like it -40 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    Can you explain 3rd one man ? The one in which we had to find maximum are parallelogram

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

    Lol, Can someone please tell me the reason for downvotes?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does the website request this?

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

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it -7 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will this contest's editorial would ever be published?

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

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

    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