ODDBITS - Editorial

PROBLEM LINK:

Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1

Author: Soumyadeep Pal
Tester: Manan Grover
Editorialist: Vichitr Gandas

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Binary Search, Digit DP

PROBLEM:

Find the minimum integer K such that sum of bits present on odd positions in binary representation of all integers from 1 to K is greater than or equal to N.

QUICK EXPLANATION

Use digit DP to find sum of bits present on odd positions in binary presentation of all integer from 1 to K for a particular K. As the sum would only increase with increasing K hence we can binary search on K.

EXPLANATION

Lets define a function F(K) as sum of bits present on odd positions in binary representation of all integers between 1 to K. As sum would increase if we increase K hence
F(K+1) \ge F(K)

As F is a non-decreasing function, this gives an ideal condition to binary search on K such that F(K) \ge N.

Now the task is reduced to find F(K) for a given K. This can be easily found with digit dp.

Let B be the binary representation of K and its length be len. Consider 1-based indexing in rest of the editorial.
Let dp1[pos][tight] represent the count of numbers which are \le B[pos: len].
Here B[pos: len] represents the substring of B starting from index pos upto end.
Here tight is a boolean which represents if previous bits ie from index 1 to pos-1 are chosen exactly same as they are in B.

Now first let’s calculate dp1.
Case 1: tight = 1
This means all previous bits have been chosen as it is, hence current bit can be selected <= B[pos]. Otherwise current number would be greater than K. Hence,

  • If B[pos] = 0, we can select current bit as only 0 so dp transition would be as following:
    dp1[pos][tight] = dp1[pos+1][tight].
  • If B[pos] = 1, we have two choices for current bit as either 0 or 1. If we choose 0, tight would become 0 as the number would no more remain same as B upto current index. And if we choose current digit as 1, tight would remain 1 only so dp transition would be as following:
    dp1[pos][tight] = dp1[pos+1][0] + dp1[pos+1][1].

Case 2: tight = 0
If tight = 0, then we can use either 0 or 1 for current bit as the number would always be <K hence dp transition would be:
dp1[pos][tight] = dp1[pos+1][tight] + dp1[pos+1][tight].

Calculating F(K) with DP

Now we will use this dp to calculate F. Let dp2[pos][tight][parity] represent the sum of odd bits of numbers which started from an index with odd-even parity as parity and are \le B[pos: len].
Here B[pos: len] represents the substring of B starting from index pos upto end.
Here tight is a boolean which represents if previous bits ie from index 1 to pos-1 are chosen exactly same as they are in B.
Here if start index was odd then parity=1, if start index was even then parity=0. Initially we will say parity=2 if start index is not known.

Now lets calculate dp2. Two cases here as well:
Case 1: tight = 1
Here if B[pos] = 0, current bit won’t contribute anything to the sum as its 0. Sum value would be equal to the sum we get from next index. Hence dp transition can be written as following:

  • dp2[pos][tight][parity] = dp2[pos+1][tight][parity]

If B[pos] = 1

  • We can either select 0 for current bit
    • In that case, tight would become 0 and sum would be equal to the sum we get from next index ie dp2[pos+1][0][parity].
  • Or we can also choose 1 for current bit
    • If parity = 2 then it would become parity = pos \% 2 as pos would be start position because of picking current bit as 1.
    • Current bit would contribute only if the current pos is at odd position from start ie (pos-parity) \% 2 = 0.
    • Also the contribution from current bit would be dp1[pos+1][tight]. Because the count of numbers which can be formed <=K after fixing current bit as 1 is dp1[pos+1][tight].
    • Contribution from next index ie dp2[pos+1][tight][pos \% 2] would also be added as we are finding sum.
  • To find the sum, we add the values we get from both choices.

Hence the dp transition can be written as following:

dp2[pos][tight][parity] = dp2[pos+1][0][parity] + dp2[pos+1][tight][pos \% 2] + ((pos-parity) \% 2 == 0) ? dp1[pos+1][tight] : 0.

Case 2: tight = 0
In this case, we always have 2 choices for current bit.

  • If we select current bit as 0, the sum would be equal to dp2[pos+1][tight][parity].
  • If we select current bit as 1
    • If parity = 2 then it would become parity = pos \% 2 as pos would be start position because of picking current bit as 1.
    • Current bit would contribute only if the current pos is at odd position from start ie (pos-parity) \% 2 = 0.
    • Also the contribution from current bit would be dp1[pos+1][tight]. Because the count of numbers which can be formed <=K after fixing current bit as 1 is dp1[pos+1][tight].
    • Contribution from next index ie dp2[pos+1][tight][pos \% 2] would also be added as we are finding sum.
  • To find the sum, we add the values we get from both choices.

