# D2C103 - Editorial

Contest

Author: Aman Gupta
Tester: Pankaj Sharma
Editorialist: Aman Gupta

CAKEWALK

# PREREQUISITES:

Basic observations, Math, Greedy

# PROBLEM:

Chef has to make cuts in Chocolate bar to make minimum K pieces. So that chef can make any length of Chocolate bar of 1\leq length \leq L by adding these pieces of chocolate bar.
Also, the length of pieces of chocolate bar should be in integer.

# QUICK EXPLANATION:

Chef has to make minimum k pieces from the length of chocolate bar L .
The approach is that any Length can be formed 1\leq length \leq L .By dividing the Length of chocolate bar in m+1 different numbers where m=log2(Length).
So the minimum no of pieces of chocolate bar are k=log2(Length)+1.

# EXPLANATION:

The key observation is that any number can be written using distinct powers of two’s.
Consider the length of a chocolate bar as a number N.
See proof here.
Now we have known that we need to split N as sum of distinct powers of two’s.
Now we need to choose minimum numbers by which we can make all numbers from 1 to N.
Now consider binary representation of N = 7 as 111.
We need 3 bits to represent all numbers from 1 to 7. So using 1, 2, 4 we can get all numbers from 1 to 7.
Now to represent all numbers from 1 to N we need only numbers equal to the total number of bits in N which is log_2 N + 1

what if N = 10 and something like this
Binary of 10 = 1010
Now we can use numbers like 1,2,4,3 and we can make all numbers from 1 to 4 using these 4. How ?
using 1,2,4 we can make 1 to 7 right?
So we using 7,6,5 made using 1,2,4 we can make 10,9,8 respectively.
So for general N having k bits we can make we can make all numbers from 1 to 2^{k-1} using k-1 bits and can get any number greater than that is from 2^{k-1}+1 to N by choosing last number as difference of N and required number.

So our answer will be log_2 N + 1

Now coming back to original problem
Lets understand by some examples.
The approach is that any Length can be formed from 1\leq length \leq L .By dividing the Length of chocolate bar in m+1 different numbers where m=log2(Length).

So chef has to cut chocolate bar into minimum k pieces where k=m+1. So that he can make any any size of chocolate bar from these pieces.

For example: Length of chocolate Bar is 6
log2(6) =2
So chef has to make 2 cuts in chocolate bar.These 2 cuts in chocolate bar can generators 3 pieces.
The chocolate bar can be cut into pieces of length 1,2,3 so that we can form any size of chocolate bar.
(1,2,3,4=3+1,5=3+2,6=1+2+3)

# SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>

using namespace std;

int main()
{

int t;
cin>>t;
while(t--)

{

int n;

cin>>n;

cout<<floor(log2(n))+1<<endl;

}

return 0;

}


Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long           ll;
#define all(x) (x).begin(), (x).end()
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 << '\n'; }
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << " = " << arg1 << " | "; __f(comma + 1, args...);
}
void solve() {
ll ans = 0;
ll n;
cin >> n;
ll max = 1e9;
assert(n >= 1 and n <= max);
while (n > 0) {
n /= 2;
ans++;
}
cout << ans << "\n";
}
int main()
{
cin.sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
assert(t >= 1 && t <= 100);
while (t--)
solve();
return 0;
}



For doubts, please leave them in the comment section, I’ll address them.