This is the third part of the series on online assessments that I witnessed during the season of 2024. The previous parts can be found here and here.

• Phone Pe
• Oracle
• Confluent
• Amazon
• Seimens
• Walmart
• Winzo
• Typeface
• Media.net
• Samsung Research Institute Bangalore (SRIB)

Phone Pe

Other Campus Questions

1. You are given a tree with $n$ nodes. Each node has $arr[i]$ amount of apples on it. You start walking from the node $1$, and on the walk you randomly choose any unvisited node connected to the current node with equal probability. You can only visit each node once. You can eat the apples on the node you are currently on. What is the expected number of apples you will eat?

   Solution

   We will perform a single DFS to calculate the same. The time complexity of the same would be $O(n)$.

   double dfs(int u, int p, vector<vector<int>> &g, vector<int> &arr) {
       int cntChild = 0;
       for (int v : g[u]) {
           if (v == p) continue;
           cntChild++;
       }
   
       if (cntChild == 0)
           return arr[u];
   
       double ans = arr[u], p = 1.0 / (double)cntChild;
       for (int v : g[u]) {
           if (v == p) continue;
           ans += p * dfs(v, u, g, arr);
       }
   
       return ans;
   }
   
   int main() {
       int n;
       cin >> n;
   
       vector<int> arr(n);
       for (int i = 0; i < n; i++) {
           cin >> arr[i];
       }
   
       vector<vector<int>> g(n);
       for (int i = 0; i < n - 1; i++) {
           int u, v;
           cin >> u >> v;
           u--, v--;
           g[u].push_back(v);
           g[v].push_back(u);
       }
   
       cout << fixed << setprecision(10) << dfs(0, -1, g, arr) << endl;
   }

2. There are $n$ numbers of a board. In one operation, you will pick two numbers $x$ and $y$ from the board, erase them and add the following number back to the board:

   • $x - y$ if both $x$ and $y$ have the same parity.
   • $x + y$ if both $x$ and $y$ have different parity.

   Calculate how many different final numbers can be present on the board.

   Constraints:

   • $1 \leq n \leq 50$
   • $1 \leq a_i \leq 100$

3. There is a contest where two flags have been placed among checkpoints on the map of Haven. Checkpoints are connected by $m$ roads, it is possible that there are checkpoints between which no path exists, meaning there are no roads connecting them. You are given a checkpoint $a$ where you will start your journey, and you have to collect both flags, placed at checkpoints $b$ and $c$ in order ($b$ first and then $c$). You can pass through checkpoints more than once. However, you have to pay a price to use the road, so if someone goes along a road then every time he should pay the price for that road. You are given an array of costs of size $m$. You have to distribute prices such that each price of the road corresponds to only one road, so that the cost of collecting both flags will be minimal and hence win the contest. You cannot rearrange prices after the start of the contest. It is guaranteed that there are no self loops or multiple edges in the graph.

   Constraints:

   • $1 \leq n, m \leq 10^5$
   • $1 \leq a, b, c \leq n$
   • $1 \leq cost_i \leq 10^9$

4. Raju works for PhonePe and needs to deliver QR codes to Vanous merchants in a city laid out as an inom grid, Each shop in the grid requires a certain number of QR codes. Raju starts his journey at the top-left corner of the grid $(0,0)$ and needs to reach the bottom-right corner $(n-1, m-1)$. He can only move right or down at any step. Raju wants to distribute the maximum number of QR codes in a single commute. But there’s a twist, To assist a merchant more efficiently Raju chooses to double the number of QR codes for one specific merchant along his path. However, he can only do this for one shop in his entire Journey. Your task is to help Raju determine the maximum number of QR’s he would need on his way to the destination, Help considering the option to double the value of exactly one cell.

   Constraints:

   • $1 \leq n, m \leq 10^3$
   • $1 \leq a_{ij} \leq 10^3$
   Solution

   int main()
   {
       int Y, X;
       cin >> Y >> X;
   
       vector<vector<int>> g(Y, vector<int>(X));
       for (int i = 0; i < Y; i++)
           for (int j = 0; j < X; j++)
               cin >> g[i][j];
   
       long long dp[Y][X][2];
       memset(dp, 0, sizeof(dp));
   
       dp[0][0][0] = g[0][0];
       dp[0][0][1] = g[0][0] * 2;
   
       for (int y = 0; y < Y; y++)
           for (int x = 0; x < X; x++)
           {
               if (x != 0)
               {
                   dp[y][x][0] = max(dp[y][x][0], dp[y][x - 1][0] + g[y][x]);
                   dp[y][x][1] = max({
                       dp[y][x][1],
                       dp[y][x - 1][1] + g[y][x],
                       dp[y][x - 1][0] + g[y][x] * 2,
                   });
               }
   
               if (y != 0)
               {
                   dp[y][x][0] = max(dp[y][x][0], dp[y - 1][x][0] + g[y][x]);
                   dp[y][x][1] = max({
                       dp[y][x][1],
                       dp[y - 1][x][1] + g[y][x],
                       dp[y - 1][x][0] + g[y][x] * 2,
                   });
               }
           }
   
       cout << dp[Y - 1][X - 1][1] << endl;
   }

