 # CHEFFFUNC - Editorial

Author: indreshsingh
Testers: iceknight1093, rivalq
Editorialist: iceknight1093

TBD

# PREREQUISITES:

Familiarity with bitwise operations

# PROBLEM:

You’re given two functions f and g, whose definitions can be found in the statement.
You’re also given integers L and R.

Find the maximum value of f(x) + g(x) across all L \leq x \leq R.

# EXPLANATION:

Our first order of business should be figuring out what the functions f and g actually are, since they’re given to us in a recursive form.

This can be done by analyzing them a bit (or computing a few early values and putting the sequence into OEIS )

Computing f(x)

Looking at the definition of f should make you think of binary, since computing it requires us to divide by 2 each time.

You should quickly notice that, in terms of binary:

• If the last digit is 0 (meaning the number is even), we add 1 to the answer; otherwise we add 0 to the answer.
• Then, we delete the last digit (which corresponds to dividing by 2)

In other words, f(x) is simply the number of zeros in the binary representation of x.

Computing g(x)

Looking at the definition of g, we see the following:

• Suppose x = 2k. Then, g(x) = 2\cdot g(k)+1.
• Suppose x = 2k+1. Then, g(x) = 2\cdot g(k).

Notice that these are suspiciously similar: obtaining x from k is exactly the opposite of obtaining g(x) from g(k); in terms of adding 1 after multiplying by 2.

Now let’s contextualize this in terms of binary.
Any integer x can be obtained by starting with 1, then continually multiplying by 2 and adding either zero or one, depending on whether we need to add a new bit or not.

We can thus build g(x) as we build x; except that we add a bit to g(x) if and only if we don’t add a bit to x.

In other words, g(x) is obtained by inverting all the bits of x, except for the highest bit.

For example, if x = 17 = 1\color{red}{0001}\color{black}{_2}, then g(x) = 1\color{red}{1110}\color{black}{_2} = 30.

Now that we know f and g, let’s observe a couple of their properties.

• f(x) is pretty small: since x \leq R \leq 10^9, we have f(x) \leq 30.
• f(x) is largest when x is a power of 2.
• If x+1 is not a power of 2, then g(x) \gt g(x+1).
• In fact, if x+1 is not a power of 2, then g(x) = g(x+1)+1.
• If x+1 is a power of 2, then g(x) \lt g(x+1).
• In this case, g(x+1) is larger than g(y) for every y \leq x.

The above discussion tells us that to maximize f(x)+g(x), ideally x should be a power of 2.
So, if the range [L, R] contains a power of 2, simply choose x to be the largest power of 2 in this range and compute f(x) + g(x) for it — that’s the answer.

Now, what about when [L, R] doesn’t contain a power of 2?
Notice our third point above: g is a strictly decreasing function on this range, i.e, g(L)\gt g(L+1) \gt \ldots \gt g(R).
Also recall that f can only take values upto 30.

So, for any x \gt L+31, f(x)+g(x) can never be larger than f(L)+g(L), since f cannot make up for the difference between the g-values.

So, it’s enough to check for x = L, L+1, \ldots, L+31.
Compute f(x)+g(x) for each one, take the maximum of them all.

Computing f(x) and/or g(x) for a given x can be done in \mathcal{O}(\log x) using the given recursive definitions.

# TIME COMPLEXITY:

\mathcal{O}(\log^2 R) per testcase.

# CODE:

Setter's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int               long long
#define pb                push_back
#define ppb               pop_back
#define pf                push_front
#define ppf               pop_front
#define all(x)            (x).begin(),(x).end()
#define uniq(v)           (v).erase(unique(all(v)),(v).end())
#define sz(x)             (int)((x).size())
#define fr                first
#define sc                second
#define pii               pair<int,int>
#define rep(i,a,b)        for(int i=a;i<b;i++)
#define mem1(a)           memset(a,-1,sizeof(a))
#define mem0(a)           memset(a,0,sizeof(a))
#define ppc               __builtin_popcount
#define ppcll             __builtin_popcountll
#define debug(x)  cout<<(x)<<'\n';

