Question: Zomato, Recently Asked Questions in IITs, November, 2022
0
Entering edit mode
ADD COMMENTlink 14 days ago Rohit • 190 • updated 10 days ago Ujjwal Srivastava 160
0
Entering edit mode

Question 2

Overview

  • Given an array A consisting of N integers. Also given Q queries along with it.
  • In each query, you are given 3 spaced separated integers L, R and X.
  • You need to output the summation of XOR of X with each of the array elements from range L to R both inclusive(1- based indexing).

Solution

  • For each of the bits i.e from 0_th to 30_th-bit, maintain a count(prefix sum) for each of them, how many times they are set in the range 0 to L.
  • Now to find how many times i_th bit is set in range L to R we can simply do pre_sum[i][R]-pre_sum[i][L-1].
  • Now we will iterate from 0_th bit to 30_th bit and do the following.

    • For each of the bits we will count how many times they are set in the range L to R. Let it be set_current_bit_number.
    • Now if the current bit is set in X , then we will add (1ll<<current_bit)*((R-L+1)-set_current_bit_number) to the answer.
    • If the current bit is not set in X, then we will add (1ll<<current_bit)*(set_current_bit_number) to the answer.
    • At last print the answer.
  • This can be done for all the queries.

Code

ll n, q;
cin &gt;&gt; n &gt;&gt; q;
vector&lt;ll&gt; a(n);
ll pre_sum[31][n + 1];
mem0(pre_sum);
for (ll i = 0; i &lt; n; i++)
{
    cin &gt;&gt; a[i];
    for (ll j = 0; j &lt;= 30; j++)
    {
        if (a[i] &amp; (1ll &lt;&lt; j))
        {
            pre_sum[j][i]++;
        }
        if (i)
            pre_sum[j][i] += pre_sum[j][i - 1];// maintain a prefix sum for each bit
    }
}
for (ll i = 1; i &lt;= q; i++)
{
    ll l, r, x;
    cin &gt;&gt; l &gt;&gt; r &gt;&gt; x;
    l--, r--;
    ll ans = 0;
    for (ll j = 0; j &lt;= 30; j++)
    {
        ll set_current_bit_number = 0;
        if (l)
            set_current_bit_number = pre_sum[j][r] - pre_sum[j][l - 1];// count how many times i_th bit is set in range l to r
        else
            set_current_bit_number = pre_sum[j][r];
        if (x &amp; (1ll &lt;&lt; j))// if current bit is set in x
        {
            ans += ((1ll &lt;&lt; j) * ((r - l + 1) - set_current_bit_number));// multiply the corresponding value by number of unset indices
        }
        else
        {
            ans += ((1ll &lt;&lt; j) * (set_current_bit_number));// multiply the corresponding value by number of set indices.
        }
    }
    cout &lt;&lt; ans &lt;&lt; endl;// print the answer
}
return;
ADD COMMENTlink 11 days ago Ujjwal Srivastava 160
0
Entering edit mode

Question-1

Overview

  • Given N people. For a pair of people, they have a friend value A[i][j].
  • We want to split these people into N groups, such that each people belong to exactly one group and each group contains at least one person.
  • The partition value of a split is defined as the minimum friend value over all the pairs of different people within the same group.
  • Find the maximum partition value possible.
  • Suppose the minimum friend value of all pairs of different people from Group 1 is min1 and from Group2 is min2. Then the partition value is defined as min(min1,min2).

Solution

  • If N = 3, then one group will contain only one person hence the partition value will be 0.
  • If N >= 4 then each group can have at least 2 people.
  • Now to find the optimal value, we will binary search over the answer.
  • Let's say the possible partition value is x. To find out whether it is possible or not we will do the following

    • Iterate over the NxN matrix, if for pairs i, j (i not equal to j) the value A[i][j] is less than x then they must be in the opposite group hence make an edge between them.
    • If the value is greater than or equal to x then they can be in the same or opposite group, hence there is no need to make an edge.
    • Now after we have iterated over the matrix, we will check if the graph formed above is bipartite or not. If not then x is not a possible value and we have to reduce the high value in the binary search.
    • If the graph is bipartite and each group contains at least two people, the x is a possible value and we can increase the low value in binary search.
    • In this way at last we will arrive at the most optimal possible value of x.

Code

bool check_bipartite(ll n, vector&lt;vector&lt;ll&gt;&gt; adj){

vector&lt;ll&gt; side(n, -1);
bool is_bipartite = true;
queue&lt;ll&gt; q;
vector&lt;pll&gt; vsides;
for (ll st = 0; st &lt; n; st++)
{
    if (side[st] == -1)
    {
        q.push(st);
        side[st] = 0;
        ll cnt_st0 = 0, cnt_st1 = 0;
        while (!q.empty())
        {
            ll v = q.front();
            if (side[v]) // if it belongs to side 1
                cnt_st1++;
            else
                cnt_st0++;
            q.pop();
            for (ll u : adj[v])
            {
                if (side[u] == -1)
                {
                    side[u] = side[v] ^ 1; // make side of adjacent one different from the current one
                    q.push(u);
                }
                else
                {
                    is_bipartite &amp;= side[u] != side[v]; // if adjacent one belong to same side then the graph is not bipartite
                }
            }
        }
        vsides.pb({cnt_st0, cnt_st1}); // push the two different sides in a vector of pairs
    }
}

if (!is_bipartite) // if the graph is not bipartite return 0
    return 0;
else // if graph is bipartite
{
    if (vsides.size() &gt; 1) // It can always be divided into two groups such that each of them have atleast two members
        return 1;
    else
    {
        if (vsides[0].ff == 1 || vsides[0].ss == 1) // If it is not possible to divide into two groups such that each of them have atleast two members
            return 0;

        return 1;
    }
}

}


void solve(){

ll n;
cin &gt;&gt; n;
ll a[n][n];
mem0(a);
for (ll i = 0; i &lt; n; i++)
{
    for (ll j = 0; j &lt; n; j++)
    {
        cin &gt;&gt; a[i][j];
    }
}
if (n == 3) // It is not poosible to divide it into two groups such that each of them have atleast 2 members
{
    cout &lt;&lt; 0 &lt;&lt; endl;
    return;
}
ll lw = 1, hi = 1e9; // take the minimum and maximum value
while (lw &lt;= hi)
{
    ll mid = (lw + hi) / 2;
    vector&lt;vector&lt;ll&gt;&gt; adj(n);
    for (ll i = 0; i &lt; n; i++)
    {
        for (ll j = 0; j &lt; n; j++)
        {
            if (i != j)
            {
                if (a[i][j] &lt; mid)
                {
                    adj[i].pb(j);
                }
            }
        }
    }
    if (check_bipartite(n, adj)) // check if mid is a possible value
    {
        lw = mid + 1; // if yes increment the lower bound
    }
    else
    {
        hi = mid - 1; // if no decrement the upper bound
    }
}
cout &lt;&lt; hi &lt;&lt; endl; // print the optimal value
return;
}
ADD COMMENTlink 10 days ago Ujjwal Srivastava 160

Login before adding your answer.

Similar Posts
Loading Similar Posts