Loading Similar Posts

Entering edit mode

Friends

Click here to Practice

Submit Problem to OJ

Question 2

Click here to Practice

Submit Problem to OJ

==========

Entering edit mode

**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.

- For each of the bits we will count how many times they are set in the range L to R. Let it be
- This can be done for all the queries.

**Code**

```
ll n, q;
cin >> n >> q;
vector<ll> a(n);
ll pre_sum[31][n + 1];
mem0(pre_sum);
for (ll i = 0; i < n; i++)
{
cin >> a[i];
for (ll j = 0; j <= 30; j++)
{
if (a[i] & (1ll << 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 <= q; i++)
{
ll l, r, x;
cin >> l >> r >> x;
l--, r--;
ll ans = 0;
for (ll j = 0; j <= 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 & (1ll << j))// if current bit is set in x
{
ans += ((1ll << j) * ((r - l + 1) - set_current_bit_number));// multiply the corresponding value by number of unset indices
}
else
{
ans += ((1ll << j) * (set_current_bit_number));// multiply the corresponding value by number of set indices.
}
}
cout << ans << endl;// print the answer
}
return;
```

Entering edit mode

**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<vector<ll>> adj){
vector<ll> side(n, -1);
bool is_bipartite = true;
queue<ll> q;
vector<pll> vsides;
for (ll st = 0; st < 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 &= 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() > 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 >> n;
ll a[n][n];
mem0(a);
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < n; j++)
{
cin >> 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 << 0 << endl;
return;
}
ll lw = 1, hi = 1e9; // take the minimum and maximum value
while (lw <= hi)
{
ll mid = (lw + hi) / 2;
vector<vector<ll>> adj(n);
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < n; j++)
{
if (i != j)
{
if (a[i][j] < 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 << hi << endl; // print the optimal value
return;
}
```

Loading Similar Posts