Unacademy Hiring challenge [Debugging - Cpp - Q2]

[ssrivastava990]

#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 ?

[kk2_agnihotri]

How many you are able to solve?

[pastor]

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

[ssrivastava990]

3 , all coding , none debugging,

[kk2_agnihotri]

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

[pastor]

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

[ssrivastava990]

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;
}

[knightknight]

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?

[pastor]

nobody asked

[desi_yoddha]

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.

[rathi_22]

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

[erfaniaa]

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;
}

[ssrivastava990]

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

[l_returns]

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

[erfaniaa]

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

[ssrivastava990]

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

[knightknight]

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

[ssrivastava990]

wait for sometime , it will update .

[knightknight]

Ok Brooo waiting

[amit_1112]

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