PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter and Editorialist: Soumyadeep Pal
Testers: Takuki Kurokawa, Tejas Pandey
DIFFICULTY:
3099
PREREQUISITES:
Bitwise operations, Binary Search
PROBLEM:
You are given two integers N \ ( N \geq 2) and S. You have to construct an array A containing N integers such that:
- 0 \leq A_i \leq S
- A_1 + A_2 + \ldots + A_N = S
- A_1 & A_2 & .... & A_N = 0, where & denotes bitwise AND operator.
- The maximum element of the array is minimized.
Find the maximum element of the array A.
EXPLANATION:
Hint 1
For a fixed maximum element x, what is the maximum sum of array elements that can be obtained? Remember, a bit can be set in atmost N - 1 integers to obtain A_1 & A_2 & .... & A_N = 0.
Hint 2
For a fixed maximum element x, say the maximum sum of array elements obtained is S. Then we can create any valid array with \sum_{i=1}^{N}A_i \le S.
Hint 3
Try to think of binary search.
Solution
Let x is the maximum array element of array A of length N and F(x, N) denotes the maximum sum of the array elements that can be obtained satisfing A_1 & A_2 & .... & A_N = 0 .
How to calculate the value of F(x, N)?
Say N = 4, x = (101001101)_2, Then one possible way to obtain the maximum sum of array element is:
Index of bits: \;876543210
\;\;\; \;\;\;\; \;\; \;\;A_1 : (101001000)_2
\;\;\; \;\;\;\; \;\; \;\;A_2 : (101000111)_2
\;\;\; \;\;\;\; \;\; \;\;A_3 : (100111111)_2
\;\;\; \;\;\;\; \;\; \;\;A_4 : (011111111)_2
We set the bits from the most significant bit to the least significant bit. We have to unset a fixed bit in atleast one of the integers of the array to obtain a bitwise AND equal to 0.
- First we set the 8^{th} bit in A_1, A_2, A_3 and unset in A_4. Also, we set the remaining bits of A_4(i.e from 7^{th} bit to 0^{th} bit).
- Now the 7^{th} bit is already set in A_4. We can’t set this bit in any other integer, as it would result in numbers greater than the maximum element of the array.
- The 6^{th} is already set in A_4. Now we set this bit in A_1, A_2 and unset in A_3. Also, we set the remaining bits of A_3(i.e from 5^{th} bit to 0^{th} bit).
- Now the 5^{th} bit is set in A_3, A_4, we can’t set this bit in any more integer, as it would result in numbers greater than the maximum element of the array.
…
…
(We repeat this process for the remaining bits)
Say, the i^{th} bit can be set in atmost K integers. Now from the above observation, we can see that for every bit two cases occur:
- If the i^{th} bit is set in the x, then K = N - 1.
- Otherwise, K = min(N - 1, the number of set bits in x on the left of i^{th} bit).
Thus F(x, N) = \sum_{i = 0}^{i = 30}(K \cdot 2^i).
How to create a valid array of length N with a sum S which is less than F(x, N)?
Traverse from bit i = 30 to i = 0: Say the i^{th} bit can be set in atmost K integers. Now two cases may occur:
- S \ge K \cdot 2 ^ i: Set the i^{th} bit set in K integers, do S = S - K \cdot 2 ^ i and continue with the remaining bits.
- S \lt K \cdot 2 ^ i: Say M = \lfloor \frac{S}{2^i} \rfloor, now set the i^{th} bit set in M integers and do S = S - M \cdot 2 ^ i. It is guaranteed that K \gt M. So we could have set the i^{th} bit in (K -M) different integers and the remaining value of S \lt 2 ^i. Hence we add the remaining S to one of these (K-M) integers. Now the sum of array elements is equal to S, hence we can terminate the loop.
How does binary search work?
It is obvious that if x_1 \lt x_2, then F(x_1, N) \lt F(x_2, N). So we can apply binary search over the value of x and find the minimum x with F(x, N) \ge S.
Further optimization
Make sure you have gone through the above solution.
A bit can be set in atmost (N - 1) integers. So if we want to construct a valid array considering from 0^{th} bit to i^{th} bit, the maximum sum that can be obtained is
= (N-1) \cdot \sum_{k = 0}^{k = i}2 ^k. So first find the minimum value of i such that (N - 1) \cdot \sum_{k = 0}^{k = i}2 ^ k \ge S.
Say the minimum possible value of the maximum element is X. Initially take X = 0, so the maximum sum of elements that can be obtained, denoted by S' should also be 0. Take another variable cnt = 0. Now traverse from bit j = i to j=0, for every bit first check:
Can we unset the j-th bit in X?
What is the maximum sum of array elements that can be obtained if the j^{th} bit is not set in X?
Here cnt denotes the number of bits from i^{th} bit to (j + 1)^{th} which we have set in X. If we unset the j^{th} bit in X, then the j^{th} bit can be set atmost \min(N - 1, cnt) elements of A, the bits after the j^{th} bit (i.e from (j-1)^{th} bit to 0^{th} bit) can be set in in atmost (N-1) integers. So the maximum sum obtained by unsettling j^{th} bit in X is S' + \min(N - 1, cnt) \cdot 2 ^ j + (N - 1) \cdot \sum_{k = 0} ^ {j - 1} 2 ^ k.
If this value is greater or equal to S, we can unset the j^{th} bit in X and increment the value of S' with \min(N - 1, cnt) \cdot 2 ^ j .
Otherwise.....
We have to set the j^{th} bit in X and set j^{th} bit in (N-1) integers of A, so we increase the value of S' by (N - 1) \cdot 2 ^ j .and increment the value of cnt by 1.
TIME COMPLEXITY:
O(\log S) or O(\log^2 S) for each test case.
SOLUTION:
Setter's solution - log^2 (S) approach
#include<bits/stdc++.h>
using namespace std;
template<class T> inline T Bit(T x, int i) { return (x >> i) & 1;}
void solve(int tc) {
int n, s;
cin >> n >> s;
int l = 1, r = s, ans;
while (l <= r) {
int mid = (l + r) / 2;
long long sum = 0;
int cnt = 0;
for (int i = 30; i >= 0; i--) {
if (Bit(mid, i)) {
sum += 1LL * (n - 1) * (1LL << i);
cnt = min(++cnt, n - 1);
} else {
sum += 1LL * cnt * (1LL << i);
}
}
if (sum >= s) {
r = mid - 1;
ans = mid;
} else {
l = mid + 1;
}
}
cout << ans << '\n';
}
int main() {
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t = 1;
cin >> t;
for (int i = 1; i <= t; i++) solve(i);
}
Admin's (Utkarsh.25dec) solution - log (S) approach
//Utkarsh.25dec
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
void solve()
{
ll n,m;
cin>>n>>m;
ll sum[35]={0};
sum[0]=1;
for(int i=1;i<=32;i++)
sum[i]=sum[i-1]+(1LL<<i);
ll ans=0;
for(int b=0;b<=35;b++)
{
if((sum[b]*(n-1))>=m)
{
ans|=(1LL<<b);
ll good=min(n-1,m/(1LL<<b));
ll bad=n-good;
m-=(good*(1LL<<b));
for(int bit=b-1;bit>=0;bit--)
{
ll tmp=0;
if(bit>=1)
tmp=sum[bit-1]*(n-1);
if(((bad*(1<<bit))+tmp)>=m)
{
int use=min(bad,m/(1LL<<bit));
m-=(use*(1LL<<bit));
}
else
{
int use=min(n-1,m/(1LL<<bit));
int exceed=use-bad;
good=exceed;
bad=n-good;
m-=(use*(1LL<<bit));
ans|=(1LL<<bit);
}
}
break;
}
}
cout<<ans<<'\n';
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
int T=1;
cin>>T;
while(T--)
solve();
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Tester 1's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, s;
cin >> n >> s;
int low = 0;
int high = s;
while (high - low > 1) {
int mid = (high + low) >> 1;
long long x = mid * 1LL * n;
int cnt = 0;
for (int i = 30; i >= 0; i--) {
if (mid & (1 << i)) {
cnt++;
if (cnt >= n) {
x -= 1 << i;
} else {
x -= mid;
x += (mid - (1 << i)) | ((1 << i) - 1);
}
}
}
if (x >= s) {
high = mid;
} else {
low = mid;
}
}
cout << high << endl;
}
return 0;
}
Tester 2's Solution
#include <iostream>
using namespace std;
int main() {
int t;
cin >> t;
while(t--) {
long long int n, s;
cin >> n >> s;
long long int mx = n, mn = 0, ans = 0;
for(int i = 29; i > -1; i--) {
long long int val = (1LL<<i);
long long int req = s/val;
if(req > n - 1) req = n - 1;
if(!req) continue;
if(mn >= req) {
s -= req*val;
} else {
if(s - mn*val <= (n - 1)*(val - 1)) {
s -= mn*val;
} else {
ans |= val;
int mnreq = req;
s -= mnreq*val;
mnreq -= mn;
mx = mnreq;
mn = n - mx;
}
}
}
cout << ans << "\n";
}
return 0;
}