BIN_BAT - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: Gaurav Somai
Testers: Hriday, Utkarsh Gupta
Editorialist: Nishank Suresh

DIFFICULTY:

786

PREREQUISITES:

None

PROBLEM:

N players play in a single-elimination tournament. Each round takes A minutes, and there is a B-minute break after every round except the last.
How much time does the tournament take?

EXPLANATION:

We are given that N is a power of 2, so let N = 2^k.
Note that the tournament has exactly k rounds.

For these k rounds:

  • Each one takes A minutes
  • All but the last have a further break of B minutes

This gives us a total time of

k\cdot A + (k-1)\cdot B

The only thing that remains is to correctly compute k.
This can be done in many ways:

  • You can iterate k on a loop and check if 2^k = N
  • Alternately, most languages have builtin functions to compute this, for example:
    • __lg(N) or log2(N) in C++
    • N.bit_length()-1 in Python

Once k is computed, use the formula above.

TIME COMPLEXITY

\mathcal{O}(1) per test case.

CODE:

Setter's code (C++) 
#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 n,a,b;
    cin>>n>>a>>b;
    int k = log2(n);
    int ans = (a*k)+(b*(k-1));
    cout<<ans<<"\n";
   }

   return 0;
}
Editorialist's code (Python) 
for _ in range(int(input())):
    n, a, b = map(int, input().split())
    rounds = n.bit_length() - 1
    print((rounds-1)*(a+b) + a)
1 Like