5. To ensure seamless transactions, PhonePe needs to optimize its server network to minimize communication costs across these locations You are given a network of $N$ machines, which can either be server machines or client machines, and $M$ directed, weighted edges representing the network cost to travel from one machine to its neighbor machine. If a path exists from one machine to another, then network cost is defined as the sum of edge weights via that path. Your task is to determine the minimum sum of network cost to reach all machines (client and server machines) from any server. Additionally, each client machine can be upgraded to a server machine at a given one-time cost. This means the number of server machines will increase by $1$, but with additional cost.

   • The cost to reach itself for a client machine with server capabilities is zero since reaching itself needs no edge traversal.
   • The cost to reach a server machine from itself is zero.

   Input Format:

   • An integer $N$ representing the total number of machines. Machines are labeled from $1$ to $N$
   • An integer $C$ representing the total number of client.
   • $machines$: A list of integers containing client machine nodes.
   • An integer $S$ representing the total number of server machines.
   • A list of integers containing server machine nodes.
   • An integer $M$ representing the number of directed, weighted edges.
   • A list of $M$ tuples $(u,v,w)$, where $u$ is the starting machine, $v$ is the destination machine, and $w$ is the network cost to travel from $u$ to $v$.
   • An integer $K$ representing the number of upgradable client machines
   • A $K \times 2$ size two dimensional integer list $A$, where $A[i][0]$ denotes client machine node and $A[i][1]$ denotes upgradation cost to have server capabilities.

   Return the minimum network cost sum. Return $-1$ if it is not possible to reach all machines. Since the answer can overflow, you need to return the answer modulo $(10^6+7)$.

   Constraints:

   • $1 \leq N \leq 100$
   • $0 \leq M \leq N^2$
   • $1 \leq u, v \leq N$
   • $0 \leq w \leq 10^6$
   • $0 \leq k \leq 10$
   • $1 \leq A[i][0] \leq 100$
   • $0 \leq A[i][1] \leq 10^6$
   Solution

   We will use a bitmask on the upgradable servers and a multi-source Dijkstra to solve this problem. The time complexity of the solution would be $O(2^k \cdot (N + M) \log N)$.

   1
   int main()
   2
   {
   3
       int n;
   4
       cin >> n;
   5
   
   6
       // Client -> 1, Server -> 2
   7
       vector<int> arr(n + 1, 0);
   8
   
   9
       int c;
   10
       cin >> c;
   11
       for (int i = 0; i < c; i++)
   12
       {
   13
           int x;
   14
           cin >> x;
   15
           arr[x] = 1;
   16
       }
   17
   
   18
       int s;
   19
       cin >> s;
   20
       for (int i = 0; i < s; i++)
   21
       {
   22
           int x;
   23
           cin >> x;
   24
           arr[x] = 2;
   25
       }
   26
   
   27
       vector<vector<pair<int, int>>> g(n + 1);
   28
       int m;
   29
       cin >> m;
   30
       for (int i = 0; i < m; i++)
   31
       {
   32
           int u, v, w;
   33
           cin >> u >> v >> w;
   34
           g[u].push_back({v, w});
   35
       }
   36
   
   37
       int k;
   38
       cin >> k;
   39
       vector<vector<int>> A(k, vector<int>(2));
   40
       for (int i = 0; i < k; i++)
   41
           cin >> A[i][0] >> A[i][1];
   42
   
   43
       long long ans = 1e18;
   44
   
   45
       for (int mask = 0; mask < (1 << k); mask++)
   46
       {
   47
           long long curCost = 0;
   48
   
   49
           vector<long long> dist(n + 1, 1e18);
   50
           priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
   51
   
   52
           // Add all the original servers
   53
           for (int i = 1; i <= n; i++)
   54
               if (arr[i] == 2)
   55
               {
   56
                   dist[i] = 0;
   57
                   pq.push({0, i});
   58
               }
   59
   
   60
           // Add all the new servers
   61
           for (int i = 0; i < k; i++)
   62
               if (mask & (1 << i))
   63
               {
   64
                   dist[A[i][0]] = 0;
   65
                   pq.push({0, A[i][0]});
   66
                   curCost += A[i][1];
   67
               }
   68
   
   69
           while (!pq.empty())
   70
           {
   71
               auto [d, u] = pq.top();
   72
               pq.pop();
   73
   
   74
               if (dist[u] < d)
   75
                   continue;
   76
   
   77
               for (auto [v, w] : g[u])
   78
                   if (dist[v] > dist[u] + w)
   79
                   {
   80
                       dist[v] = dist[u] + w;
   81
                       pq.push({dist[v], v});
   82
                   }
   83
           }
   84
   
   85
           bool valid = true;
   86
           for (int i = 1; i <= n; i++)
   87
               if (arr[i] == 1)
   88
               {
   89
                   if (dist[i] == 1e18)
   90
                   {
   91
                       valid = false;
   92
                       break;
   93
                   }
   94
                   curCost += dist[i];
   95
               }
   96
   
   97
           if (valid)
   98
               ans = min(ans, curCost);
   99
       }
   100
   
   101
       if (ans == 1e18)
   102
           ans = -1;
   103
       else
   104
           ans %= ((long long)1e6 + 7);
   105
   
   106
       cout << ans << endl;
   107
   }