Hence the dp transition can be written as following:

dp2[pos][tight][parity] = dp2[pos+1][tight][parity] + dp2[pos+1][tight][pos \% 2] +((pos-parity) \% 2 == 0) ? dp1[pos+1][tight] : 0.

TIME COMPLEXITY:

O(10 \cdot log^2n) per test case

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long

long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        // char g = getc(fp);
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
            
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }
            // cerr << x << " " << l << " " << r << endl;
            assert(l<=x && x<=r);
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        // char g=getc(fp);
        assert(g != -1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}

int sz, n;
int cache[32][2][3], ways[32][2];

int dp1(string &s, int idx = 0, int tight = 1) {
	if (idx == sz) {
		return ways[idx][tight] = 1;
	}
	int &ans = ways[idx][tight];
	if (ans != -1) return ans;
	ans = 0;
	int last = 1;
	if (tight) last = s[idx] - '0';
	for (int i = 0; i <= last; ++i) {
		ans += dp1(s, idx + 1, tight && (i == last));
	}
	// cout << idx << " " << tight << " " << ans << endl;
	return ans;
}

int dp2(string &s, int idx = 0, int tight = 1, int start_bit = 2) {
	if (idx == sz) {
		return 0;
	}
	int &ans = cache[idx][tight][start_bit];
	if (ans != -1) return ans;
	ans = 0;
	int last = 1;
	if (tight) last = s[idx] - '0';
	for (int i = 0; i <= last; ++i) {
		if (start_bit == 2 and i == 1) start_bit = idx % 2;
		int cur = 0;
		if (i == 1) {
			int idx_from_left = (idx - start_bit);
			cur = (idx_from_left & 1 ? 0 : 1);
		}
		int tight1 = tight && (i == last);
		ans += (cur * ways[idx + 1][tight1]) + dp2(s, idx + 1, tight1, start_bit);
	}
	return ans;
}

int check(int x) {
	string s;
	while (x > 0) {
		s.push_back((char)(x % 2 + '0'));
		x /= 2;
	}
	reverse(s.begin(), s.end());
	sz = (int)(s.size());
	memset(cache, -1, sizeof(cache));
	memset(ways, -1, sizeof(ways));
	dp1(s);
	int y = dp2(s);
	// cout << s << " " << y << endl;
	return y;
}

int32_t main() {
	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t = readIntLn(1, 1000);
	while (t--) {
		int n = readIntLn(1, 1000000000);
		int st = 1, end = n, ans = 1e10;
		while (st <= end) {
			int mid = (st + end) / 2;
			if (check(mid) >= n) {
				ans = mid;
				end = mid - 1;
			} else {
				st = mid + 1;
			}
		}
		cout << ans << '\n';
	}
	assert(getchar()==-1);
	return 0;
}

Tester's Solution
#include <bits/stdc++.h>
using namespace std;
int n;
bool check(int x){
  long long ans = 0;
  int temp = 1;
  int cnt = -1;
  while(true){
    temp *= 2;
    cnt++;
    int len = min(temp, x + 1) - temp / 2;
    ans += len;
    if(temp <= x + 1){
      ans += (len / 2) * (cnt / 2);
    }else{
      if(cnt % 2){
        temp = 4;
      }else{
        temp = 2;
      }
      cnt /= 2;
      for(int i = 0; i < cnt; i++){
        int y = len % temp;
        ans += (len - y) / 2;
        ans += max(0, y - temp / 2);
        temp *= 4;
      }
      break;
    }
  }
  return n <= ans;
}
int main(){
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  int t;
  cin>>t;
  while(t--){
    cin>>n;
    int ans;
    int l = 1, r = n;
    while(l <= r){
      int mid = (r + l) / 2;
      if(check(mid)){
        ans = mid;
        r = mid - 1;
      }else{
        l = mid + 1;
      }
    }
    cout<<ans<<"\n";
  }
  return 0;
}
Editorialist's Solution
/*
 * @author: vichitr
 * @date: 25th July 2021
 */

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fast ios::sync_with_stdio(0); cin.tie(0);

