### supersonic11's blog

By supersonic11, 2 months ago,

Today I had CodeNation coding round (on-campus):

question1 : Give an array $a$ of size $n$ where $1<=n<=1e5$ and $1<=a_i<=2e5$, we need to find out for each $i$ number of other $j$ such that either $a_imoda_j=0$ or $a_jmoda_i=0$.

Example : 4 2 1 3

output : 2 2 3 1

We can solve it in nlogn by using concept of harmonic series.

question2 : given tree of size $n$, $1<=n<=1e5$ indexed from 0,rooted at node 0 and each node having distinct value from 0 till n-1. Find mex of each subtree.

Example : n=3 , edges : (0,1),(0,2) and values : v[0]=0, v[1]=1, v[2]=2. Output : mex[0]=3,mex[1]=0,mex[2]=0.

Was able to solve partially in $O(n*n)$. can someone tell how to solve in better complexity ?

question3 : Given an array $a$ of size $n$, beauty from $l$ to $r$ is defined as $a_l+(-1)*a_{l+1}+a_{l+2}+(-1)*a_{l+3}....$repeating till r. $1<=n<=1e4$. There are $Q$ queries, $1<=Q<=1e5$. Either 1 i x, which means update a[i]=x, or 2 L R, which means maximum beauty among all subarrays in index range L to R. Note that $-1e9<=x,a[i]<=1e9$.

Example :n=2 a: 4 -2 7, two queries 1 2 1e9 and 2 1 3. answer for query is 7.

How to solve 2nd and 3rd one ?

• +39

 » 2 months ago, # |   0 can you share the code for 1st problem ?
•  » » 2 months ago, # ^ | ← Rev. 2 →   -8 Code...  int n,N=1e5+5; cin >> n; int z[N], f[N]; memset(z, 0,sizeof(z)); memset(f, 0,sizeof(f)); pair a[n]; for (int x = 0; x < n; x++) { cin >> a[x].F; a[x].S = x; z[a[x].F]++; } sort(a, a + n); int d[N], ans[n]; memset(d, -1,sizeof(d)); for (int x = 0; x < n; x++) { if (d[a[x].F] != -1) ans[a[x].S] = d[a[x].F]; else { int i = a[x].F; int c = z[i] - 1; c += f[i]; for (int y = i * 2; y < N; y += i) { c += z[y]; f[y] += z[i]; } ans[a[x].S] = c; d[i] = c; } } for (int x = 0; x < n; x++) cout << ans[x] << ' '; 
•  » » 2 months ago, # ^ | ← Rev. 5 →   -12 [DELETED]
•  » » » 2 months ago, # ^ |   0 Can you please explain your approach for Ques 1?
•  » » » » 2 months ago, # ^ |   0 He made an dp array which initially stores the frequency of elements with value equal to i in dp[i]. Then in the loop, he calculated the answer for every present value, he first add the all multiples of value i as they will friends to and then he adds all the factors which are present in the given array. The --res[i] is for avoiding counting itself as the friend.In last he makes an answer array in which he stores the answer calculated for each value and returns that.
•  » » 2 months ago, # ^ |   +3
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 can you explain the first one please?
•  » » » » 2 months ago, # ^ | ← Rev. 3 →   0 Let f[i] = frequency of value i in given array and cnt[i] = count of value j such that i%j=0 or j%i=0 for every i, iterate over its multiples and perform cnt[i] += f[j] (case j%i=0) again, if (i,j) is a pair, (j,i) is also a pair, so cnt[j]+= f[i] when i=j, we did cnt[j]+=f[i] , cnt[i]+=f[j], so we subtract f[i] from each cnt[i] ( counted twice ) finally we don't want the pair with itself, so we subtract 1 from the total ans = cnt[i] — f[i] — 1
•  » » » » » 13 days ago, # ^ | ← Rev. 2 →   +1 .
 » 2 months ago, # |   +15 Q2: Just observe that there will be a path from root to the node having value 0, outside this path all the other nodes will have their mex=0. Now for this particular path we can maintain an array starting from the node having value 0 to the root and marking all the values in that particular subtree.
•  » » 2 months ago, # ^ |   0 Thanks! Understood.
•  » » 2 months ago, # ^ |   0 won't it give TLE?? I mean in worst case time complexity will be o(n^2)
•  » » » 2 months ago, # ^ |   +14 No, for each ancestor of the node with value 0, we'll only mark those nodes in its subtree which haven't already been marked. This is $\mathcal{O}(n)$.
•  » » » » 6 weeks ago, # ^ |   0 can you post or send me solution??
•  » » » » » 6 weeks ago, # ^ |   0 It is what sqrt_pi has described above.
 » 2 months ago, # |   0 is anybody remember the where these problem are? can u please provide problem link
 » 2 months ago, # | ← Rev. 3 →   0 .
