### swapnil07's blog

By swapnil07, history, 5 weeks ago, 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:

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.
4. 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 :) #dsa, Comments (28)
 » 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.
 » 5 weeks ago, # | ← Rev. 3 →   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?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   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)> adj[MAX]; vector visited(MAX,0),pos(MAX,0); ll cur=1; ll till=0; void calc(vector vec){ if(vec.empty()){ return; } for(auto it:vec){ pos[it]=cur; } cur+=(ll)(vec.size()); vector> track; for(auto it:vec){ for(auto chld:adj[it]){ if(!visited[chld.f]){ visited[chld.f]=1; track.push_back({chld.s,chld.f}); } } } sort(all(track)); vector now; ll prev=-1; for(auto it:track){ if(it.f!=prev){ calc(now); now.clear(); } now.push_back(it.s); prev=it.f; } calc(now); } void solve(){ ll n,q; cin>>n>>q; for(ll i=1;i>u>>v>>c; ll d=c-'a'+1; adj[u].push_back({v,d}); adj[v].push_back({u,d}); } vector query[n+5]; while(q--){ ll u,v; cin>>u>>v; query[u].push_back(v); } ll ans=0; for(ll i=1;i<=n;i++){ for(ll j=1;j<=n;j++){ visited[j]=0; pos[j]=-1; } cur=-1; vector vec={i}; visited[i]=1; calc(vec); for(auto it:query[i]){ ans^=pos[it]; } } cout< •  » » » satyam_343 could you please comment your code or elaborate a little more, would be really helpful for understanding. •  » » » » 5 weeks ago, # ^ | ← Rev. 4 → 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$uv$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) 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) Code with commentsvector> adj[MAX]; vector visited(MAX,0),pos(MAX,0); ll cur=1; void dfs(vector vec){ if(vec.empty()){ return; } for(auto it:vec){ pos[it]=cur; //assigning value of f(root,it) and all nodes having having same value of f(root,i) are assigned value in one go } cur+=(ll)(vec.size()); //increasing the count of already assigned nodes vector> track; for(auto it:vec){ for(auto chld:adj[it]){ if(!visited[chld.second]){ visited[chld.second]=1; track.push_back(chld); } } } sort(track.begin().track.end()); //sorting the nodes on the basis of weight vector now; ll prev=-1; for(auto it:track){ if(it.first!=prev){ dfs(now); //visiting all nodes having same edge weight now.clear(); } now.push_back(it.second); prev=it.first; } dfs(now); } void solve(){ ll n,q; cin>>n>>q; for(ll i=1;i>u>>v>>c; ll d=c-'a'+1; adj[u].push_back({d,v}); adj[v].push_back({d,u}); } vector query[n+5]; while(q--){ ll u,v; cin>>u>>v; query[u].push_back(v); } ll ans=0; for(ll i=1;i<=n;i++){ for(ll j=1;j<=n;j++){ visited[j]=0; pos[j]=-1; } cur=-1; vector vec={i}; visited[i]=1; dfs(vec); //initially only root is in the vector for(auto it:query[i]){ ans^=pos[it]; //answer queries offline } } cout< •  » » » » » Thanks for explaining thoroughly. Got your point, really nice approach. •  » » 5 weeks ago, # ^ | ← Rev. 8 → 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 102 8My Output: 2Actual Answer: 8 So yeah, you guys might wanna include this tc in the system also. My Code#include using namespace std; const int MOD = 1000000007; const char nl = '\n'; void setIO(string name = "") { ios_base::sync_with_stdio(false); cin.tie(0); if (name.size()) { (void)!freopen((name + ".in").c_str(), "r", stdin); (void)!freopen((name + ".out").c_str(), "w", stdout); } } void findFactors(int num, vector &factors) { for (int i = 1; i * i <= num; i++) { if (num % i == 0) { factors.push_back(i); if (i * i != num) factors.push_back(num / i); } } } int main() { setIO(); int n, r; cin >> n >> r; vector v1(n); for (int i = 0; i < n; i++) cin >> v1[i]; sort(v1.begin(), v1.end()); vector factors; findFactors(v1, factors); sort(factors.begin(), factors.end(), greater()); for (int i = 0; i < (int)factors.size(); i++) { bool flag = true, ok = true; for (int j = 0; j < n; j++) { if (v1[j] % factors[i] != 0) { if (flag) { flag = false; if (factors[i] > r) { ok = false; break; } } else { ok = false; break; } } } if (ok) { cout << factors[i] << nl; break; } } return 0; } /***Author: Vishwajeet Prasad***/ 
•  » » » 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