int n, dp1[33][2], dp2[33][2][3];
string B;

int sol1(int pos, int tight) {
	if (pos == B.size())
		return 1;
	int &ans = dp1[pos][tight];
	if (ans != -1)
		return ans;
	ans = 0;
	if (tight == 1) {
		if (B[pos] == '0')
			ans = sol1(pos + 1, tight);
		else {
			ans = sol1(pos + 1, 0) + sol1(pos + 1, 1);
		}
	}
	else {
		ans = sol1(pos + 1, tight) * 2;
	}
	return ans;
}

int sol2(int pos, int tight, int parity) {
	if (pos == B.size())
		return 0;
	int &ans = dp2[pos][tight][parity];
	if (ans != -1)
		return ans;
	ans = 0;
	if (tight) {
		if (B[pos] == '0')
			ans = sol2(pos + 1, tight, parity);
		else {
			// current bit as 0
			ans += sol2(pos + 1, 0, parity);
			// current bit as 1
			// if parity is still 2 then update it with current pos
			if (parity == 2) parity = pos % 2;
			// ans from next index for  choice 1 for current bit
			ans += sol2(pos + 1, 1, parity);
			// if cur pos is odd position from start then add
			// contribution of current bit
			if ((pos - parity) % 2 == 0)
				ans += sol1(pos + 1, tight);
		}
	}
	else {
		// current bit as 0
		ans += sol2(pos + 1, tight, parity);
		// current bit as 1
		// if parity is still 2 then update it with current pos
		if (parity == 2) parity = pos % 2;
		// ans from next index for choice 1 for current bit
		ans += sol2(pos + 1, tight, parity);
		// if cur pos is odd position from start then add
		// contribution of current bit
		if ((pos - parity) % 2 == 0)
			ans += sol1(pos + 1, tight);
	}
	return ans;
}

bool check(int x) {
	memset(dp1, -1, sizeof dp1);
	memset(dp2, -1, sizeof dp2);
	B.clear();
	while (x) {
		B += (char)(x % 2 + '0');
		x /= 2;
	}
	B += '0';
	reverse(B.begin(), B.end());
	return sol2(1, 1, 2) >= n;
}

void solve() {
	cin >> n;
	int ans = 0, s = 0, e = n;
	while (s <= e) {
		int m = (s + e) / 2;
		if (check(m)) {
			ans = m;
			e = m - 1;
		}
		else
			s = m + 1;
	}
	cout << ans << '\n';
}

signed main() {
	fast;

#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif

	int t = 1;
	cin >> t;
	for (int tt = 1; tt <= t; tt++) {
		// cout << "Case #" << tt << ": ";
		solve();
	}
	return 0;
}

VIDEO EDITORIAL:

If you have other approaches or solutions, let’s discuss in comments.If you have other approaches or solutions, let’s discuss in comments.

6 Likes

My solution without digit dp with standard contribution counting \mathcal{O}(\log^3N) Solution

3 Likes

Ya it’s again a nice solution. We kept the time limit such that upto logn * log n* 100 solutions easily pass because the digit dp can be implemented in many ways.

1 Like

Can you please explain your method

can anyone explain Tester Sol’n ?

What I can understand is he is doing counting. Other than this, it’s out of my head :frowning:

2 Likes

Not sure if this should have passed, but the solution is much simpler if one just knows the basics of digit dp. Let’s make a dp[start\_pos][cur\_idx][cur\_sum][tight] to calculate the count of bits at odd positions from 1 to K. start\_pos denotes the starting position of binary number, cur\_idx denotes the index where we are currently, cur\_sum stores the current odd bits sum and tight is the usual variable 0/1 .
Once we have fixed the starting position, we just need to change cur\_idx, cur\_sum depends on start\_pos and cur\_idx. Rest implementation is mostly taken from here.

1 Like

As size can be at most ~32 hence overall it takes O(32 \cdot 32 \cdot 32 \cdot 2 \cdot 2). This should pass with current constraints. Yeah this one doesn’t require much thinking on the conditions.
Also we can easily reduce it to O(32 \cdot 32 \cdot 2 \cdot 2 \cdot 2) by storing parity of start index instead of actual start index.

Some resources that helped me in understanding the editorial better:

An easier but slower solution:
The main crux is,
oddsetbits(n) = oddsetbits(n/2) + x
x = 1, if the last bit is set and is in odd position
https://www.codechef.com/viewsolution/49086007

