Missing Soldiers

An infinite army of ants is marching on an infinite 2-D plane. Since ants are disciplined, here's how they march: each ant chooses exactly one x coordinate and moves along it in positive y-direction, starting from (x, 0). There exists exactly one ant for each x coordinate on that plane and hence there are infinite ants!

There are N horizontal barriers lying on this plane. The ith barrier is defined by (xi, yi) and di, which means that the barrier is blocking all ants which want to pass through points lying on line segment connecting (xi, yi) and (xi + di, yi). Once an ant encounters a barrier, it stops moving.

Given all the barriers, your task is to find the total number of ants, that will be ever blocked at some point in their march.

Example:

Input: n = 2, arr = {{1, 1, 4}, {7, 3, 5}}
Output: 11

Approach

C++

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> a;

vector<pair<int, int>> merge(const vector<pair<int, int>> &x)
{
    int n = x.size();

    //if size is 1 then return the
    //same vector
    if (n == 1)
        return x;
    vector<pair<int, int>> res;
    res.push_back(x[0]);
    for (int i = 1; i < n; ++i)
    {
        if (x[i].first <= res.back().second)
        {
            res.back().second = max(res.back().second, 
                                   x[i].second);
        }
        else
        {
            res.push_back(x[i]);
        }
    }
    return res;
}

int missingSoldiers(int n, vector<vector<int>> &arr)
{
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        a.push_back(make_pair(arr[i][0], arr[i][0] + arr[i][2]));
    }
    //sort the array
    sort(a.begin(), a.end());
    a = merge(a);
    for (int i = 0; i < a.size(); ++i)
    {
        ans += (a[i].second - a[i].first + 1LL);
    }
    return ans;
}
int main()
{

    int n = 2;

    vector<vector<int>> arr = {{1, 1, 4},
                               {7, 3, 5}};

    cout << missingSoldiers(n, arr) << "\n";
    return 0;
}

Scoreboard queries

In a tournament there are $(N+1)$ players, $N$ players have already played and their scores are denoted by an array $A$. Here, $A_1$ is the score of the first player, $A_2$ of the second, ..., $A_N$ of the $N^{th}$ player.

Now, the organizers decide the ranks according to the following rules:

The player $x$ scored more than player $y$, player $x$ gets a better rank.

In the case of a tie, the player with lower indices gets a better rank.

Now, it is the turn of the $(N+1{)}^{th}$ player to play. Before playing, he wants to know the number of ranks that he can secure so that he can decide his strategy.

Now, the jury has some scoreboard updates. Therefore, your task is to tell the jury after every update the number of distinct possible ranks that he can get.

Example:

Input:  n = 4, q = 1, arr = {2, 1, 1, 5}

Output:

5

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

void scoreboardQueries(long n, long q, vector<long> v,
                       vector<vector<long>> &queries)
{
    unordered_map<long, long> board;
    for (long i = 1; i <= n; ++i)
    {

        ++board[v[i]];
    }
    for (long i = 0; i < q; i++)
    {
        long l = queries[i][0];
        long r = queries[i][1];
        --board[v[l]];
        if (board[v[l]] == 0)
            board.erase(v[l]);
        v[l] = r;
        ++board[v[l]];
        cout << board.size() + 1 << "\n";
    }
}
int main()
{

    long n = 4, q = 1;
    vector<long> arr = {2, 1, 1, 5};
    vector<long> v(n + 1);
    for (long i = 1; i <= n; i++)
        v[i] = arr[i - 1];
    vector<vector<long>> queries = {{2, 3}};

    scoreboardQueries(n, q, v, queries);

    return 0;
}

Minimum XOR

You are given $q$ queries of two types:

1. $1X$: Append value $X$ into an array.
2. $2XK$: You are required to print the $K^{th}$ minimum XOR of $X$ with the current array.
   You have to make a new array whose $i^{th}$ element is current_array[i]${}^X$. Then sort it and print the $K^{th}$ element.

Example:

Input: q = 8, queries = {{1, 5}, {1, 3}, {1, 2}, {1, 9}, {2, 8, 3}, {1, 89}, {1, 56}, {2, 85, 5}}

Output:

11
92

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

//structure of the trie
struct Trienode
{
    Trienode *left;
    Trienode *right;
    int below = 0;
};

//function to insert the data into
//the trie
void insert(Trienode *head, long long element)
{
    Trienode *curr = head;
    for (long long i = 63; i >= 0; i--)
    {
        long long b = (element >> i) & 1;
        curr->below++;

        //if zero go for left side
        if (b == 0)
        {

            //if left does not exit
            //then create new node for left
            if (!curr->left)
            {
                curr->left = new Trienode();
            }

            //move to left of current node
            curr = curr->left;
        }

        //if not zero then go to
        //right side
        else
        {

            //if right does not exist
            //create new node for right
            if (!curr->right)
            {
                curr->right = new Trienode();
            }

            //move right of current node
            curr = curr->right;
        }
    }

    //update below
    curr->below++;
}

long long query(Trienode *head, long long x, long long k)
{
    Trienode *curr = head;
    long long ans = 0;
    for (long long i = 63; i >= 0; i--)
    {
        long long b = (x >> i) & 1;
        long long t = (1LL << i);
        long long res = 0;

        //if zero then go to left size
        if (b == 0)
        {

            //if current's left exist

            if (curr->left)
            {
                res = curr->left->below;
            }
            if (res >= k)
            {
                curr = curr->left;
            }

            //now move to right side
            else
            {
                ans += t;
                k -= res;
                if (!curr->right)
                {
                    curr->right = new Trienode();
                }
                curr = curr->right;
            }
        }

        //if not zero then go to right side
        else
        {
            if (curr->right)
            {
                res = curr->right->below;
            }
            if (res >= k)
            {
                curr = curr->right;
            }
            else
            {
                ans += t;
                k -= res;
                if (!curr->left)
                {
                    curr->left = new Trienode();
                }
                curr = curr->left;
            }
        }
    }
    return ans;
}

int main()
{

    Trienode *head = new Trienode();
    long long q = 8;

    vector<vector<long long>> queries = {{1, 5},
                                         {1, 3},
                                         {1, 2},
                                         {1, 9},
                                         {2, 8, 3},
                                         {1, 89},
                                         {1, 56},
                                         {2, 85, 5}};

    for (long long i = 0; i < q; i++)
    {
        long long c = queries[i][0];
        if (c == 1)
        {
            long long y = queries[i][1];
            insert(head, y);
        }
        else
        {
            long long x = queries[i][1];
            long long k = queries[i][2];

            cout << query(head, x, k) << "\n";
        }
    }
    return 0;
}