•  » » 2 months ago, # ^ |   0 all subarray ?
•  » » » 2 months ago, # ^ |   0 F, missed that part xd
•  » » » » 2 months ago, # ^ |   0 me too, that too in the actual test :(
 » 2 months ago, # |   0 how to do 1st and what is harmonic series
•  » » 2 months ago, # ^ | ← Rev. 4 →   0 Harmonic Series. As a side note, N/1 + N/2 + N/3 + ... + N/N is approximately NlogN. (reference)edited to remove incorrect approach.
•  » » » 2 months ago, # ^ |   +3 For input array 2, 4, 8, your output would be 1, 2, 3 but the correct output would be 2, 2, 2.
•  » » » » 2 months ago, # ^ |   0 Thanks for pointing it out! Much appreciated. I've edited the comment to remove that part.
 » 2 months ago, # | ← Rev. 4 →   0 For Q2 use an Euler's tour on tree and store the flattened tree in array, then you can query on subarray for every node to calculate MEX of each node, you can use segment tree for calculating MEX for each query.Total complexity: $O(nlogn)$
•  » » 2 months ago, # ^ |   0 What will you store in nodes of segment tree?
•  » » » 2 months ago, # ^ |   0 You can answer the queries offline, first sort the quersies by increasing order of $r_i$ , then traverse $i$ from left to right and store last position of $x$ till $i$ in $last[x]$ , now for the queries with $r_i=i$ , you need to calculate minimum $x$ such that $last[x]  » 2 months ago, # | ← Rev. 3 → +14 Someone asked me the second problem as a doubt after their round had ended. The first solution I came up with was$N.log^2N$using DSU on trees. SpoilerYes I now realise that it was an overkill :( •  » » 2 months ago, # ^ | +1 Yes I now realise that it was an overkill :( What is better approach ? •  » » » 2 months ago, # ^ | +10 There is a single chain of nodes in which one node will have the value$0$. For all subtrees which do not contain this node, the answer is simply$0$. For this chain, we can calculate the answers in linear time. •  » » » » 2 months ago, # ^ | 0 For that nodes which are ancestor of 0, while calculating its mex will we have to look for the nodes values in their subtree(this won't happen linearly) or is there any method by which we can find its mex just by the mex of its children? •  » » » » » 2 months ago, # ^ | ← Rev. 8 → 0 We can maintain an array/vector of size$N$, where each index has value either$1$or$0$depending on whether the current subtree contains that number or not. Starting from whichever vertex has the value$0$(let's call it$v_0$), perform a depth-first search on all of its unvisited children, mark them as visited and then mark the starting node as visited as well. We also maintain a variable which stores the current MEX. While performing our dfs, flip$arr[value]$from$0$to$1$for all vertices that we encounter. If we encounter a vertex which has its value equal to our current MEX, we flip our$arr[MEX]$from$0$to$1$, and keep moving forwards in the array until we hit a$0$again, which is our new MEX. We can do this for all ancestors of$v_0$, moving up from$v_0\$ towards the root. I hope this made sense. If it did not, please let me know!
 » 2 months ago, # |   0 I think the tree question can be done in nlogn using set. Where set will repersent all the values that are not present in the whole substree and the merge the left and right subtree set and ans for i will be *st.begin()
 » 2 months ago, # |   0 pls share how did you use harmonic series for Q1
 » 2 months ago, # |   0 For Ques 3 you can use Segment Tree. It is a very general ST problem (refer this) Finding subsegments with the maximal sum -> scroll down to this topic in above link.It is almost same as given in the above link, the only difference is that you have to create 2 segment trees, first for(-a[0],a[1],-a[2]...a[n]) and second for (a[0],-a[1],a[2],-a[3].....-a[n]).Now depending upon the query type you can find the maximal subarray sum accordingly.Also note that in the update query you will have to update both of your segment trees.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 .
•  » » 2 months ago, # ^ |   0 I think your solution is wrong because suppose u are querying on subarray [-100,1,2] in one of the query, then your solution will return 101 but actual answer is 2.
 » 2 months ago, # | ← Rev. 2 →   0 This is my proposed solution for Q2 Let loc[x] be the location of node with value x , Let LCA(x,y) be the lowest common ancestor of node x and y ,Then LCA(loc[1],loc[0]) and its ancestors will have mex >=2 , LCA(LCA(loc[0],loc[1]),loc[2]) and its ancestors will have mex >=3 and so on...Can anyone confirm if this will work ?
