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:
- 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
- ₹100 Amazon gift vouchers to the top 50 participants.
- ₹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!
Auto comment: topic has been updated by swapnil07 (previous revision, new revision, compare).
Auto comment: topic has been updated by swapnil07 (previous revision, new revision, compare).
How to solve problem 3 (Max Out Parallelogram) ??
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.
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.
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.
[DELETED]
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.
" 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.
Edit : Never mind I understood what you were trying to tell me and I analyzed the time complexity wrongly.
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).
where |a| = |x2-x1| and |b| = |y2-y1|
void solve(){ ll n; cin>>n; vector<pll> v(n); for(ll i=0;i<n;i++){ cin>>v[i].ff>>v[i].ss; } map<pll,vll> mm; for(ll i=0;i<n;i++){ for(ll j=0;j<n;j++){ ll x=v[i].ff-v[j].ff; ll y=v[i].ss-v[j].ss; if(x<0){ x*=-1; y*=-1; } ll c=x*(v[i].ss)-(y*(v[i].ff)); mm[{x,y}].PB(c); } } ll ans=0; trav(w,mm){ srt(w.ss); ans=max(ans,abs(w.ss[0]-w.ss.back())); } cout<<ans<<endl;}
how to solve problem 2?
So here we can see that a chain is formed between numbers
i.e. $$$1<->2<->4<->8<->16...<=n $$$
And we can also see that a chain always start from an odd number
And 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 remove
ans = ans — floor((chain)/2)*x
now we will divide n by 2 -> n/=2
and increase chain length by 1 -> chain++
and do this untill n>0
PS : Note a clean code
Missed rank 2 by 3 minutes. Fixed the bug in F, 3 minutes after the contest T-T.
Can you explain 3rd one man ? The one in which we had to find maximum are parallelogram
Lol, Can someone please tell me the reason for downvotes?
Why does the website request this?
How is my gender, exact day of birth, and phone number relevant?
You can register with any random phone no. as well . Your account will work with unverified phone no. as well .
Auto comment: topic has been updated by swapnil07 (previous revision, new revision, compare).
OEIS solution for problem 2
Will this contest's editorial would ever be published?
How to solve the 4th problem, Funny Tree. Can anyone help?
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
Thanks for help.