### swapnil07's blog

By swapnil07, history, 2 months ago,

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.

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, Lubba_Lubba, 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

 » 2 months ago, # |   0 Auto comment: topic has been updated by swapnil07 (previous revision, new revision, compare).
 » 2 months ago, # |   0 Auto comment: topic has been updated by swapnil07 (previous revision, new revision, compare).
 » 2 months ago, # |   0 How to solve problem 3 (Max Out Parallelogram) ??
•  » » 2 months ago, # ^ | ← 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.
•  » » » 2 months ago, # ^ |   +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.
•  » » » » 2 months ago, # ^ |   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.
•  » » » » 2 months ago, # ^ | ← Rev. 3 →   0 [DELETED]
•  » » » » » 2 months ago, # ^ |   +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.
•  » » » » » 2 months ago, # ^ | ← 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.
•  » » » » » » 2 months ago, # ^ | ← Rev. 3 →   0 Edit : Never mind I understood what you were trying to tell me and I analyzed the time complexity wrongly.
•  » » 2 months ago, # ^ | ← 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?$height = \frac{|c2-c1|}{\sqrt{a^2 + b^2}}$ $base = {\sqrt{a^2 + b^2}}$where |a| = |x2-x1| and |b| = |y2-y1| my submission`void solve(){ ll n; cin>>n; vector v(n); for(ll i=0;i>v[i].ff>>v[i].ss; } map mm; for(ll i=0;i
 » 2 months ago, # | ← Rev. 2 →   +3 how to solve problem 2?
•  » » 2 months ago, # ^ | ← Rev. 2 →   +8 My ApproachSo here we can see that a chain is formed between numbersi.e. $1<->2<->4<->8<->16...<=n$And we can also see that a chain always start from an odd numberAnd we can easily say that if chain is of odd length then we will pick (len+1)/2 elements in our subset otherwise we can pick (len)/2 elements in our subset so we will remove floor((len)/2) elements.So we solve this by below method:Intially $ans$ is equal to $n$ and $chain = 1$now we will find number of odds between $[n,n/2)$ lets say this is $x$ then we will removeans = ans — floor((chain)/2)*xnow we will divide n by 2 -> n/=2and increase chain length by 1 -> chain++and do this untill n>0PS : Note a clean code C++ Code
 » 2 months ago, # |   -40 Missed rank 2 by 3 minutes. Fixed the bug in F, 3 minutes after the contest T-T.
•  » » 2 months ago, # ^ |   -13 Can you explain 3rd one man ? The one in which we had to find maximum are parallelogram
•  » » 2 months ago, # ^ |   -11 Lol, Can someone please tell me the reason for downvotes?
 » 2 months ago, # |   0 Why does the website request this?How is my gender, exact day of birth, and phone number relevant?
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 You can register with any random phone no. as well . Your account will work with unverified phone no. as well .
 » 2 months ago, # |   -7 Auto comment: topic has been updated by swapnil07 (previous revision, new revision, compare).
 » 2 months ago, # | ← Rev. 2 →   -16 leaderboard Mysubmission I had submitted my first correct answer after 3 wrong submissions but it's still showing +5
 » 2 months ago, # |   0
 » 7 weeks ago, # |   0 Will this contest's editorial would ever be published?
 » 5 weeks ago, # |   +8 How to solve the 4th problem, Funny Tree. Can anyone help?
•  » » 5 weeks ago, # ^ |   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
•  » » » 5 weeks ago, # ^ |   +3 Thanks for help.