6. There are houses numbered from $1$ to $n$. Alice is intially at house $x$, and Bob is at house $y$. In one second, they can either move one house to the left or one house to the right. What is the minimum time they need to visit all the houses atleast once? There are $t$ testcases in one test file.

   Constraints:

   • $1 \leq t \leq 10^5$
   • $1 \leq n \leq 10^9$
   • $1 \leq x, y \leq n$
   Solution

   1
   bool check(int time, int n, int x, int y) {
   2
       int cnt1 = x + max(0, time - 2 * (x - 1));
   3
       cnt1 = max(cnt1, (time + x + 1)/2);
   4
   
   5
       int cnt2 = max(n - y + 1 + max(0, time - 2 * (n - y)));
   6
       cnt2 = max(cnt2, n - (n + y - time + 1)/2 + 1);
   7
   
   8
       return cnt1 + cnt2 >= n;
   9
   }
   10
   
   11
   void solve() {
   12
       int n, x, y;
   13
       cin >> n >> x >> y;
   14
   
   15
       if (x > y)
   16
           swap(x, y);
   17
   
   18
       int l = max(x - 1, n - y), r = 2 * n;
   19
       int ans;
   20
       while (l <= r) {
   21
           int m = l + (r - l) / 2;
   22
           if (check(m, x, y, n)) {
   23
               ans = m;
   24
               r = m - 1;
   25
           } else {
   26
               l = m + 1;
   27
           }
   28
       }
   29
   
   30
       cout << ans << endl;
   31
   }
   32
   
   33
   int main() {
   34
       int t;
   35
       cin >> t;
   36
   
   37
       while (t--)
   38
           solve();
   39
   }

7. There is a country with $n$ cities and $n$ directed edges between them. It is desired to reorient the edges so that every city is reachable from every other city. Figure out the minimum cost to do the same. A city has atmost $2$ edges in this nation. The cost of reversing a directed edge is equal to the weight of the edges. It is gauranteed that a solution always exists for the provided setting.

   Constraints:

   • $1 \leq n \leq 10^5$
   • $1 \leq a_i \leq 10^9$
   Solution

   Under the given conditions, it can be seen that the final layout with be that of a loop. Thus we just need to figure out the minimum cost to make a loop. The time complexity of the solution would be $O(n)$.

   1
   int main() {
   2
       int n;
   3
       cin >> n;
   4
   
   5
       vector<vector<int>> g(n);
   6
       map<pair<int, int>, int> cost;
   7
       for (int i = 0; i < n; i++) {
   8
           int u, v, w;
   9
           cin >> u >> v >> w;
   10
           u--, v--;
   11
           g[u].push_back(v);
   12
           g[v].push_back(u);
   13
           cost[{u, v}] = 0;
   14
           cost[{v, u}] = w;
   15
       }
   16
   
   17
       vector<int> vis(n, 0);
   18
       vector<int> cycle;
   19
   
   20
       function<void(int, int)> dfs = [&](int u, int p) {
   21
           vis[u] = 1;
   22
           cycle.push_back(u);
   23
   
   24
           for (int v : g[u]) {
   25
               if (v == p) continue;
   26
               if (!vis[v])
   27
                   dfs(v, u);
   28
           }
   29
       };
   30
       dfs(0, -1);
   31
   
   32
       long long cost1 = 0, cost2 = 0;
   33
       for (int i = 0; i < n; i++) {
   34
           int u = cycle[i], v = cycle[(i + 1) % n];
   35
           cost1 += cost[{u, v}];
   36
           cost2 += cost[{v, u}];
   37
       }
   38
       cout << min(cost1, cost2) << endl;
   39
   }

8. There are $n$ hurdles in a course and crossing each one increments your score by $arr[i]$. An athelete can only cross at max $k$ consecutive hurdles on the course. What is the maximum score any athlete can get on the course?

   Constraints:

   • $1 \leq n \leq 10^5$
   • $1 \leq k \leq n$
   • $1 \leq arr[i] \leq 10^9$
   Solution

   We will use dynamic programming to solve this problem. Let us denote $dp[i]$ as the minimum sum of elements I must remove from the array $arr[1 \ldots i]$ such that the condition mentioned in the question holds. We also define $g[i]$ to be equal to $dp[i-1] + arr[i]$, and the value of $dp[i]$ can be calculated as $dp[i] = \min (g[j])$ for the previous $k$ indices with respect to $i$. We will use a deque to calculate the range minimum. The time complexity of the solution would be $O(n)$.

   1
   int main()
   2
   {
   3
       int n, k;
   4
       cin >> n >> k;
   5
   
   6
       vector<int> arr(n + 1);
   7
       long long sum = 0;
   8
       for (int i = 1; i <= n; i++)
   9
       {
   10
           cin >> arr[i];
   11
           sum += arr[i];
   12
       }
   13
   
   14
       vector<long long> dp(n + 1), g(n + 1);
   15
       deque<int> dq;
   16
       for (int i = 1; i <= k; i++)
   17
       {
   18
           dp[i] = 0;
   19
           g[i] = dp[i - 1] + arr[i];
   20
   
   21
           while (!dq.empty() && g[dq.back()] >= g[i])
   22
               dq.pop_back();
   23
           dq.push_back(i);
   24
       }
   25
   
   26
       for (int i = k + 1; i <= n; i++)
   27
       {
   28
           while (!dq.empty() && i - dq.front() > k)
   29
               dq.pop_front();
   30
   
   31
           dp[i] = g[dq.front()];
   32
           g[i] = dp[i - 1] + arr[i];
   33
   
   34
           while (!dq.empty() && g[dq.back()] >= g[i])
   35
               dq.pop_back();
   36
           dq.push_back(i);
   37
       }
   38
   
   39
       cout << sum - dp[n] << endl;
   40
   }

