Join Us
Loading Similar Posts
Entering edit mode
Question 1
Friends
There are N people. For a pair of people (i,j), they have a friend value A[i][j].
We want to split these N people into 2 groups, such that each person belongs 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 of all 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 Group 2 it is min2.
Then partition value is defined as min(min1, min2).
Input format-
- The first line contains single integer N representing the number of people.
- The next N line contains N integers each where A[i][j] represents friend value between i and j.
Output format-
- Print a single integer representing the maximum partition value possible.
Constraints-
3 < N <= 500
1 <= A[i][j] <= 109, for i!=j
A[i][i] = 0
A[i][j] = A[j][i]
Click here to Practice
Submit Problem to OJ
Question 2
The XOR Operation
Find the answer of each query
You are given an array of integers A of size N. Now you are given Q queries to be performed over this array.
In each of the query, you are given 3 space separated integers L,R and X, you need to output the summation of XOR of X with each of the array element from range L to R both inclusive (1-based indexing).
The array does not change after any query.
Input format:
N Q
A1 A2 ... AN
L1 R1 X1
L2 R2 X2
...
LO RQ XQ
- The first line contains the size of array N and the number of queries Q.
- Next line contains N space separated array elements.
- Q lines follow, each containing 3 space separated integers L R and X
Output Format
S1
S2
…
SQ
Print Qlines, the i-th line denoting the answer(Si) to the i-th query.
Example
Input:
5 2
2 3 1 4 5
1 1 3
3 5 2
Output:
1
16
Explanation:
For 1st query we have L=1, R=1 and X=3, i.e. A1^X = 2^3 = 1.
For 2nd query we have L=3, R=5 and X=2, i.e. A3^X + A4^X + A5^X => 1^2 + 4^2 + 5^2 = 16.
Click here to Practice
Submit Problem to OJ
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<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;
}
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 >> 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;
cant we do this problem by dp by precomputing min in a range and then using partition dp to break the array of peoples into groups