FODCHAIN - Editorial

editorial
, , ,
1

PROBLEM LINK:

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

Author: Daanish Mahajan
Tester: Manan Grover
Editorialist: Vichitr Gandas

DIFFICULTY:

CAKEWALK

PREREQUISITES:

NONE

PROBLEM:

Given the initial energy E and it reduces by a factor of K when going to next level. Find the length of food chain where each level has non-zero energy.

EXPLANATION

It is given that K >= 2 hence we can just loop on E and every time do E = E/K until E becomes 0. The number of loop iterations is the maximum number of levels.

Notice that answer is just \log_{K}{E} as everytime E is reduced by a factor of K.

TIME COMPLEXITY:

O(\log_{K}{E}) per test case

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>
# define pb push_back 
#define pii pair<int, int>
#define mp make_pair
# define ll long long int

using namespace std;

const string newln = "\n", space = " ";
const int maxt = 1e5, maxe = 1e9, maxb = 1e9;
int main()
{   
    int t, e, b; 
    cin >> t;
    while(t--){
        cin >> e >> b;
        int ans = 1;
        while(e / b > 0){
            e /= b; ans++;
        }
        cout << ans << endl;
    }
}
Tester's Solution 
#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, k;
    cin>>n>>k;
    int ans = 0;
    while(n != 0){
      ans++;
      n /= k;
    }
    cout<<ans<<"\n";
  }
  return 0;
}
Editorialist's Solution 
/*
 * @author: vichitr
 * @date: 24th July 2021
 */

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fast ios::sync_with_stdio(0); cin.tie(0);

void solve() {
	int E, K; cin >> E >> K;
	int ans = 0;
	while (E > 0) {
		E = E / K;
		ans++;
	}
	cout << ans << '\n';
}

signed main() {
	fast;

#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif

	int t = 1;
	cin >> t;
	for (int tt = 1; tt <= t; tt++) {
		// cout << "Case #" << tt << ": ";
		solve();
	}
	return 0;
}

VIDEO EDITORIAL:

If you have other approaches or solutions, let’s discuss in comments.If you have other approaches or solutions, let’s discuss in comments.

2

An efficient solution
https://www.codechef.com/viewsolution/49061461

3

This is same as my solution or possibly every other solution. The inbuilt function \log also take same time as mentioned in the editorial.

4 
#include <bits/stdc++.h>
using namespace std;
int main()
{
#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

    freopen("output.txt", "w", stdout);

#endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long test_case;
    cin >> test_case;
    while (test_case--)
    {
        long long a, b;
        cin >> a >> b;
        if (a==0)
        cout << 0;
        else
        cout << 1 + (floor)((log(a) / log(b)));
        cout << "\n";
    }
    return 0;
}

please help me, what’s wrong with this solution?

5

This will lead to precision loss. You should follow the approach provided in the editorial for correct output.

EDIT: I may be wrong. Just tested your code against mine. I couldn’t find any test case where your code fails.

6

Kudos to the Author for generating strong test cases :clap:.

7

But what’s the problem with this approach mentioned by hemangkinra?