TOWERTOP - Editorial

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;
}
2 Likes

Guys for some reason this doesnt work until i store the ceil in a value then compare, does anybody know why ?

#include
using namespace std;
    int main(){
    ios::sync_with_stdio(false);
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    long long int t;    
    cin>>t;
    while(t--){
    long long int x,m;
    cin>>x>>m;
    long long int count=0;
    if(m>=ceil(log2(x)+1)){
        count+=1;
    }
    if(m-ceil(log2(x)+1)>=0){
        count+=m-ceil(log2(x)+1);
    }
    cout<
1 Like

can someone please help me about what is wrong in this code

import java.util.*;
public class buildingtowers {
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-- != 0)
{
double x = sc.nextDouble();
double m = sc.nextDouble();
double n;
//double h = 2;
// while(true)
// {
// if(x > Math.pow(h,n-1))
// n++;
// else
// break;
// }
n = Math.ceil(Math.log(x)/Math.log(2.0) + 1);
double ans = m - n;
if(m < n)
System.out.println(“0”);
else
System.out.println((int)ans+1);
}
}
}

Honestly, I had 0 motivation while solving this problem. Stupid scenario. One can frame a more interesting scenario on the same problem.

2 Likes

This code gives the wrong answer for Task #3, can someone please look into the program?

#include
#include<math.h>
#include<bits/stdc++.h>
using namespace std;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int t;
cin>>t;

while(t--)
{
    int x,m;
    cin>>x>>m;

    if(m-ceil(log2(x)) > 0)
      cout<<(m)-ceil(log2(x))<<endl;
    else
      cout<<"0"<<endl;
    
}
return 0;

}

this code is giving me WA in Task#3. Can somebody help me with this?

#define _crt_secure_no_warnings
#include <bits/stdc++.h>

int highestPowerof2(int n)
{
    int res = 0;
    for (int i = n; i >= 1; i--)
    {
        if ((i & (i - 1)) == 0)
        {
            res = i;
            break;
        }
    }
    return res;
}

void solve() {
    int x, m;
    cin >> x >> m;
    int cnt = 0;
    int curnt = highestPowerof2(x);
    //cout << curnt << endl;
    int ops = log2(curnt) + 1;
    int h = curnt;
    if (m < ops) {
        cout << cnt << endl;
        return;
    }
    else {
        m = m - ops;
        if (h == x)cnt++;
        else {
            m--;
            cnt++;
        }
        cout << cnt + m << endl;
        return;
    }
    
}
int main() {
    test;
    while (T--)
        solve();
    return 0;
}

m can be as big as 10^{17}. So use long instead of int.

thanks :blush:

use long long instead of int for m

Thank You!

I understand that Task#3 is failing for me because the number limit in javascript has been reached. Here is my solution which is basically the same as in the video editorial. How do I get around the long long issue. The BigInt datatype isn’t accepted in codechef IDE.

Can you try this?

@suman_18733097 This doesn’t work. Looks like Codechef needs to add the primitive datatype BigInt to its IDE. BigInt - JavaScript | MDN

1 Like

on submitting my code it is not running for the last case , i am not able to figure out what problem is there , which case is not considered , can anyone please help

#include<bits/stdc++.h>
#include<math.h>
using namespace std;
void solve()
{
int k=0,x,m;
cin>>x>>m;
if(x>pow(2,(m-1)))
{
cout<<0<<"\n";
return;
}
int num=x;
while(x>=2)
{
k++;
x=x/2;
}

if(num>int(pow(2,k)))
{
cout<<(m-k-1)<<"\n";
}
else{
    
 cout<<m-k<<"\n";
}
return;

}

int main()

{

int t;
cin>>t;
while(t–)
{
solve();
}
}

Intuitive Solution:

from math import log2
def solve():
    H, M = map(int, input().split())
    ops = int(log2(H))
    if pow(2, ops) < H: # counting ops can be done through looping too (powers of 2 <= H)
        ops += 1
    ops += 1
    if ops > M:
        print(0)
        return
    print(M - ops + 1)

t = int(input())
for _ in range(t):
    solve()

I’m not sure I would count that as intuitive as such… a more construction-driven solution might be:

def solve():
    X, M = map(int, input().split())
    blocks = 1
    while blocks < X and M > 0:
        M -= 1        # Use a step...
        blocks *= 2   # to double blocks by building up the first tower
    return M          # build a full tower on all remaining steps

t = int(input())
for _ in range(t):
    print( solve() )