9. There are $n$ cities in a country. You need to start at city $s$ and end at city $t$. Between any two cities, you can either take a plane or a boat. The cost for both of them would be given. You want to plan your journey in such a manner that you change your mode of travel between cities (i.e. from plane to boat, or from boat to plane) at most once in the whole journey. Find the minimum cost of the travel.

   Constraints:

   • $1 \leq n \leq 10^3$
   • $1 \leq s, t \leq n$
   • $1 \leq cost_{ij} \leq 10^9$
   Solution

   1
   int main() {
   2
       int n;
   3
       cin >> n;
   4
   
   5
       vector<vector<int>> boat(n, vector<int>(n));
   6
       for (int i = 0; i < n; i++)
   7
           for (int j = 0; j < n; j++)
   8
               cin >> boat[i][j];
   9
   
   10
       vector<vector<int>> plane(n, vector<int>(n));
   11
       for (int i = 0; i < n; i++)
   12
           for (int j = 0; j < n; j++)
   13
               cin >> plane[i][j];
   14
   
   15
       int s, t;
   16
       cin >> s >> t;
   17
       s--, t--;
   18
   
   19
       // Node, Last Mode, Flipped Mode
   20
       long long dis[n][2][2];
   21
       for (int i = 0; i < n; i++)
   22
           for (int j = 0; j < 2; j++)
   23
               for (int k = 0; k < 2; k++)
   24
                   dis[i][j][k] = 1e18;
   25
   
   26
       priority_queue<vector<long long>, vector<vector<long long>>, greater<vector<long long>>> pq;
   27
       pq.push({0, s, 0, 0});
   28
       pq.push({0, s, 1, 0});
   29
       dis[s][0][0] = 0;
   30
       dis[s][1][0] = 0;
   31
   
   32
       while (!pq.empty()) {
   33
           auto top = pq.top();
   34
           pq.pop();
   35
   
   36
           long long d = top[0], u = top[1], mode = top[2], flipped = top[3];
   37
           if (dis[u][mode][flipped] < d)
   38
               continue;
   39
   
   40
           for (int v = 0; v < n; v++)
   41
               for (int newMode = 0; newMode < 2; newMode++) {
   42
                   long long w = (newMode == 0 ? boat[u][v] : plane[u][v]);
   43
                   if (w == -1)
   44
                       continue;
   45
   
   46
                   int newFlipped = flipped + (mode != newMode);
   47
                   if (newFlipped > 1)
   48
                       continue;
   49
   
   50
                   if (dis[v][newMode][newFlipped] > dis[u][mode][flipped] + w) {
   51
                       dis[v][newMode][newFlipped] = dis[u][mode][flipped] + w;
   52
                       pq.push({dis[v][newMode][newFlipped], v, newMode, newFlipped});
   53
                   }
   54
               }
   55
       }
   56
   
   57
       cout << min({
   58
           dis[t][0][0],
   59
           dis[t][0][1],
   60
           dis[t][1][0],
   61
           dis[t][1][1],
   62
       }) << endl;
   63
   }

10. You are given an array of length $n$. In each step you do the following:

    1. Add the sum of the array to your score.
    2. If the length of the array is $1$, the game ends.
    3. You partition the array into two parts, such that both the parts are non-emtpty. You repeat the game with each part individually, and then add the score of both the parts to your score.

    What is the maximum score you can get?

    Constraints:

    • $1 \leq n \leq 10^5$
    • $1 \leq arr[i] \leq 10^9$
    Solution

    We will greedily always parition the rest of the subarray and remove the smallest element from the subarray. The time complexity of the solution would be $O(n \log n)$ due to sorting.

    1
    int main()
    2
    {
    3
        int n;
    4
        cin >> n;
    5
    
    6
        vector<int> arr(n);
    7
        for (int i = 0; i < n; i++)
    8
            cin >> arr[i];
    9
    
    10
        sort(arr.begin(), arr.end());
    11
        vector<long long> suf(n);
    12
        suf[n - 1] = arr[n - 1];
    13
        for (int i = n - 2; i >= 0; i--)
    14
            suf[i] = suf[i + 1] + arr[i + 1];
    15
    
    16
        long long ans = 0;
    17
        for (int i = 0; i < n; i++)
    18
            ans += suf[i];
    19
    
    20
        cout << ans << "\n";
    21
    }

