FIXSUM - Editorial

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

Can’t figure out what is role of cnt in binary search solution . Please help.

Please see the part How to calculate the value of F(x, N)?

Shouldn’t this be ?
S' + \min(N - 1, cnt) \cdot 2 ^ j + (N - 1) \cdot \sum_{k = 0} ^ {j - 1} 2 ^ k.

Yes corrected it.