PROBLEM LINK:
Author: Aman Gupta
Tester: Pankaj Sharma
Editorialist: Aman Gupta
DIFFICULTY:
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.