11. You are given an array of length $n$. Count the number of subarrays of the same whose $XOR$ has an even number of divisors.

    Contraints:

    • $1 \leq n \leq 10^5$
    • $1 \leq arr[i] \leq n$
    Solution

    1
    int main()
    2
    {
    3
        long long n;
    4
        cin >> n;
    5
    
    6
        vector<int> arr(n);
    7
        for (int i = 0; i < n; i++)
    8
            cin >> arr[i];
    9
    
    10
        vector<int> sq;
    11
        for (int i = 0; i * i <= 2 * n; i++)
    12
            sq.push_back(i * i);
    13
    
    14
        long long ans = n * (n + 1) / 2;
    15
        map<int, int> cnt;
    16
        cnt[0] = 1;
    17
    
    18
        int pre = 0;
    19
        for (int i = 0; i < n; i++)
    20
        {
    21
            pre ^= arr[i];
    22
            for (int j : sq)
    23
                ans -= cnt[j ^ pre];
    24
            cnt[pre]++;
    25
        }
    26
    
    27
        cout << ans << "\n";
    28
    }

12. XOUR

13. Given a string $s$, find the number of substrings of $s$ that have length atleast $l$, length atmost $r$, and have less than or equal to $k$ distinct characters present in them.

    Constraints:

    • $1 \leq |s| \leq 10^5$
    • $1 \leq l \leq r \leq |s|$
    • $1 \leq k \leq 26$
    Solution

    We will use a two-pointer approach to solve this problem. We have calculated an utility that calculates the number of substrings with length at most $maxLen$ and having atmost $k$ distinct characters. Using the same, we can calculate the required quantity in the question. The time complexity of the solution would be $O(n)$.

    1
    int cntMaxLen(string &s, int maxLen, int k)
    2
    {
    3
        if (k == 0 || maxLen == 0)
    4
            return 0;
    5
    
    6
        int n = s.size();
    7
        map<char, int> cnt;
    8
        int j = 0;
    9
        cnt[s[0]] = 1;
    10
    
    11
        int ans = 0;
    12
        for (int i = 0; i < n; i++)
    13
        {
    14
            while (j + 1 < n)
    15
            {
    16
                int curLen = j - i + 1;
    17
                bool lenSatify = curLen + 1 <= maxLen;
    18
                bool szSatisfy = cnt.size() < k || (cnt.find(s[j + 1]) != cnt.end());
    19
                if (lenSatify && szSatisfy)
    20
                {
    21
                    j++;
    22
                    cnt[s[j]]++;
    23
                }
    24
                else
    25
                    break;
    26
            }
    27
    
    28
            ans += j - i + 1;
    29
            cnt[s[i]]--;
    30
            if (!cnt[s[i]])
    31
                cnt.erase(s[i]);
    32
        }
    33
    
    34
        return ans;
    35
    }
    36
    
    37
    int main()
    38
    {
    39
        string s;
    40
        cin >> s;
    41
    
    42
        int l, r, k;
    43
        cin >> l >> r >> k;
    44
        cout << cntMaxLen(s, r, k) - cntMaxLen(s, l - 1, k);
    45
    }

14. There is an undirected graph of $n$ vertices, connected by $n-1$ bidirectional edges. People are standing on each node of the graph connected by a rope inside of this graph. There are $2$ ends of the rope: head is at vertex $a$ and it’s tail is at vertex $b$. The people connected by this rope occupy all vertices on the unique simple path between $a$ and $b$. The people want to know if they can reverse their order, meaning that the person standing at the head of the rope needs to move to the node where the rope’s tail is, and the person standing on the tail node needs to move to the node where the rope’s head is. Unfortunately, the people’s movement is restricted to the graph structure.

    In an operation, the person on the head can move to an adjacent vertex not currently occupied. When the person at the head does this each person connected will also move one vertes closer to the head, so that the length of the rope remains unchanged. Similarly, the person standing on the tail vertex can move to an adjacent verter not currently occupied. When the person at tall does this cach person connected will also move one vertex closer to the tail. Determine if it is possible to reverse the people with some sequence of moves.

    Constraints:

    • $1 \leq n \leq 10^5$
    • $1 \leq a, b \leq n$

    This is a restatement of the question The Majestic Brown Snake.

15. You are monitoring the building density in a district of houses. The district is represented as a number line, where a house can be built at each numbered point on the line if at least one of the neighboring points is not occupied. Initially, there are no houses in the district. You are given $queries$, an array of integers representing the locations of new houses in the order in which they will be built. After each house is built, your task is to find the longest segment of contiguous houses in the district. It is guaranteed that all of the house locations in queries are unique and no house was built at a point with existing houses on both left and right adjacent points.

    Constraints:

    • $1 \leq |queries| \leq 10^5$
    • $1 \leq queries[i] \leq 10^9$
    Solution

    1
    int main()
    2
    {
    3
        int q;
    4
        cin >> q;
    5
    
    6
        set<pair<int, int>> s;
    7
        multiset<int> le;
    8
        int x;
    9
        cin >> x;
    10
        s.insert({x, x});
    11
        le.insert(1);
    12
        cout << 1 << " ";
    13
    
    14
        for (int i = 1; i < q; i++)
    15
        {
    16
            cin >> x;
    17
    
    18
            auto itr = s.lower_bound({x, x});
    19
            if (itr != s.end() && (*itr).first == x + 1)
    20
            {
    21
                auto p = *itr;
    22
                le.erase(le.find(p.second - p.first + 1));
    23
                s.erase(itr);
    24
                s.insert({p.first - 1, p.second});
    25
                le.insert({p.second - p.first + 2});
    26
            }
    27
            else if (itr != s.begin() && (*(--itr)).second == x - 1)
    28
            {
    29
                auto p = *itr;
    30
                le.erase(le.find(p.second - p.first + 1));
    31
                s.erase(itr);
    32
                s.insert({p.first, p.second + 1});
    33
                le.insert({p.second - p.first + 2});
    34
            }
    35
            else
    36
            {
    37
                le.insert(1);
    38
                s.insert({x, x});
    39
            }
    40
    
    41
            cout << *le.rbegin() << " ";
    42
        }
    43
    }

