Warm greetings,
Newton School cordially invites you to be a part of our monthly coding contest. The challenge will go live on 31st August 2022 at 9 PM IST.
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 _Enigma__.
We would also like to thank pradumangoyal and 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.
- Dragon eggs to random participants (undisclosed).
Note: Top 5 participants from other countries can opt to receive the prize money through Paypal. All the other gift vouchers will be sent in INR.
We hope you like the contest! See you all at the leaderboard! Winter is coming :)
Couldn't register. Every time, I enter my valid phone number and click "Send OTP", it pops up the message -_-
Some unexpected error happened at third party library
Same
It's fixed now!
Sorry for the inconvenience caused.
Thank you for fixing it.
Will it be possible to submit in practice mode?
contest will open for practice mode soon
Hey, the contest is open for practice!
When i open problem it still has locked sign on the top-left corner. Locked sign has only problems which I had submitted during contest.
In E(Golden Coins), why is the weight of $$$(x,y) \rightarrow (x+1,y)$$$ denoted by $$$B$$$, not $$$A$$$?
You could say that this can be a matter of taste. However, I and gennadykorotkevitch made the same mistake of swapping these two parameters, so it should be unnatural to some extent.
What was the intended solution of Lady Alicent and Dragons?
I submitted $$$O(n^2 logn)$$$ solution.
I found answer for queries offline.
Here's what I did.
Suppose our current root is $$$u$$$. Now look at all nodes which are adjacent to $$$u$$$.
Suppose $$$x$$$ and $$$y$$$ are two children of $$$u$$$ such that $$$EdgeValue(u,x)<EdgeValue(u,y)$$$. Now $$$path(u,v)<path(u,y)$$$ for all nodes $$$v$$$ which lie in the subtree of $$$x$$$.
So if we intend to visit the nodes in order $$$a_1,a_2,\dots a_n$$$ such that $$$path(u,a_{i-1}) \leq path(u,a_{i})$$$, we should visit whole subtree of $$$x$$$ before visiting node $$$y$$$. So you can try recursive solution somewhat similar to dfs.
satyam_343 could you please comment your code or elaborate a little more, would be really helpful for understanding.
Suppose you have rooted the tree at some node $$$u$$$ and you plan to find $$$f(u,i)$$$ $$$(1 \leq i \leq n)$$$.
Here $$$f(u,i)$$$ gives the number of nodes $$$v$$$ such that $$$path(u,i)>path(u,v)$$$.
Also note that by definition answer to query $$$u$$$ $$$v$$$ is just $$$f(u,v)$$$.
Now let's see how to find $$$f(u,i)$$$ for all $$$(1 \leq i \leq n)$$$.
First of all $$$f(u,u)=0$$$.
Here is one way in which you visit nodes $$$a_1,a_2,\dots ,a_n$$$ such that $$$path(u,a_{i-1}) \leq path(u,a_i)$$$.
Traverse over all nodes $$$v$$$ which are adjacent to $$$u$$$ — $$$ v_1,v_2,\dots ,v_k$$$.
As our motive is to visit nodes such that path of current node $$$\geq$$$ path of previously visited node, it is intuitive to visit nodes in non-decreasing order of edge weight(here we are talking about order of $$$v_1,v_2,\dots,v_k$$$ only).
Also if $$$weight(u,v_i)<weight(u,v_j) (1 \leq i,j \leq k)$$$, all nodes in the subtree of $$$v_i$$$ should be visited before visiting $$$v_j$$$. So if we sort the nodes in all adjacency lists($$$adj[i] (1 \leq i \leq n)$$$ on the basis of edge weight and do standard dfs, we will visit all nodes in subtree of $$$v_i$$$ before visiting $$$v_j$$$.
But which node to visit first if $$$weight(u,v_i)=weight(u,v_j)$$$?
As both nodes have same path we should visit both nodes at same time. But how to do that?
In standard dfs we visit one node at a time — $$$ dfs(int CurrentNode)$$$
For our problem, we can visit a list of nodes at a time — $$$ dfs(vector<int> CurrentNodes)$$$
Is there something special about vector $$$CurrentNodes$$$?
Yes, all nodes in this vector will have same path.
Also it is not possible that $$$path(u,i)=path(u,j)$$$ such that $$$i \in CurrentNodes$$$ and $$$ j \notin CurrentNodes $$$ (Why? — Left as an exercise)
Thanks for explaining thoroughly. Got your point, really nice approach.
I simply used a trie. Fix a root $$$u$$$, now, I will store answers of all query in form $$$(u,v)$$$ in $$$dp[u][v]$$$.
Imagine a trie with all strings inserted starting from root. Formally, all strings which are formed via simple path $$$(u,i)$$$ are present in my trie. Then, to compute answer for query $$$(u,v)$$$ would be easy. (Figure it out yourself!)
Inserting strings into trie can be done in $$$O(1)$$$ instead of $$$O(L)$$$ ($$$L$$$ is the length of string) by doing a dfs on the tree and inserting string into trie on the way, (by maintaining the ending string node of the parent of the current node).
Time Complexity: $$$O(n^2)$$$
What was your approach for Problem 3(Stepstones)?
What I did was, I calculated the factors for the smallest number in the array and iterated over all factors in descending order and checked if it can be the GCD of entire array with doing the given operation at most one time. Time Complexity: O(Sqrt(Min(A)) + |Factors_Set|*N)
Ok my code should not work but it apparently passed all the test cases, as we can also replace the smallest element.
Counter TC:
2 10
2 8
My Output: 2
Actual Answer: 8
So yeah, you guys might wanna include this tc in the system also.
Why is this getting downvotes? Isn't that case is missing from the system test cases?
How are you going to select 50 random participants.
Is there any way to see the names of those 50 participants.
Click on the star to view the selected participants.
Where are the editorials posted?
swapnil07, also please share the video editorials if possible.
Where is the editorial?
No one reply me :(
When will you distribute the prizes?
They did not publish the editorials.
What about prizes?
They usually send it before the start of the next contest.
Ok thanks