template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.fr>>a.sc;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.fr<<" "<<a.sc;return out;}
template<typename T,typename T1>T amax(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T amin(T &a,T1 b){if(b<a)a=b;return a;}

const long long INF=1e18;
const int32_t M=1e9+7;
const int32_t MM=998244353;

const int N=0;

//function which gives binary length of n ,eg n=8->1000 length is 4
int countBits(int n)
{
int count = 0;
while (n)
{
count++;
n >>= 1;
}
return count;
}

//binary representation of n
string convertTobinary(int n)
{

string b;

while(n)
{
if(n%2) b.pb('1');
else b.pb('0');
n=n/2;
}

reverse(all(b));
return b;

}

void solve(){

int l,r;
cin>>l>>r;

int length_l,length_r;

length_l=countBits(l);
length_r=countBits(r);

if(length_l<length_r) // eg : l=1,r=3->11 we can make all zeroes except first digit we get 10 so ans=1
{

cout<<length_r-1+(1ll<<(length_r))-1<<'\n';
return;

}

string sl,sr; //binary representation of l and r
int length=length_r;

sl=convertTobinary(l);
sr=convertTobinary(r);
int ans=0;
for(int i=l;i<=min(40+l,r);i++)
{

int j=i;
int curr=0;
int k=0;
while(j)
{

if(j==1)
{
curr+=1ll<<k;
}
else if(j%2==0)
{
curr+=1ll<<k;
}
j=j/2;
k++;

}
j=i;
while(j)
{

if(j%2==0) curr++;
j=j/2;
}

ans=max(ans,curr);

}
cout<<ans<<'\n';

}

signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#ifdef SIEVE
sieve();
#endif
#ifdef NCR
init();
#endif
int t=1;
cin>>t;
while(t--) solve();
return 0;
}

Editorialist's code (Python)
def f(x):
ret = 0
while x > 0:
ret += 1 - x%2
x //= 2
return ret

def g(x):
ret = x
for i in range(30):
if 2**(i+1) > x: break
if x & (1 << i): x -= 1 << i
else: x += 1 << i
return x

import sys
for _ in range(int(input())):
l, r = map(int, input().split())
ans = 0
if len(bin(l)) < len(bin(r)): # [L, R] contains a power of 2
pw = len(bin(r))-3
x = 2**pw
ans = 2*x-1 + pw
else:
pw = 2**(len(bin(l))-3)
for i in range(31):
if l+i > r: break
ans = max(ans, f(l+i) + g(l+i))
print(ans)

1 Like
from functools import cache
@cache
def f(x):
if (x == 1): return 0;
if (x & 1): return f((x - 1) // 2);
return f(x // 2) + 1;
@cache
def g(x):
if (x == 1): return 1;
if (x & 1): return 2 * g((x - 1) // 2);
return 2 * g(x // 2) + 1;

for _ in range(int(input())):
l, r = map(int, input().split())
a = 0
while l <= r:
a = max(a, f(l) + g(l))
l += l & -l
print(a)

1 Like

@iceknight1093 Could you share me the input/output data for one case please?

Because I’m suspicious that my solution would be bigger than just looping L ~ L+30. Please let me know if you can share me only one input/output data set. I know it’s not allowed to share the input/output but I just need partial of it.

@iceknight1093 Or could you please help me to check if my solutions’ output is bigger? I hope you can check the input/output

This solution gets WA but I’m wondering if the output is bigger than the solution

Failing test case is
l=79,r=93

1 Like

Cool, thanks. That explains the reason

@frankli How do we know that the maximum value x can produce is 30 ?

1 Like

if we take x = 536870912 which is less than 10^9 . Then the number x in binary representation will be 100000000000000000000000000000 or 1 followed by 30 zeros. f(x) will give a value of 30 at the value of x.

1 Like I don’t understand how the above was generalised to these 2 properties below The 2 values of x were simply an even value and an odd value, how does it generalise to bigger values of x, like if I put x = 2*k + 2 in formula, it doesn’t seem to hold true.

There’s some writing inbetween those two parts, have you gone through that?
Specifically, I related the binary representation of g(x) to the binary representation of x, and then described what g(x) looks like in terms of x.

1 Like

@iceknight1093
it would be really appreciable if you put some light here … !!

See this section:

Look at f(L+31) + g(L+31).

• g(L+31) = g(L) - 31 (remember that we are in the case where there’s no power of 2 in the range.
• f(L+31) \leq 30
• So, f(L+31) + g(L+31) \leq g(L)-31+30 = g(L)-1 which is obviously strictly less than f(L)+g(L).

You can apply this argument to any f(L+x) + g(L+x) where x \geq 31, as long as you don’t reach the next power of 2.

1 Like