1 Like

My solution Solution: 49085941 | CodeChef is slightly faster because I precomputed array b. Elements of array b are sums of bits at odd positions in numbers from 1 to k, where k is power of two.

1 Like

@vichitr

Why does the editorilist’s solution fail when we do not use ans reference, but instead change every instance of &ans for the respective dp value?

Here’s code that doesn’t produce correct answer for any case (even the samples) which is the same as editorialist’s but without references:

CODE
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fast ios::sync_with_stdio(0); cin.tie(0);

int n, dp1[33][2], dp2[33][2][3];
string B;

int sol1(int pos, int tight) {
	if (pos == B.size())
		return 1;
	int &ans = dp1[pos][tight];
	if (ans != -1)
		return ans;
	ans = 0;
	if (tight == 1) {
		if (B[pos] == '0')
			ans = sol1(pos + 1, tight);
		else {
			ans = sol1(pos + 1, 0) + sol1(pos + 1, 1);
		}
	}
	else {
		ans = sol1(pos + 1, tight) * 2;
	}
	return ans;
}

int sol2(int pos, int tight, int parity) {
	if (pos == B.size())
		return 0;
	// int &ans = dp2[pos][tight][parity];
	if (dp2[pos][tight][parity] != -1)
		return dp2[pos][tight][parity];
	dp2[pos][tight][parity] = 0;
	if (tight) {
		if (B[pos] == '0')
			dp2[pos][tight][parity] = sol2(pos + 1, tight, parity);
		else {
			// current bit as 0
			dp2[pos][tight][parity] += sol2(pos + 1, 0, parity);
			// current bit as 1
			// if parity is still 2 then update it with current pos
			if (parity == 2) parity = pos % 2;
			// ans from next index for  choice 1 for current bit
			dp2[pos][tight][parity] += sol2(pos + 1, 1, parity);
			// if cur pos is odd position from start then add
			// contribution of current bit
			if ((pos - parity) % 2 == 0)
				dp2[pos][tight][parity] += sol1(pos + 1, tight);
		}
	}
	else {
		// current bit as 0
		dp2[pos][tight][parity] += sol2(pos + 1, tight, parity);
		// current bit as 1
		// if parity is still 2 then update it with current pos
		if (parity == 2) parity = pos % 2;
		// ans from next index for choice 1 for current bit
		dp2[pos][tight][parity] += sol2(pos + 1, tight, parity);
		// if cur pos is odd position from start then add
		// contribution of current bit
		if ((pos - parity) % 2 == 0)
			dp2[pos][tight][parity] += sol1(pos + 1, tight);
	}
	return dp2[pos][tight][parity];
}

bool check(int x) {
	memset(dp1, -1, sizeof dp1);
	memset(dp2, -1, sizeof dp2);
	B.clear();
	while (x) {
		B += (char)(x % 2 + '0');
		x /= 2;
	}
	B += '0';
	reverse(B.begin(), B.end());
	return sol2(1, 1, 2) >= n;
}

void solve() {
	cin >> n;
	int ans = 0, s = 0, e = n;
	while (s <= e) {
		int m = (s + e) / 2;
		if (check(m)) {
			ans = m;
			e = m - 1;
		}
		else
			s = m + 1;
	}
	cout << ans << '\n';
}

signed main() {
	fast;
    int t;
	cin >> t;
	for (int tt = 1; tt <= t; tt++) {
		// cout << "Case #" << tt << ": ";
		solve();
	}
	return 0;
}

It only makes a difference when used in sol2. Could someone elaborate on this, I really see no reason why this wouldn’t work. I was always convinced using references for this type of stuff just makes it a bit easier to write, but i’ve tried to edit it multiple times and it always fails when this is changed.

Because we are updating tight and parity inside conditions. Did you notice that?

if (parity == 2) parity = pos % 2;

So instead of saving to older dp[pos][tight][parity], you are adding to some other state.
One way to fix is to use new variables tight1 and parity1 inside conditions and making next calls with them and keeping original tight and parity values as it is.

1 Like

Oh my bad! I was confused about this for the past few hours, really silly mistake on my end. Sorry for unnecessary tag and thanks for clarifying, now it makes sense.

1 Like

No issues. Glad it helped. :slight_smile:

why not video tutorial is not out yet?? Eagerly waiting.