Unacademy Hiring challenge [Debugging - Cpp - Q2]

What are the constraints ? over N

What , and I filled part time and 5 to 6 hrs . :frowning_face:

thanks manā€¦i need this :slight_smile:

1 Like

see @pastor :slight_smile:

Can someone share ISITSQRTā€™s solutionā€¦ I guess I missed something important in problem, even my bruteforce was not passing ? @vijju123

My 100 points 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 100005
 
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;

        for(int i=1;i<=n;i++){
            graph[i].clear();
            rev_graph[i].clear();
            visited[i]=false;
            visited2[i]=false;
            indegree[i]=0;
            represent_node[i]=0;
        }
 
        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();
            s.pop();
            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[x]]++;

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

can someone give the contest link

ended.

i know, but stillā€¦so i can see and try all problems of the contest. You may just give me all problem links, but the first option is easier

for now questions are not visible.

PAINT Problem - CodeChef isnā€™t this one of the questions tho?

NOPE

:disappointed_relieved:

Here is my solution.First of all for each type of query we need to find the maximum of a range.So for this part I used a sparse table which stores the maximum of each range.Now since the values of the arrays are distinct so it is always ensured that the maximum value occurs only once.So now what we can do is simply map the values of the arrays to index.Now for each type of query we just find the maximum element using sparse table and then do as specified in the problem.
Here is the code if you want to see:

        #include<bits/stdc++.h>
        #define ll long long
        #define f   first
        #define s   second
        #define pb          push_back
        #define mod        1000000007
        #define mod1       1000000009
        #define hell        998244353
        #define inf         1000000000000000000LL
        #define pi          3.14159265358979323
        //#define N           100005 
        const int N=100050;
        using namespace std;
        ll n,k,sum,q,res,m,val,ans;
        ll x,y;
        double p;
        ll xx[]={1,0,-1,0};
        ll yy[]={0,1,0,-1};
        ll st[N][25];
        ll mylog[N];
        void f()
        {
            mylog[1]=0;
            for(int i=2;i<N;i++) mylog[i]=mylog[i/2]+1;
        }
        void solve()    
        {   
            memset(st,0,sizeof(st));
            cin>>n>>q;
            vector<ll> v(n);
            map<ll,ll> hm;
            for(int i=0;i<n;i++) {cin>>x;hm[x]=i;st[i][0]=x;}
            for(int i=0;i<n;i++) cin>>v[i];
            for(int j=1;j<=25;j++)
            {
                for(int i=0;i+(1<<j)<=n;i++)
                    st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
            }
            while(q--)
            {
                int type;
                cin>>type;
                if(type==1)
                {
                    ll l,r,qt;
                    cin>>l>>r>>qt;
                    l--;r--;
                    ll id=mylog[r-l+1];
                    x=max(st[l][id],st[r-(1<<id)+1][id]);
                    //cout<<x<<"\n";
                    v[hm[x]]+=qt;
                }
                else
                {
                    ll x,y,qt,thr;
                    cin>>x>>y>>qt>>thr;
                    ll l,r;
                    y--;
                    l=max(0LL,y-x);
                    r=min(n-1,y+x);
                    ll id=mylog[r-l+1];
                    x=max(st[l][id],st[r-(1<<id)+1][id]);
                    if(x<thr || v[hm[x]]<qt) {cout<<"No purchase\n";}
                    else {cout<<hm[x]+1<<"\n";v[hm[x]]-=qt;}
                }
            }
        }
        int main()  
        {   ios_base::sync_with_stdio(false);
            cin.tie(0);cout.tie(0);
            int t=1;
            f();
            cin>>t;
             while(t--)
                solve();
            
        }

