Telecom Towers in a city

Opimized approach

Covering all cities can be expressed as splitting 'N'  into the sum of several positive odd integers. To calculate this you should have a basic knowledge of dynamic programming with prefix sums, but we can also prove that the number of ways to split 'N'  is exactly the N-th integer in the Fibonacci sequence as follows (this proof uses mathematical induction):

• for 'N'  ≤ 2, it's quite obvious;
• for 'N'  > 2 and N mod 2 = 0, let's iterate on the length of the last segment. We have to sum F1 + F3 +⋯+ FN − 1; F1 + F3 = 1 + 2 = F4; F4 + F5 = F6; F6 + F7 = F8, and so on, until we get FN − 2 + FN − 1 = FN;
• for N > 2 and N mod 2 = 1, let's iterate on the length of the last segment, and add 1 to the result since we can cover everything with a single segment. So, this is 1 + F2 + F4 + F6 +⋯+ FN − 11 + F2 + F4 + F6 +⋯+ FN−1. 1 + F2 = F3 ,F3 + F4 = F5, and so on.

So, the answer to the problem is FN/(2^N)

Now the final thing we need to consider is that we have to print a fraction modulo 998244353998244353. Since 998244353998244353 is a prime, using Fermat little theorem, we can calculate y^−1 as y^998244351mod998244353. Exponentiation must be done with some fast algorithm (for example, binary exponentiation).

Note: it's common in problems requiring to calculate something modulo some prime number to have problems with overflow in intermediate calculations or some other issues when we forget to take the result of some expression modulo 998244353998244353. I recommend using either special addition/multiplication/exponentiation functions that always take the result modulo 998244353998244353 (an example of how to write and use them can be viewed in the model solution), or a special modular integer data structure with overloaded operators that you have to implement by yourself. Below is the implementation for the given approach explained for the problem of Telecom Towers in a city.

Algorithm for optimized approach

• Make a vector that will store the prefix results of size N + 1 named as 'fib'
• Pre Initialise the value of fib[0] with 0 and fib[1] with 1 respectively.
• Iterate from i = 1 to i = N in vector and fill the values using the precomputed values and dynamic programming approach.
• While pre-computing the value in the vector, take care of modulo operation for that use modulo addition techniques.
• Use  Fermat little theorem to calculate now for the final formula obtained explained in the approach above to take care of modulo operations.

Code:

// Implementation of Telecom Towers in a city
#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;

// Function for adding while taking care of modulo
int add(int x, int y)
{
    x += y;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}

int mul(int x, int y)
{
    return (x * 1ll * y) % MOD;
}

int binpow(int x, int y)
{
    int ans = 1;
    while(y > 0)
    {
        if(y % 2 == 1)
            ans = mul(ans, x);
        x = mul(x, x);
        y /= 2;
    }
    return ans;
}

// calculation for Telecom Towers in a city
int divide(int x, int y)
{
    return mul(x, binpow(y, MOD - 2));
}

// Drive code for Telecom Towers in a city
int main()
{

    // Taking Input from user
    int n;
    cin >> n;

    // Pre computation array to store the result obtained from dynamic programming
    vector<int> fib(n + 1);

    // Pre initialization
    fib[0] = 0;
    fib[1] = 1;

    // Filling the prefix array 
    for(int i = 2; i <= n; i++)
        fib[i] = add(fib[i - 1], fib[i - 2]);

    // final answer obtained from the formula explained in approach
    cout << divide(fib[n], binpow(2, n)) << endl;    
}

You can also try this code with Online C++ Compiler

Run Code

Output:

842268673

You can also try this code with Online C++ Compiler

Run Code

Time Complexity 

O(N)

The time complexity to solve this problem Telecom Towers in a city is O(N), where 'N' is the total input given by the user. Since we are linearly iterating on the fin vector to precompute the values, that will cost linear time. Further, while calculating the final answer, we have used the formula Fn/(2^N), which can be done in o(1), but in order to handle the modulo operation, we used Fermat little theorem, which does the work for us in logarithmic time. So the total time complexity for the entire implementation will be linear.

Space Complexity 

O(N)

The space complexity to solve this problem of Telecom Towers in a city is O(N). Where 'N' is the total input given by the user, since we have used an extra data structure vector to store the precomputed values, it will cost us linear space.

FAQs

1. What is Modular Multiplicative Inverse?

Ans: The modular multiplicative inverse of a (mod b) is the number x, where ax ≡ 1 mod(p). The modular inverse only exists if a and m are co-prime, i.e., they don't have any common factor other than 1. x is an integer that must also lie in the range [1, p-1] (1 and p-1 inclusive).

2. I have observed values such as 1000000007 and 998244353 being used in problems commonly, why?

Ans: Large prime numbers make up these values. Their popularity comes from the fact that performing any of the basic modular arithmetic operations with them does not cause overflow in a 64-bit integer, and the fact that they are large primes ensures that the modular multiplicative inverse and other quantities can be found without restriction in most problems. By making them huge, you can get a wide range of output.

Key Takeaways

In this article, we have extensively discussed the solution of the problem "Telecom Towers in a city," in which we were required to set the signal for the telecom towers such that it meets some given constraints in the problem statement. Along with the detailed solution, the article discussed the time and space complexity of the solution.

Until then, All the best for your future endeavors, and Keep Coding. "We hope that this blog has helped you enhance your knowledge regarding this problem, and if you would like to learn more, check out our articles on  Coding Ninjas Studio. Do upvote our blog to help other ninjas grow. Happy Coding!”