Online Assessment Questions

1. Checking if the given graph was bipartite.

2. You are given an array $arr$ of length $n$. What is the shortest subarray that you must remove from the same so that the sum of the leftover array is divisible by $p$?

   Constraints:

   • $1 \leq n \leq 10^5$
   • $1 \leq arr[i] \leq 10^9$
   • $1 \leq p \leq 10^9$

3. What is the number of subsets of the numbers $[1, 2, 3, ...., n]$ such that if $x$ is present in a subset, then $2 \cdot x$ and $3 \cdot x$ are not present in the same? Return the answer modulo $10^9 + 7$.

   Constraints:

   • $1 \leq n \leq 10^5$

4. There is a grid of bricks of size $N \times M$. You make $q$ attacks on the same. Each attack is represented as $(x, y, t)$ where you destroy the brick in the row $x$ and column $y$ at the time $t$. Find the minimum time after which there is atleast a square hole of size $k \times k$ in the wall.

   Constraints:

   • $1 \leq n, m \leq 10^3$
   • $1 \leq q \leq 10^5$
   • $1 \leq x \leq n$
   • $1 \leq y \leq m$
   • $1 \leq t \leq 10^9$

Oracle

Other Campus Questions

1. You are given two integer $x$ and $y$. You need to find an integer $z$ such that $z \leq 2^n$ and the value of $(x \oplus z) \cdot (y \oplus z)$ is maximum. Here, $\oplus$ denotes the bitwise XOR operation. Return the value of $(x \oplus z) * (y \oplus z)$ modulo $10^9 + 7$.

   Constraints:

   • $1 \leq x, y \leq 10^18$
   • $1 \leq n \leq 50$
   Solution

   We will iterate over all the bits of $x$ and $y$ and try to set try to set the bit of both the numbers obtained after the XOR to $1$. If the same is not possible, we first prefer set the same in the smaller number. The time complexity of the solution would be $O(n)$.

   int maximumXorProduct(long long a, long long b, int n) {
       for (int bit = n - 1; bit >= 0; bit--)
       {
           int x = (a >> bit) & 1;
           int y = (b >> bit) & 1;
   
           if (x == y) {
               a |= (1LL << bit);
               b |= (1LL << bit);
           }
           else
           {
               if (a > b)
                   swap(a, b);
               a |= (1LL << bit);
               if ((b >> bit) & 1)
                   b ^= (1LL << bit);
           }
       }
   
       long long mod = 1e9 + 7;
       return (a % mod) * (b % mod) % mod;
   }

2. You are given an undirected connected graph witn $n$ nodes and $m$ edges. You first need to construct any traversal of the graph, and store it in array $a$. All the nodes must be visited atleast once in this traversal. Then you need to construct another array $b$ from the array $a$, such that $b$ is a subsequence of $a$ consiting of only the first occurences of every node. Thus the length of $b$ would be exactly $n$. Find the lexographically maximum sequence $b$ that can be generated by chosing the array $a$ optimally.

   Constraints:

   • $1 \leq n, m \leq 10^5$
   • $1 \leq a_i, b_i \leq n$
   Solution

   1
   int main()
   2
   {
   3
       int n, m;
   4
       cin >> n >> m;
   5
   
   6
       vector<vector<int>> g(n);
   7
       for (int i = 0; i < m; i++)
   8
       {
   9
           int x, y;
   10
           cin >> x >> y;
   11
           g[x - 1].push_back(y - 1);
   12
           g[y - 1].push_back(x - 1);
   13
       }
   14
   
   15
       vector<int> done(n, 0);
   16
       set<int> candidates;
   17
       vector<int> b;
   18
   
   19
       b.push_back(n);
   20
       done[n - 1] = 1;
   21
       for (int v : g[n - 1])
   22
           candidates.insert(v);
   23
   
   24
       while (!candidates.empty())
   25
       {
   26
           auto t = *candidates.rbegin();
   27
           candidates.erase(--candidates.end());
   28
   
   29
           b.push_back(t + 1);
   30
           done[t] = 1;
   31
           for (int v : g[t])
   32
               if (!done[v])
   33
                   candidates.insert(v);
   34
       }
   35
   
   36
       for (int x : b)
   37
           cout << x << " ";
   38
   }

3. Count the number of subsequences of string $t$ in the given string $s$. Return the answer modulo $10^9 + 7$.

   Constraints:

   • $1 \leq |s|, |t| \leq 10^3$
   Solution

   int main()
   {
       string s, t;
       cin >> s >> t;
   
       int n = s.size(), m = t.size();
       vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
       for (int i = 0; i <= n; i++)
           dp[i][0] = 1;
   
       int mod = 1e9 + 7;
   
       for (int i = 1; i <= n; i++)
           for (int j = 1; j <= m; j++)
           {
               if (s[i - 1] != t[j - 1])
                   dp[i][j] = dp[i - 1][j];
               else
                   dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
               dp[i][j] %= mod;
           }
   
       cout << dp[n][m] << "\n";
   }