indegree[represent_node[i]++

This must be
indegree[represent_node[x]]++

link to contest?

1 Like

I used Segment Tree. Hereā€™s my solution

import java.math.*;
import java.io.*;
import java.util.*;

class Solution {
    static class SegmentTreeNode{
        public int max;
        public int l, r;
        public SegmentTreeNode left, right;
        public SegmentTreeNode(int l, int r) {
            this.l = l;
            this.r = r;
        }
    }
    static class SegmentTree{
        private static SegmentTreeNode root = null;
        int ar[];
        public SegmentTree(int ar[]) {
            this.ar = ar;
            root = buildTree(root, ar, 0, ar.length - 1);
        }
        public SegmentTreeNode buildTree(SegmentTreeNode n, int ar[], int l, int r) {
            if (n == null)
                n = new SegmentTreeNode(l, r);
            if (l < r) {
                int mid = (l + r) >> 1;
                n.left = buildTree(n.left, ar, l, mid);
                n.right = buildTree(n.right, ar, mid + 1, r);
                n.max = Math.max(n.left.max, n.right.max);
            }
            else if (l == r) {
                n.max = ar[l];
                n.left = null;
                n.right = null;
            }
            else
                return null;
            return n;
        }
        public int maxquery(int l, int r) {
            return max(root, l, r);
        }
        public int max(SegmentTreeNode n, int l, int r) {
            if (n == null) {
                return Integer.MIN_VALUE;
            }
            if (n.l >= l && n.r <= r) {
                return n.max;
            }
            if (n.l > r || n.r < l) {
                return Integer.MIN_VALUE;
            }
            return Math.max(max(n.left, l, r), max(n.right, l, r));
        }
    }
    public static void main(String[] args) throws Exception {
        InputReader in = new InputReader(System.in);
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        int tc = in.readInt();
        for (int t = 0; t < tc; t++) {
            int n = in.readInt();
            int q = in.readInt();
            int col[] = new int[n];
            long qan[] = new long[n];
            for (int i = 0; i < n; i++) {
                col[i] = in.readInt();
            }
            for (int i = 0; i < n; i++) {
                qan[i] = in.readInt();
            }
            SegmentTree segmentTree = new SegmentTree(col);
            Map<Integer, Integer> colShopMap = new HashMap<>();
            for (int i = 0; i < n; i++) {
                colShopMap.put(col[i], i);
            }
            for (int qc = 0; qc < q; qc++) {
                int type = in.readInt();
                if (type == 1) {
                    int l = in.readInt() - 1;
                    int r = in.readInt() - 1;
                    long qt = in.readLong();
                    int maxCol = segmentTree.maxquery(l, r);
                    int shopId = colShopMap.get(maxCol);
                    qan[shopId] += qt;
                }
                else {
                    int v = in.readInt();
                    int shop = in.readInt() - 1;
                    int l = Math.max(0, shop - v);
                    int r = Math.min(n - 1, shop + v);
                    int qt = in.readInt();
                    int thres = in.readInt();
                    int maxCol = segmentTree.maxquery(l, r);
                    if (maxCol >= thres) {
                        int shopId = colShopMap.get(maxCol);
                        if (qan[shopId] >= qt) {
                            qan[shopId] -= qt;
                            out.write(Integer.toString(shopId + 1));
                        }
                        else {
                            out.write("No purchase");
                        }
                    }
                    else {
                        out.write("No purchase");
                    }
                    out.newLine();
                }
            }
            out.newLine();
        }
        out.close();
    }
}
class InputReader {
    private boolean finished = false;

    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;

    public InputReader(InputStream stream) {
        this.stream = stream;
    }

    public int read() {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    public int peek() {
        if (numChars == -1)
            return -1;
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                return -1;
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar];
    }

    public int readInt() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public long readLong() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        long res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public String readString() {
        int length = readInt();
        if (length < 0)
            return null;
        byte[] bytes = new byte[length];
        for (int i = 0; i < length; i++)
            bytes[i] = (byte) read();
        try {
            return new String(bytes, "UTF-8");
        } catch (UnsupportedEncodingException e) {
            return new String(bytes);
        }
    }

    public static boolean isSpaceChar(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    private String readLine0() {
        StringBuffer buf = new StringBuffer();
        int c = read();
        while (c != '\n' && c != -1) {
            if (c != '\r')
                buf.appendCodePoint(c);
            c = read();
        }
        return buf.toString();
    }

    public String readLine() {
        String s = readLine0();
        while (s.trim().length() == 0)
            s = readLine0();
        return s;
    }

    public String readLine(boolean ignoreEmptyLines) {
        if (ignoreEmptyLines)
            return readLine();
        else
            return readLine0();
    }

    public BigInteger readBigInteger() {
        try {
            return new BigInteger(readString());
        } catch (NumberFormatException e) {
            throw new InputMismatchException();
        }
    }

    public char readCharacter() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        return (char) c;
    }

    public double readDouble() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        double res = 0;
        while (!isSpaceChar(c) && c != '.') {
            if (c == 'e' || c == 'E')
                return res * Math.pow(10, readInt());
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        }
        if (c == '.') {
            c = read();
            double m = 1;
            while (!isSpaceChar(c)) {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, readInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                m /= 10;
                res += (c - '0') * m;
                c = read();
            }
        }
        return res * sgn;
    }

    public boolean isExhausted() {
        int value;
        while (isSpaceChar(value = peek()) && value != -1)
            read();
        return value == -1;
    }

    public String next() {
        return readString();
    }

    public boolean readBoolean() {
        return readInt() == 1;
    }
}

i asked 'em too, but they havenā€™t given me one yet

Can I know when and where did this challenge took place

If I am not wrong they invited 4 stars and above for the challenge. The problems are not visible now, so link of the contest is of no use. It happened today from 4pm to 7pm IST.