can you explain a bit more please with example?
Yup, the state is dp[mask] = Number of teams which can be formed if people are chosen according to mask (‘1’ means that person is chosen, ‘0’ means not chosen), and for transition, iterate over pair of nodes, for every pair, set both bits in mask, increase number of projects if compatible and try remaining mask. Corner case can be handled at the end if only one bit is not set.
Not sure about Time complexity as at every child, two bits are flipped, and each transition except last takes N^2 iterations.
Not participated, not submitted.
1 Like
Here is my Solution , to the first Question. I believe its correct , please have a look on it , if any error please mention.
It first assign 1 to all occurrence of smallest number, two arrays maintain the label we have assigned to just smallest number if present in a particular row or column. Two other arrays maintain the label we have assigned in a row or column for occurrence of same element, as at last all the labels will be equal to maximum of all the labels assigned to same elements. (Sort is done initially.)
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
typedef struct
{
ll val;
ll r;
ll c;
ll ans;
}node;
bool cmp(node a, node b)
{
return a.val < b.val;
}
int main()
{
int n,m;
cin>>n>>m;
int ele = n*m;
node dp[ele];
ll row[n] = {-1};
ll col[m] = {-1};
ll ans[n][m];
ll trow[n] = {-1};
ll tcol[m] = {-1};
for(int j = 0 ; j < ele ; j++)
{
cin>>dp[j].val;
dp[j].r = j/m;
dp[j].c = j%m;
dp[j].ans = -1;
}
sort(dp, dp + ele , cmp);
for(int i = 0 ; i < ele ; i++)
{
if(i == 0)
{
ll v = dp[0].val;
while(dp[i].val == v)
{
row[dp[i].r] = 1;
col[dp[i].c] = 1;
dp[i].ans = 1;
i++;
}
i--;
}
else
{
ll v = dp[i].val;
int j = i;
int k = i;
while(dp[i].val == v)
{
int ma = max(row[dp[i].r],col[dp[i].c]);
if(ma == -1) {
dp[i].ans = 1;
trow[dp[i].r] = max(trow[dp[i].r],dp[i].ans);
tcol[dp[i].c] = max(tcol[dp[i].c],dp[i].ans);
trow[dp[i].r] = max(trow[dp[i].r],tcol[dp[i].c]);
tcol[dp[i].c] = trow[dp[i].r];
}
else
{
dp[i].ans = ma + 1;
trow[dp[i].r] = max(trow[dp[i].r],dp[i].ans);
tcol[dp[i].c] = max(tcol[dp[i].c],dp[i].ans);
trow[dp[i].r] = max(trow[dp[i].r],tcol[dp[i].c]);
tcol[dp[i].c] = trow[dp[i].r];
}
i++;
}
i--;
while(dp[j].val == v)
{
dp[j].ans = max(dp[j].ans,max(trow[dp[j].r],tcol[dp[j].c]));
j++;
}
while(dp[k].val == v)
{
row[dp[k].r] = max(row[dp[k].r],dp[k].ans);
col[dp[k].c] = max(col[dp[k].c],dp[k].ans);
trow[dp[k].r] = -1;
tcol[dp[k].c] = -1;
k++;
}
}
}
for(int i = 0 ; i < ele ; i++)
{
ans[dp[i].r][dp[i].c] = dp[i].ans;
}
for(int i = 0 ; i < n ; i++)
{
for(int j = 0 ; j < m ; j++)
cout<<ans[i][j]<<" ";
cout<<endl;
}
}Preformatted text
1 Like
If for each bitmask , we iterate over all the pairs , then probably it will result in time out. Here we also have T = 20 test cases and then time complexity will be near to O(10^10) , which may result in timeout, can there be any approach to solve it in O(T*(2^N)*N).
Can you run this test case on your code:
-1 48 39 0
30 47 0 229
I think the correct output is :
1 4 3 2
2 3 1 4
Is it?
Thanks.
Yes, it is showing same output.
I was sure I had seen Elys with Matrix earlier. And it turns out it is the follow up from here: https://leetcode.com/discuss/interview-question/326564/google-onsite-interview-compress-2d-array
2 Likes
Here is a possible solution to Elys With matrix:
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m;
scanf("%d %d",&m,&n);
printf(“Input matrix:\n”);
vector< vector > v(m, vector (n,0));
set myset;
vector< set > row(m, myset);
vector< set > col(n, myset);
for(int i =0;i<m;i++)
{
for(int j =0;j<n;j++)
{
scanf("%d",&v[i][j]);
row[i].insert(v[i][j]);
col[j].insert(v[i][j]);
}
}
for(int i =0;i<m;i++)
{
for(int j = 0;j<n;j++)
{
v[i][j] = 1 + max( distance(row[i].begin(), row[i].find(v[i][j])), distance(col[j].begin(), col[j].find(v[i][j])) );
}
}
printf(“Resultant matrix:\n”);
for(int i =0;i<m;i++)
{
for(int j = 0;j<n;j++)
{
cout<<v[i][j]<<" “;
}
cout<<”\n";
}
return 0;
}
is it AC ? I thought we need graph for this que
to all sharing solutions. please mention if you got 100 points or how many points
wow it was toposort 
Nice que 
1 Like
Were you and your friends able to pass any number of test cases in the remaining two questions? @anon61866802
Can you please write down the code or atleast the pseudo code please?
Naah… Those were comparatively tougher than this one. So we didn’t even try solving them 
My solution to the project allocation.please give feedback if its the right approach.
def calculate(m,t,count=0):
if(len(m) < 2):
if(len(m)==1):
b=m[0][-1]
if m[0][b]=='S':
count=count+1
return count
#return count_max
temp=t
q=None
#r=0
for j in range(int(employee)):
if m[0][j] == 'S':
if(j is not m[0][-1]):
t=t-2
for n in range(temp):
if m[n][-1]==j:
q=n
print("q=",q)
if q is None:
count=0
continue
m2 = [[0 for i in range(int(employee+1))] for j in range(t)]
else:
t=t-1
m2=[[0 for i in range(int(employee+1))] for j in range(t)]
count=count+1
#print(count)
print(m2)
L=0
for k in range(1,temp):
if k == q:
pass
else:
m2[L]=m[k]
L=L+1
print(m2)
#if count >= count_max:
#count_max=count
#print(count_max)
count=calculate(m2,t,count)
counts.append(count)
#r=r+1
count=0
t=employee
# return count_max
counts=[]
test=int(input("enter number of test cases"))
while(test>0):
count_max=0
employee=int(input("enter"))
matrix=[['x' for i in range(employee+1)]for j in range(int(employee))]
for i in range(int(employee)):
matrix[i]=list(input())+[i]
#for i in range(int(employee)):
#matrix[i][-1]=i
#print(matrix)
calculate(matrix,employee)
#count_max=calculate(matrix,count_max,employee)
print("\n")
test=test-1
res=[i for i in counts if i]
print(max(res))I surfed about codenation CNIL Test and found a blog that has question asked in test along with question asked in other MNCs too. Visit
1 Like
on which platform ,it was hosted?
Hacker rank
How many questions needed to be done in the test, to get an interview call?