•  » » 2 months ago, # ^ |   0 This sounds good logically, but how will it help in finding the answer?
•  » » » 2 months ago, # ^ |   0 So if a = 0 , b = LCA(loc[1],loc[0]) ,c = LCA(LCA(loc[0],loc[1]),loc[2])Then all nodes in range : [a,b) will have mex = 1 [b,c) will have mex = 2 and so on.. All the other nodes will have mex = 0
 » 2 months ago, # |   +4 Found video editorials for these questions.
 » 2 months ago, # |   +2 One can try GSS3 on spoj. It's similar to 2nd problem.
 » 6 weeks ago, # | ← Rev. 3 →   0 I don't know if it's correct, but here is code for Mex of a tree: code#include using namespace std; #define int long long int const int mxN=100001; class Tree { vectoradj[mxN]; vectorval; mapvalToInd; vectorin; vectorout; vectoreTour; public: Tree(vectorarr) { int n = arr.size(); val.resize(n); in.resize(n+1); out.resize(n+1); for(int i=0;i &vis) { vis[src] = 1; eTour.push_back(src); for(auto it : adj[src]) { if(!vis[it]) dfs(it, vis); } eTour.push_back(src); } void eulerTour() { vectorvis(val.size()); dfs(1, vis); for(int i = 0; i < eTour.size(); i++) { if(in[eTour[i]] == -1) in[eTour[i]] = i; else out[eTour[i]] = i; // cout< pathtozero() { int zerNode=valToInd[0]; queueq; q.push(1); vectorans; vectorparent(valToInd.size()+1,-1); while(!q.empty()) { int x=q.front(); q.pop(); if(x==zerNode) { while(parent[x]!=-1) { ans.push_back(x); x=parent[x]; } ans.push_back(1); reverse(ans.begin(),ans.end()); return ans; } else{ for(auto it:adj[x]){ parent[it]=x; q.push(it); } } } return ans; } void addEdge(int x, int y) { adj[x].push_back(y); // adj[y].push_back(x); } bool query(int mex,int node) { if(mex>=val.size())return 1; int l1=in[node]; int r1=out[node]; int l2=in[valToInd[mex]]; int r2=out[valToInd[mex]]; return (l1>l2&&r1 solve(int n, vector& val, vector> &c) { Tree tr(val); for(int i=0;ipathToZero=tr.pathtozero(); int i=1; vectormex(n,-1); for(int j=pathToZero.size()-1;j>=0;j--) { while(!tr.query(i,pathToZero[j])) { i++; } mex[pathToZero[j]-1]=i; } for(int i=0;i>n; vectorb(n); for(int i=0;i>b[i]; vector> c; for(int i=0;i>x>>y; vectora; a.push_back(x); a.push_back(y); c.push_back(a); } vectorans=solve(n,b,c); for(int i=0;i
 » 6 weeks ago, # |   +7 How will we do the question 2 if the nodes don't have distinct values and also the values ranges from 0 to 1e9?
•  » » 6 weeks ago, # ^ |   0 Values range won't affect much but they have to be distinct according to me.
 » 2 weeks ago, # |   0 Question 2Observation 1: If there is No zero ans will be 0 for allObservation 2: The nodes which occur in between from root to node which has zero value they will have MEX > 0Approach: Find node with 0 value (say NODE) and do dfs mark all values which are in the subtree of that node,use a variable (say mex = 0) that will store ans for this node. while mex is marked true as visited increase it and find first missing positive. now move NODE to parent[NODE] Do this while NODE != -1 class Solution { public: vector> adj; vector vis; void dfs(int curr, vector&nums){ vis[nums[curr]] = 1; for(int v : adj[curr]){ if(!vis[nums[v]]) dfs(v, nums); } } vector MexSubTree(vector& parent, vector& nums) { int n = parent.size(); int idx = -1; for(int i = 0; i < nums.size(); i++){ if(nums[i] == 0){ idx = i; break; } } vector ans(n, 0); if(idx == -1)return ans; adj.resize(n); vis.resize(n+2, false); int MEX = 0; for(int i = 1 ; i < n ; i++){ adj[parent[i]].push_back(i); } while(idx != -1){ dfs(idx, nums); while(vis[MEX]) MEX++; ans[idx] = MEX; idx = parent[idx]; } return ans; } };