Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
1.
Problem
2.
Solution
3.
FAQs
4.
Key Takeaways
Last Updated: Mar 27, 2024

# Matchstick Problem

GAZAL ARORA
1 upvote

## Problem

Given N matchsticks numbered from 0 to N-1. bi seconds is taken by ith 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 bi 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 â‰¤ 105
• 1â‰¤ bi â‰¤ 108
• 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 t1 be the minimum time some matchstick takes in the range L to R to burn out completely.
• Let t2 be the maximum time some matchstick takes in the range L to R to burn out completely.
• Let t3 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 t1 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 (t2 - t1) / 2 seconds to burn out completely.
• The matchsticks outside the L-R range take a maximum of tseconds to burn out completely.

Therefore, the time taken by all the matchsticks to burn out is t1 + max( (t1t1) / 2, t3 ).

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

## FAQs

1. What are segment trees used for?
Segment Trees is a data structure that can solve Range Min or Max, Sum Queries, and range update queries in O (log N) time complexity. The array is stored at the tree's leaves, while the inner nodes contain information about the segments represented by its children.

## Key Takeaways

In this article, we designed an algorithm to solve the queries about the time taken in burning all the matchsticks. We used the segment trees data structure to solve the problem. The time complexity and space complexity of the algorithm is O(NlogN).

Recommended Problems: