### codenationtest's blog

By codenationtest, history, 9 months ago, , Codenation test was conducted on Hackerrank on 15th July. There were 3 questions in the hiring contest.

Q1) Given a NxM (NxM <= 1e5) matrix with each cell having a value mod(Aij) <= 1e9. Job is to rank each element by the following rules:

1) Ranks start from 1.
2) Equal elements in the same row or same column should have the same rank.
3) Greater elements in the same row or same column should have a greater rank.
4) Maximum Rank should be minimized.

Print the final rank matrix.

Q2) N employees are given, you have to divide them into teams of two. If n is odd the last person will form a one man team. Problem is all employees are not compatible with each other. and if both are compatible with each other then only a team can be formed.

Aij ='C' if employee i is compatible with employee j, Aij = 'X' otherwise.
Aii ='C' if employee i can work as one man team, Aii = 'X' otherwise.

find the maximum no of valid teams that can be formed. constraints: T <=20, N<=18.

Q3) Given a Directed graph with N nodes and M edges. each node has a population Ai. you have to open outlets in some or all nodes following the conditions in decreasing priority:

1) Every Node must have access to some outlet either directly or through some path.
2) Maximize the average sales per outlet. sales are linearly proportional to the no of people that visit that
location. Average sales per outlet = (sum of all outlet sales)/(total number of outlets)
3) Minimize the number of outlets.

Print how many outlets will you open and in which node. Constraints : T <= 100, N <= 1e3, M <= min( 1e5, N(N-1)), Ai <= 1e3. Comments (29)
 » Auto comment: topic has been updated by codenationtest (previous revision, new revision, compare).
 » I see the test has been cancelled. How did you get the questions?
•  » » The off-campus test was canceled. But for specific colleges, the test was held as per the usual schedule.
•  » » » there will happen any offcampus test in nearby future or not
 » Do you have solutions to those questions?
 » 9 months ago, # | ← Rev. 2 →   2)for this we can simply do dp with bitmasking by updating 2 bits at a time,also for case of odd numbers we can update all dp state with one set bit to 1 initially. 3)i guess we can calculate total no. of connected components in the graph and any one point from each component can be taken as position for outlet though didnt do that in contest :')but i think this is the correct approch.u can use dsu for this
•  » » 9 months ago, # ^ | ← Rev. 2 →   In 3rd question, to maximize the 'average' number of sales and to minimise the number of outlets, isn't it always better to choose the most populated node(only one) in each connected component and not 'any random node' as you said ?
•  » » » if they are saying every node should have a rechable outlet. i assume total sales of the outlet is total population of the conected component it is in and no.of outlets ofc is no. of components. i dont exactly remember the sample test possibly that could clarify the dilemma
•  » » » We need to output only the number of outlet. So the answer would be number of connected components.
•  » » » what you are saying is true, may be the question is asking something different or some different formula for average mean , also when edges are directed , talking about connected components doesn't make sense, so let's think of strongly connected components so now after we find SCC(strongly connected components) treat each group of SCC as a single node , so finally we will get a DAG(directed acyclic graph) where each node is a SCC. for eg: if suppose our final dag comes out to be a chain like structure with edges pointing in same direction it's better to place the outlet at the tail node(outdegree=0), if u place outlet at every node in a single SCC node the mean decreases .so i feel like we should be placing outlet's at places where the outdegree of that node is zero , just return the count of them.Iam not sure of this because i have no proof that this is maximum mean case, because sometimes placing an extra outlet in outdegree zero node increases the numerator of average sales high which overcomes the denominator and finally increasing the mean.
•  » » » » 9 months ago, # ^ | ← Rev. 6 →   If we call the nodes in this DAG 'SCC nodes', each SCC node having an outdegree of 0 must contain atleast 1 outlet due to the first condition. Among the nodes in that SCC, it is optimal to make a node with the largest population an outlet.If an SCC node's outdegree is not 0, it can access an SCC node whose outdegree is 0. So no other nodes are required to be made an outlet due to the first condition alone.Among the nodes which aren't outlets, go on making a node with the largest population an outlet as long as it increases the average.
 » Solution to 1st Question of matrix.. it may be right.. https://ideone.com/Bs911f initialize 2d matirx with -ve infinity. first of all I sorted the 2d Matrix in ascending order while maintaining index then, suppose the first element is (i,j) pos in sorted then,find max rank in that ith row and in jth col then assign the maximum rank+1,if if element is equal to prev element then asign previous rank.. nlogn complexity with segment Tree.
•  » » 9 months ago, # ^ | ← Rev. 5 →   we can solve it in another way using binary search . firstly do a co-ordinate compression to map those values inside the matrix to some small set of values then we will build a graph over the relation < , for each row/column after we sort individually&independently then we add edges to this directed graph as follows if u
•  » » » Can you please explain your solution more clearly, especially the co-ordinate compression part? Thanks in advance.
•  » » » » as matrix values can be around 1e9 , we do co-ordinate compression(google it ) , so that we map those large values to small values , now why should we do it , because to keep our graph vertices small. around 1e5.
•  » » » What about this case? 2 5 2 3 1 1 1 1 1 1 3 4 (IMHO, the optimum cost is here 3.) I haven't thought much about this but I imagine that the correct solution should (in a clever way) create a graph over all cells of the matrix and not over the distinct values.
•  » » Try some of these cases to test your program:2 35 1 32 4 22 31 1 32 3 33 21 76 52 6
•  » » this do not work for matrix like 7 8 6 6 10 3
 » someone plzz explain 2nd qst approach
 » 9 months ago, # | ← Rev. 3 →   My Approach to ques_3 Step 1 — Create an adjacency list of the graph where for each directed edge (u,v), you have an edge from v to u. Step 2 — Place an outlet for all the nodes whose oudegree is 1 (size of adj[node] is 0) Step 3- Compute the avg of the currently placed outlets based on the number of people from that node where outlet is placed. Let it be alpha. Step 4 — Now for all the nodes without any outlet, sort their sales in descending order and traverse linearly till the avg is increasing. Compute the new avg taking into account the increase in the sales for placing outlet. Step 5 — Output the resultant number I couldnt solve it during the contest:/ but i believe this should work.
 » 9 months ago, # | ← Rev. 2 →   The second problem can be solved using bitmask dp.Construct an undirected graph $n$ vertices and edges $(i, j) \in E$ $\text{iff}$ $i \neq j, A[i][j] = A[j][i] = \mathtt{C}$Let's assume $n$ is even.We have to count the number of perfect matchings for this graph.Define $\mathtt{dp}[mask]$ as the number of perfect matchings for the subgraph $mask$.$\mathtt{dp} = 1$$\mathtt{dp}[mask] = \sum{\mathtt{dp}[mask - (i, j)]}$ , such that $j \in mask, (i, j) \in E, i$ is the first set bit in $mask$ When $n$ is odd, simply iterate over each vertex assuming it to be single, and solve for even case for the rest vertices.EditIt seems like I understood the problem differently (that every employee of N must belong to some team for the distribution to be valid).If we can select any employees, then the problem is just to find the maximum matching in the above graph, which can be solved using Blossom Algorithm.
•  » » have u solved the problem or just giving possible hints?
 » I couldn’t log in to the test that day but here is my solution for Project Allocation https://pastebin.com/kisKNzEx . Explanation: dp[i][j][k] where maximum groups till ith person with current status as j and k = 0 => no single group yet, 1 => one single group.
»
9 months ago, # |
Rev. 2

//I think this can be solution to question 1, can anybody confirm please

# include<bits/stdc++.h>

using namespace std;

int main() { int n,m; cin>>n>>m;

int arr[n][m];
map<int,vector<pair<int,int>>> ma;

for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>arr[i][j];
pair<int,int> p(i,j);
ma[arr[i][j]].push_back(p);
//vec.push_back(arr[i][j]);
}
cout<<endl;
}

set<int> row[n];
set<int> column[m];

int rankMat[n][m]={0};
int flag=0;
for(auto it: ma)
{
flag++;
list<pair<int,int> > li;
int maxm=1;
for(auto itt=it.second.begin(); itt!=it.second.end(); itt++)
{
pair<int,int> p = *itt;
int a,b;
a=p.first;
b=p.second;
li.push_back(make_pair(a,b));
if(flag==1)
{
maxm=1;
continue;
}
if(row[a].empty() && column[b].empty())
{
maxm=max(maxm,1);
continue;
}
else if(row[a].empty())
{
auto x= column[b].end();
x--;
maxm=max(maxm,*x+1);
}
else if(column[b].empty())
{
auto x= row[a].end();
x--;
maxm=max(maxm,*x+1);
}
else
{
auto x1 = row[a].end();
x1--;
auto x2 = column[b].end();
x2--;
maxm=max(maxm,max(*x1+1,*x2+1));
}
}

for(auto itt=li.begin(); itt!=li.end(); itt++)
{
pair<int,int> p=*itt;
int a=p.first, b=p.second;
rankMat[a][b]=maxm;
row[a].insert(rankMat[a][b]);
column[b].insert(rankMat[a][b]);
}
}
for(int i=0; i<n;i++)
{
for(int j=0;j<m;j++)
cout<<rankMat[i][j]<<" ";
cout<<endl;
}


}

•  » » I have read and kind of got an intuition what you are doing but can you please explain clearly what the maxm is actually? What I have understood from your code is — you are iterating the whole matrix and for every occurrence of a[i][j] in the matrix and you are storing maxm=max(maxm, "something"); and after that, you are storing maxm in rankMat. Can you please explain the "something" part in your code that I have written about above? Thank you.
•  » » » 9 months ago, # ^ | ← Rev. 2 →   For the sorted vector, it is clear that the smallest element will have rank 1. I have marked every occurrence of an element with same rank. For smallest element(say x)and all its occurrences, rank is 1. For second greater element (say y) , rank may be 2 or 1. 2 will be in the case if there is at least one row or column which contains y also. Otherwise, if for every y, we do not have any row or column containing x, then its rank will be 1. Therefore, maxm is used to get this value. In this way, i am continuing till the end. ThanksEdit: That "something" is the maximum rank given in that row and column to which the current element belongs.
•  » » » » Yes, I have kind of used similar approach but the problem occurs when we have already updated some elements rank but due to the rules we need to follow we need to backtrack to that previous element and change it again. This makes the complexity high. I tried to use segment tree for fast update but didn't get the solution correct.
•  » » » » » Can you please tell any test case where the rank needs to be changed? As of i know, we traverse the elements in sorted order, so the rank is being minimized for every element. It would be helpful if you could give any such case.
 » did anyone receive interview calls for hiring ? / when will the results be declared ?