4. You are given an integer $x$. Find the smallest number greater or equal to $x$ which has no consecutive one’s in it’s binary representation.

   Constraints:

   • $1 \leq x \leq 10^9$
   Solution

   We would iterate from right to left, and maintain a mask to find the occurence of $11$ in the digit. As soon we find the same, we increment the prefix by $1$ and replace the suffix of the number with $0000 \cdots$ bits.

   int main()
   {
       int x;
       cin >> x;
   
       int mask = 3, pos = 2;
       while (mask <= x)
       {
           if ((mask & x) == mask)
           {
               x >>= pos;
               x++;
               x <<= pos;
           }
           mask <<= 1;
           pos++;
       }
   
       cout << x;
   }

5. Alex is working on a planet where there are $N$ days in a year. He noticed that his performence on $i^{th}$ the day of the year was equal to $nums[i]$. Alex is a hard worker and he wants to come to work for the max number of days that he can. However, he does not want to have a negative total perfonttance at any point in time since his boss will deduct his salary. Help Alex find the major number of days in the year that he can come to the office.

   Constraints:

   • $1 \leq N \leq 10^5$
   • $-10^9 \leq nums[i] \leq 10^9$
   Solution

   int main() {
       int n;
       cin >> n;
   
       vector<int> arr(n);
       for (int i = 0; i < n; i++)
           cin >> arr[i];
   
       long long sum = 0;
       priority_queue<int, vector<int>, greater<int>> pq;
       int ans = 0;
   
       for (int i = 0; i < n; i++) {
           if (arr[i] >= 0) {
               sum += arr[i];
               ans++;
               continue;
           }
   
           if (sum + arr[i] >= 0) {
               sum += arr[i];
               pq.push(arr[i]);
               ans++;
           } else if (!pq.empty() && pq.top() < arr[i]) {
               sum -= pq.top();
               sum += arr[i];
               pq.pop();
               pq.push(arr[i]);
           }
       }
   
       cout << ans << endl;
   }

6. You are given an array $arr$. In one operations, you are required to choose a range $[l, r]$ such that it has not been chosen previously, and then add the value of $max(arr[l] ..., arr[r])$ to your score. What is the maximum score you can obtain after performing at max $k$ operations?

   Constraints:

   • $1 \leq n \leq 10^5$
   • $1 \leq k \leq min(10^9, \frac{n (n + 1)}{2})$
   • $1 \leq arr[i] \leq 10^9$
   Solution

   1
   int main()
   2
   {
   3
       long long n, k;
   4
       cin >> n >> k;
   5
   
   6
       vector<int> arr(n);
   7
       for (int i = 0; i < n; i++)
   8
           cin >> arr[i];
   9
   
   10
       vector<int> nxtGreater(n, n);
   11
       stack<int> st;
   12
       for (int i = 0; i < n; i++)
   13
       {
   14
           while (!st.empty() && arr[i] > arr[st.top()])
   15
           {
   16
               nxtGreater[st.top()] = i;
   17
               st.pop();
   18
           }
   19
           st.push(i);
   20
       }
   21
       while (!st.empty())
   22
           st.pop();
   23
   
   24
       vector<int> prevGreater(n, -1);
   25
       for (int i = n - 1; i >= 0; i--)
   26
       {
   27
           while (!st.empty() && arr[i] >= arr[st.top()])
   28
           {
   29
               prevGreater[st.top()] = i;
   30
               st.pop();
   31
           }
   32
           st.push(i);
   33
       }
   34
   
   35
       vector<pair<long long, long long>> ele;
   36
       for (int i = 0; i < n; i++)
   37
       {
   38
           long long cnt = (i - prevGreater[i]) * (nxtGreater[i] - i);
   39
           ele.push_back({arr[i], cnt});
   40
       }
   41
       sort(ele.begin(), ele.end());
   42
       reverse(ele.begin(), ele.end());
   43
   
   44
       long long ans = 0, mod = 1e9 + 7;
   45
       for (auto &[x, cnt] : ele)
   46
       {
   47
           long long ops = min(cnt, k);
   48
           k -= ops;
   49
           ans += x * ops;
   50
           ans %= mod;
   51
           if (k == 0)
   52
               break;
   53
       }
   54
   
   55
       cout << ans << "\n";
   56
   }

