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.
