PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Setter: Prakhar Kochar
Tester: Tejas Pandey, Abhinav Sharma
Editorialist: Kanhaiya Mohan
DIFFICULTY:
Easy
PREREQUISITES:
None
PROBLEM:
Chef is given a contract to build towers in Chefland which are made by stacking blocks one above the other. Initially, there is only 1 block in the inventory and no tower has been built. Chef follows the following 2 steps in each operation:
- Step 1: Either build a new tower or update an existing tower that has been built in previous operations using the blocks currently present in the inventory. After this step, the size of the inventory reduces by the number of blocks used.
- Step 2: Suppose the tower Chef updated or built in Step 1 has B blocks after the step. Chef gets to add B new blocks to the inventory as a reward.
Find the maximum number of towers of height X Chef can build in M operations.
QUICK EXPLANATION:
- If M<(ceil(log_2(X))+1), the answer is 0.
- Else, we can build M-ceil(log_2(X)) towers of height X.
EXPLANATION:
Observation
Note that the reward for an operation is equal to the number of blocks present in the last built or updated tower. To maximise this reward, it is optimal to update an existing tower instead of building a new one, since the former one would always have more blocks. If we keep updating the current tower, the reward increases exponentially.
Building a single tower of height X
Let us build the first tower of height X. We have 1 block initially. We use it to build a tower of height 1. We now get a reward of 1 block. If we update the current tower using this, the height of the tower becomes 2. After the reward for this move, the inventory size is also 2.
We continue using the whole inventory to build and update a single tower until it reaches the height X.
The inventory size forms a sequence while we do this process: 1, 1, 2, 4, 8, 16, 32, ….
Once the sum of this sequence reaches X, we have our first tower of height greater than equal to X.
Minimum operations required to reach the sum X can either be calculated using brute force (in O(log_2X) complexity) or using the formula (ceil(log_2(X))+1) (in O(1) complexity).
If the minimum operations required is greater than M, we cannot build even a single tower and the answer is 0.
Building maximum number of towers
Once we have built our first tower of required size, we have atleast X blocks in our inventory (due to our last operation). For all the remaining operations, we build a new tower of height X in each operation.
To sum up, the answer is 0, if M<(ceil(log_2(X))+1), else, we can build M-ceil(log_2(X)) towers of height X in M operations.
TIME COMPLEXITY:
The time complexity is O(1) per test case.
SOLUTION:
Setter's Solution
t = int(input())
for _ in range(0 ,t):
x, m = map(int, input().split())
cnt = 1; size = 0; k = 0
while(m != 0):
m -= 1
size += cnt
if(size >= x):
m += 1
break
k += 1
if(k == 1):
cnt = 1
else:
cnt *= 2
if(m < 0):
print(0)
else:
print(m)
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r" , stdin);
freopen("output.txt", "w" , stdout);
#endif
int T=1;
cin >> T;
while(T--){
ll x,m;
cin>>x>>m;
ll curr_sz = 1;
ll len = 0;
ll ops = 0;
while(len < x){
len+=curr_sz;
curr_sz = len;
ops++;
}
cout<<max(0ll, m-ops+1)<<'\n';
}
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
long long int x, m;
cin>>x>>m;
long long int minm = ceil(log2(x))+1;
if(m < minm){
cout<<0;
}
else{
cout<<m - minm + 1;
}
cout<<endl;
}
return 0;
}