# CHEFFFUNC - Editorial

**URL:** <https://discuss.codechef.com/t/chefffunc-editorial/104998>\
**Category:** editorial\
**Tags:** editorial, bitwise-operation, start75\
**Created:** [January 25, 2023, 8:59am UTC](https://discuss.codechef.com/t/chefffunc-editorial/104998 "2023-01-25T08:59:15Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![iceknight1093](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@iceknight1093](https://discuss.codechef.com/u/iceknight1093)\
**Post date:** [January 25, 2023, 8:59am UTC](https://discuss.codechef.com/t/chefffunc-editorial/104998/1 "2023-01-25T08:59:15Z")

</div>

# PROBLEM LINK:

[Practice](https://www.codechef.com/problems/CHEFFFUNC)  
[Contest: Division 1](https://www.codechef.com/START75A/problems/CHEFFFUNC)  
[Contest: Division 2](https://www.codechef.com/START75B/problems/CHEFFFUNC)  
[Contest: Division 3](https://www.codechef.com/START75C/problems/CHEFFFUNC)  
[Contest: Division 4](https://www.codechef.com/START75D/problems/CHEFFFUNC)

_ **Author:** _ [indreshsingh](https://www.codechef.com/users/indreshsingh)  
_ **Testers:** _ [iceknight1093](https://www.codechef.com/users/iceknight1093), [rivalq](https://www.codechef.com/users/rivalq)  
_ **Editorialist:** _ [iceknight1093](https://www.codechef.com/users/IceKnight1093)

# DIFFICULTY:

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](https://oeis.org/) 😛 )  
[details = 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.  
[/details]  
[details = 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.  
[/details]

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:

[details = Setter’s code (C++)]

```cpp
#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;
}

```

[/details]  
[details = Editorialist’s code (Python)]

```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
input = sys.stdin.readline
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)

```

[/details]

---

<div class="post-metadata">

**Author:** ![ayushverma09](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@ayushverma09](https://discuss.codechef.com/u/ayushverma09)\
**Post date:** [January 26, 2023, 5:45pm UTC](https://discuss.codechef.com/t/chefffunc-editorial/104998/2 "2023-01-26T17:45:13Z")

</div>

```auto
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)

```

---

<div class="post-metadata">

**Author:** ![frankli](https://discuss.codechef.com/user_avatar/discuss.codechef.com/frankli/32/147360_2.png) [@frankli](https://discuss.codechef.com/u/frankli)\
**Post date:** [January 26, 2023, 5:53pm UTC](https://discuss.codechef.com/t/chefffunc-editorial/104998/3 "2023-01-26T17:53:25Z")

</div>

@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

Mine: [CodeChef: Practical coding for everyone](https://www.codechef.com/viewsolution/87024509)

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

---

<div class="post-metadata">

**Author:** ![indreshsingh](https://discuss.codechef.com/user_avatar/discuss.codechef.com/indreshsingh/32/208155_2.png) [@indreshsingh](https://discuss.codechef.com/u/indreshsingh)\
**Post date:** [January 26, 2023, 6:29pm UTC](https://discuss.codechef.com/t/chefffunc-editorial/104998/4 "2023-01-26T18:29:24Z")

</div>

Failing test case is  
l=79,r=93

---

<div class="post-metadata">

**Author:** ![frankli](https://discuss.codechef.com/user_avatar/discuss.codechef.com/frankli/32/147360_2.png) [@frankli](https://discuss.codechef.com/u/frankli)\
**Post date:** [January 27, 2023, 12:24am UTC](https://discuss.codechef.com/t/chefffunc-editorial/104998/5 "2023-01-27T00:24:35Z")

</div>

Cool, thanks. That explains the reason

---

<div class="post-metadata">

**Author:** ![aaryan\_verma](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@aaryan\_verma](https://discuss.codechef.com/u/aaryan_verma)\
**Post date:** [January 27, 2023, 10:21am UTC](https://discuss.codechef.com/t/chefffunc-editorial/104998/6 "2023-01-27T10:21:46Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![pixel3user](https://discuss.codechef.com/user_avatar/discuss.codechef.com/pixel3user/32/172400_2.png) [@pixel3user](https://discuss.codechef.com/u/pixel3user)\
**Post date:** [January 30, 2023, 3:45pm UTC](https://discuss.codechef.com/t/chefffunc-editorial/104998/7 "2023-01-30T15:45:36Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![vantaablackk](https://discuss.codechef.com/user_avatar/discuss.codechef.com/vantaablackk/32/208155_2.png) [@vantaablackk](https://discuss.codechef.com/u/vantaablackk)\
**Post date:** [January 31, 2023, 5:12pm UTC](https://discuss.codechef.com/t/chefffunc-editorial/104998/8 "2023-01-31T17:12:58Z")

</div>

![image](https://s3.amazonaws.com/discourseproduction/original/3X/f/6/f6f036230034d029b0e3753c474036de88095ad4.png)

I don’t understand how the above was generalised to these 2 properties below

![image](https://s3.amazonaws.com/discourseproduction/original/3X/d/5/d5da446f9ae1b17dc9c4b2ef0f918ab704b29292.png)

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.

---

<div class="post-metadata">

**Author:** ![iceknight1093](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@iceknight1093](https://discuss.codechef.com/u/iceknight1093)\
**Post date:** [January 31, 2023, 5:33pm UTC](https://discuss.codechef.com/t/chefffunc-editorial/104998/9 "2023-01-31T17:33:50Z")

</div>

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.

> [@iceknight1093](#):
>
> In other words, g(x) is obtained by _inverting all the bits of x_, except for the highest bit.

The points in your second image follow from this characterization.

---

<div class="post-metadata">

**Author:** ![ayush\_8303](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@ayush\_8303](https://discuss.codechef.com/u/ayush_8303)\
**Post date:** [January 31, 2023, 8:32pm UTC](https://discuss.codechef.com/t/chefffunc-editorial/104998/10 "2023-01-31T20:32:14Z")

</div>

> [@iceknight1093](#):
>
> it’s enough to check for x=L, L+1, …, L+31 .

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

---

<div class="post-metadata">

**Author:** ![iceknight1093](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@iceknight1093](https://discuss.codechef.com/u/iceknight1093)\
**Post date:** [February 1, 2023, 4:04am UTC](https://discuss.codechef.com/t/chefffunc-editorial/104998/11 "2023-02-01T04:04:05Z")

</div>

See this section:

> [@iceknight1093](#):
>
> Notice our third point above: g is a strictly decreasing function on this range, i.e, g(L)\>g(L+1)\>…\>g(R)  
> Also recall that f can only take values upto 30.
> 
> So, for any x\>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.

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.