7. You are given a string $s$. Find the length of the minimum substring of $s$ that must be removed from the same, so that the remaining string can be permuted to form a palindrome. String $s$ only consists of lowercase English alphabets.

   Constraints:

   • $1 \leq |s| \leq 10^5$
   Solution

   1
   int main()
   2
   {
   3
       string s;
   4
       cin >> s;
   5
   
   6
       int n = s.size();
   7
       vector<int> sufMask(n);
   8
       sufMask[n - 1] = (1 << (s[n - 1] - 'a'));
   9
       for (int i = n - 2; i >= 0; i--)
   10
           sufMask[i] = sufMask[i + 1] ^ (1 << (s[i] - 'a'));
   11
   
   12
       vector<int> tarMasks = {0};
   13
       for (int j = 0; j < 26; j++)
   14
           tarMasks.push_back(1 << j);
   15
   
   16
       unordered_map<int, int> idx;
   17
       idx[0] = -1;
   18
       int ans = n;
   19
       int pre = 0;
   20
   
   21
       for (int i = 0; i < n; i++)
   22
       {
   23
           pre ^= (1 << (s[i] - 'a'));
   24
           for (auto t : tarMasks)
   25
           {
   26
               t = t ^ sufMask[i];
   27
               if (idx.find(t) != idx.end())
   28
                   ans = min(ans, i - idx[t] - 1);
   29
           }
   30
   
   31
           idx[pre] = i;
   32
       }
   33
   
   34
       cout << ans << "\n";
   35
   }

8. You are given $n$ points on a grid. Calculate the area of the minimum square that encloses at-least $k$ of the points in the grid. The points that lie on the boundary of the square are not counted as to be enclosed in the same.

   Constraints:

   • $1 \leq n \leq 100$
   • $1 \leq k \leq n$
   • $-10^9 \leq x, y \leq 10^9$
   Solution

   1
   int main()
   2
   {
   3
       int n;
   4
       cin >> n;
   5
   
   6
       vector<pair<int, int>> pts(n);
   7
       for (int i = 0; i < n; i++)
   8
           cin >> pts[i].first >> pts[i].second;
   9
   
   10
       int k;
   11
       cin >> k;
   12
   
   13
       int ans = 1e9;
   14
   
   15
       for (int i = 0; i < n; i++)
   16
           for (int j = i + k - 1; j < n; j++)
   17
           {
   18
               int xr = pts[j].first - pts[i].first + 2;
   19
   
   20
               vector<int> y;
   21
               for (int t = i; t <= j; t++)
   22
                   y.push_back(pts[t].second);
   23
               sort(y.begin(), y.end());
   24
   
   25
               int m = y.size();
   26
               for (int t = 0; t + k - 1 < m; t++)
   27
               {
   28
                   int yr = y[t + k - 1] - y[t] + 2;
   29
                   ans = min(ans, max(yr, xr));
   30
               }
   31
           }
   32
   
   33
       cout << (long long)ans * (long long)ans << "\n";
   34
   }

9. Maximise the String

10. You are given a tree of $n$ nodes. You need to colour the nodes of the tree with $m$ colours, such that no two adjacent nodes, as well as two nodes that are adjacent to a common city have the same colour. Output the number of colourings of the graph modulo $10^9 + 7$.

    Constraints:

    • $1 \leq n \leq 10^5$
    • $1 \leq m \leq 10^5$
    Solution

    1
    long long MOD = 1e9 + 7;
    2
    
    3
    long long binPow(long long a, long long b)
    4
    {
    5
        a %= MOD;
    6
        long long res = 1;
    7
    
    8
        while (b)
    9
        {
    10
            if (b & 1)
    11
            {
    12
                res = res * a;
    13
                res %= MOD;
    14
            }
    15
            a *= a;
    16
            a %= MOD;
    17
            b >>= 1;
    18
        }
    19
    
    20
        return res;
    21
    }
    22
    
    23
    int main()
    24
    {
    25
        long long n, m;
    26
        cin >> n >> m;
    27
    
    28
        vector<vector<int>> g(n);
    29
        for (int i = 0; i < n - 1; i++)
    30
        {
    31
            int u, v;
    32
            cin >> u >> v;
    33
            g[u - 1].push_back(v - 1);
    34
            g[v - 1].push_back(u - 1);
    35
        }
    36
    
    37
        vector<long long> fac(m + 1);
    38
        fac[0] = 1;
    39
        for (long long i = 1; i <= m; i++)
    40
        {
    41
            fac[i] = i * fac[i - 1];
    42
            fac[i] %= MOD;
    43
        }
    44
    
    45
        vector<long long> inv(m + 1);
    46
        for (int i = 0; i <= m; i++)
    47
            inv[i] = binPow(fac[i], MOD - 2);
    48
    
    49
        auto nCr = [&](int n, int r) -> long long
    50
        {
    51
            if (r > n)
    52
                return 0;
    53
    
    54
            long long dr = (inv[r] * inv[n - r]) % MOD;
    55
            return (fac[n] * dr) % MOD;
    56
        };
    57
    
    58
        function<long long(int, int, int)> dfs = [&](int u, int p, int d) -> long long
    59
        {
    60
            int cnt = 0;
    61
    
    62
            long long ways = 1;
    63
            for (int v : g[u])
    64
            {
    65
                if (v == p)
    66
                    continue;
    67
                cnt++;
    68
                ways *= dfs(v, u, d + 1);
    69
                ways %= MOD;
    70
            }
    71
    
    72
            if (d == 0)
    73
            {
    74
                long long w = (nCr(m - 1, cnt) * fac[cnt]) % MOD;
    75
                return (w * ways) % MOD;
    76
            }
    77
    
    78
            long long w = (nCr(m - 2, cnt) * fac[cnt]) % MOD;
    79
            return (w * ways) % MOD;
    80
        };
    81
    
    82
        long long ans = m * dfs(0, -1, 0);
    83
        cout << ans % MOD << "\n";
    84
    }