Question: Zomato, Recently Asked Questions in IITs, November, 2022
0
Entering edit mode

# Question 1

Friends

Question 2

==========

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

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();
{
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;
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)
{
}
}
}
}
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;
}