Matchstick Problem

Problem

Given N matchsticks numbered from 0 to N-1. b_i seconds is taken by i^th matchstick to burn when lighted from one end. All the matchsticks burn at a uniform rate. When both ends of a matchstick are lit simultaneously, the matchstick will burn down in halftime only. All the matchsticks are arranged in the following manner:

One end of all the matchsticks is tied together at one point, and the other is kept free. The matchsticks are arranged in increasing order of their numbers. Except for the one end, no part of matchsticks touches each other. An example of 5 matchsticks is shown below.

-Source

There are Q queries, each of which asks: If we light the free end of all matchsticks numbered between L and R inclusively, how long will it take for all matchsticks to be completely burnt?

Input: 

• The first line contains a single integer N.
• The following line contains n space-separated b_i values of the corresponding matchstick.
• The next line contains an integer Q.
• Next Q lines contain pairs of integers L and R representing the queries.
   

Output: Print the answer to each query in a separated line.

Constraints:

• 1≤ N, Q ≤ 10⁵
• 1≤ bi ≤ 10⁸
• 0≤ L ≤ R ≤ N−1

For example

1.
Input: 
1
3
1
0 0
Output: 3
Explanation: As there is only 1 matchstick. It will take 3 seconds to burn.
 
2.
Input: 
2
3 5
1
0 1
Output: 4
Explanation: The two matchsticks are lit together as given in the question. Matchstick number 0 will take 3 seconds to burn down completely, and Matchstick number 1 will take 5 seconds.
After 3 seconds, matchstick 0 is burnt completely, and it lit the other end of matchstick 1. Both ends of the matchstick 1 are lit after 3 seconds, and 2 seconds are left to burn out completely. It will start burning at twice the original rate. Therefore instead of 2 seconds, it will burn completely in 1 second only. Total time = 3 + 1 = 4 seconds.

Recommended: Try to solve it yourself before moving on to the solution.

Solution

Points to consider:

• The front ends of all the matchsticks in the range L- R are lit.
• The matchstick that burns the quickest from L to R burns out and ignites all the other matchsticks on their back ends.
• Matchsticks in the L-R range now burn out twice as rapidly.
• All of the other matchsticks burn out at the same rate.
   

For each query, in range, L - R, find

• The fastest of all the burning rates for all matchsticks in the L to R.
• The slowest of all the burning rates for all matchsticks in the L to R.
• The slowest of the burning rates of matchsticks outside the range L to R.
   

Using the above findings to calculate the time taken by all the matchsticks to burn out:

For a given range L to R

• Let t₁ be the minimum time some matchstick takes in the range L to R to burn out completely.
• Let t₂ be the maximum time some matchstick takes in the range L to R to burn out completely.
• Let t₃ be the maximum time some matchstick takes outside the range L to R to burn out completely.
   

Each stage in the scenario described above takes the following amount of time:

• The fastest burning matchstick in the L to R range takes t₁ seconds to burn out completely.
• The following things are happening in parallel:
  • Matchsticks in the L-R range now burn out twice as quickly takes a maximum time of (t₂ - t₁) / 2 seconds to burn out completely.
  • The matchsticks outside the L-R range take a maximum of t₃ seconds to burn out completely.

Therefore, the time taken by all the matchsticks to burn out is t₁ + max( (t₁- t₁) / 2, t₃ ).

C++

#include <bits/stdc++.h>
#define ll long long 

using namespace std;
vector <vector <double> > mini, maxi;

// function to get the minimum burning time.
double query_min(ll l, ll r, ll n)
{
    if (r < 0 || l >= n) return -1;
    if (l == r) return mini[0][l];
    ll k = log2(r - l);
    return min(mini[k][l], mini[k][r + 1 - pow(2,k)]);

}

// function to get the maximum burning time.
double query_max(ll l, ll r, ll n)
{
    if (r < 0 || l >= n) return -1;
    if (l == r) return maxi[0][l];
    ll k = log2(r - l);
    return max(maxi[k][l], maxi[k][r + 1 - pow(2,k)]);
}

// main function.
int main()
{
    ll n, m;
    cin >> n;
    ll k = log2(n) + 1;

    mini.resize(k, vector <double>(n, 0));
    maxi.resize(k, vector <double>(n, 0));
    
    for (ll i = 0; i < n; ++i)
    {
        cin >> mini[0][i];
        maxi[0][i] = mini[0][i];
    }

    for (ll i = 1; i <= k; ++i)
    {
        for (ll j = 0; j <= n - pow(2,i); ++j)
        {
            mini[i][j] = min(mini[i - 1][j], mini[i - 1][j + pow(2, i - 1)]);
            maxi[i][j] = max(maxi[i - 1][j], maxi[i - 1][j + pow(2,i - 1)]);
        }
    }

    ll l, r, q;
    cin >> q;
    
    for (ll i = 1; i <= q; ++i)
    {
        cin >> l >> r;
        double a, b, c, out, in;
        a = query_max(0, l - 1, n);
        b = query_min(l, r, n);
        c = query_max(r + 1, n - 1, n);

        out = max(a, c) + b;
        
        // The relation we derived earlier.
        in = (double) ((query_max(l, r, n) - b) / 2) + b;
        cout << fixed << setprecision(1) << max(out, in) << "\n";
    }
    return 0;
}

Input

2
3 5
1
0 1

Output

4

Time Complexity: O(N*logN). As time complexity of function query_max and query_min is O(1) and time to find mini[i][j] and max[i][j] = N*k where N is the number of matchsticks and k = O(logN). So total time complexity becomes O(N*k) or O(N*logN).

Space Complexity: O(N*logN). As we can see, mini and maxi vectors are of size N*k, where N is the number of matchsticks and k = O(logN).

Also read, Euclid GCD Algorithm