Unacademy Hiring challenge [Debugging - Cpp - Q2]

#include<bits/stdc++.h>

using namespace std;

#define ll long long int
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007
#define MAX_N 10001

vector < int > graph[MAX_N], rev_graph[MAX_N];

bool visited[MAX_N] = {0};
bool visited2[MAX_N] = {0};

int indegree[MAX_N] = {0};
int represent_node[MAX_N] = {0};

void dfs(int node, stack < int > s) {
visited[node] = true;

for (int x: graph[node])
if (!visited[x])
dfs(x, s);

s.push(node);
}

int dfs2(int node, int representative) {
visited2[node] = true;
represent_node[node] = representative;

for (int x: rev_graph[node])
if (!visited2[x])
dfs2(x, representative);
}

int main() {
FIO;
int t, n, m, k, i, j, ans;
cin >> t;
while (t--> 0) {
cin >> n >> m;

while (m--> 0) {
cin >> j >> k;
graph[j].push_back(k);
rev_graph[k].push_back(j);
}

stack < int > s;

for (i = 1; i < n; i++)
if (!visited[i])
dfs(i, s);

while (s.size() > 0) {
j = s.top();

if (!visited2[j])
dfs2(j, j);
}

for (i = 1; i < n; i++)
for (int x: graph[i])
if (represent_node[i] != represent_node[x])
indegree[represent_node[i]]++;

for (i = 1; i < n; i++)
if (represent_node[i] = i)
if(indegree[i] = 0)
ans++;
cout << ans << "\n";
}
return 0;
}

How can we do this problem I think somethink like topological sort but not able to solve.
Anyone solved ?

1 Like

How many you are able to solve?

i was also not able to solve this tho this is standard tarjan algorithm

3 , all coding , none debugging,

2 Likes

I was also thinking something like that but not able to solve

2 coding 200 marks and in other two i got 186 marks and 1 debugging

1 Like

My solution for paint -

bool check(lli a[] , lli n , lli sum , lli k)
{
lli crsum=0;
loop(i,k)
crsum += (a[i]+(i+1)*k);
if(crsum<=sum)
return true;
for(lli i=k;i<n;i++)
{
crsum -= (a[i-k] + (i-k+1)*k);
crsum += (a[i]+(i+1)*k);
if(crsum<=sum)
return true;
}
return false;
}

int main(){
fastio
lli t=1;
//cin>>t;
while(t--) {
lli n,s;
cin>>n>>s;
lli a[n];
scanarr(a,n);
lli l=1;
lli r = n;
lli ans=0;
while(l<=r)
{
lli mid = (l+r)/2;
if(check(a,n,s,mid))
{
ans = mid;
l = mid+1;
}
else
{
r = mid-1;
}
}
print(ans);
}
return 0;
}
1 Like

I submitted a code at 6:59 and got AC after the contest ended ! My score has not been updated since ?? Will it not be marked if some one knows about this scenario?

1 Like

1 Like

Bro there are minute errors in this problem like stack s has to be passed by reference, and in the while loop with condition while(s.size()>0)… s.pop() statement was missing. The values of all the globally declared arrays vectors and variables need to be reassigned in every test case, since it was 1 based indexing n has to be included and some small errors like use of ‘’=’’ in place of “==” . I managed to get 80 points in it. Doesn’t understand why I didn’t get 100.

Make strongly connected components and any component which has zero indegree needs an edge from city N+1

7 Likes

I’ve got 80 points with this code:

#include<bits/stdc++.h>

using namespace std;

#define ll long long int
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007
#define MAX_N 100001

vector < int > graph[MAX_N], rev_graph[MAX_N];

bool visited[MAX_N] = {0};
bool visited2[MAX_N] = {0};

int indegree[MAX_N] = {0};
int represent_node[MAX_N] = {0};

void dfs(int node, stack < int > &s) {
visited[node] = true;

for (int x: graph[node])
if (!visited[x])
dfs(x, s);

s.push(node);
}

void dfs2(int node, int representative) {
visited2[node] = true;
represent_node[node] = representative;

for (int x: rev_graph[node])
if (!visited2[x])
dfs2(x, representative);
}

int main() {
FIO;
int t, n, m, k, i, j, ans;
cin >> t;
while (t--> 0) {
ans=0;
cin >> n >> m;

while (m--> 0) {
cin >> k >> j;
graph[j].push_back(k);
rev_graph[k].push_back(j);
}

stack < int > s;

for (i = 1; i <= n; i++)
if (!visited[i])
dfs(i, s);

while (s.size() > 0) {
j = s.top();

if (!visited2[j])
dfs2(j, j);
s.pop();
}

for (i = 1; i <= n; i++)
for (int x: graph[i])
if (represent_node[i] != represent_node[x])
indegree[represent_node[i]]++;

for (i = 1; i <= n; i++)
if (represent_node[i] == i)
if(indegree[i] == 0)
ans++;
cout << ans << "\n";
for (i = 1; i <= n; i++) {
visited[i]=visited2[i]=indegree[i]=represent_node[i]=0;
graph[i].clear();
rev_graph[i].clear();
}
}
return 0;
}
2 Likes

No issues man , I just shared if somebody wants he/she will see …

If it’s submitted successfully. It will be marked for sure.

1 Like

Does anyone know how can we know our final rank?
When do they want to publish the result?

Hey , u r the author of this problem please share approach or editorial ?

My score will update ?? It is still showing 400 it should be 500 by now

wait for sometime , it will update .

1 Like

Ok Brooo waiting

1 Like

Thanks for this.Now I got my mistake.I forgot to clear arrays after each test case that’s why I was getting WA .