PROBLEM LINK:
Author: ravikiran0606
Editorialist: ravikiran0606
DIFFICULTY:
MEDIUM
PREREQUISITES:
DP,MATH,BINARY SEARCH
PROBLEM:
In this problem, we have N + 1 bus stops in a straight line. All of them are numbered with integers from 0 to N in the order in which they follow from RK’s college. There are M buses running between the college and the beach: the i-th bus goes from stop si to ti (si < ti), visiting all the intermediate stops in the order in which they follow on the segment. RK can get on the i-th bus on any stop numbered from si to ti - 1 inclusive, but he can get off the i-th bus only on the bus stop ti. We need to find the number of ways RK can go from college to beach.
EXPLANATION:
In this question, for every stop from 0 to N lets calculate kx - number of ways come to them. Consider the i-th bus, number of ways come to stop ti supplied i-th bus is equal to number of ways to embus to i-th bus. One can embus to i-th bus on the stops si, si + 1, …, ti - 1. Thus number of ways come to stop ti in the i bus is equal to sum ksi + ksi + 1 + … + kti - 1. Finally, lets note that overall number of ways to come to stop ti is the sum of numbers of ways to come to stop ti on every bus.
It’s remained two problems.
First problem: 0 ≤ n ≤ 109. Therefore all kx not climb in memory limit. But we need to know only non-zero kx. For instance, one can gripe coordinates: create list of all occured stops (and also stops 0 and n), sort this list, delete the repeated stops and replace all numbers of stops they indexes in this list. After this operations all number of stops not exceed 200001, and all kx are climb to the memory.
Second problem: If we will use loop “for” for counting sum ksi + ksi + 1 + … + kti - 1, asymptotic of time of working will be O(m^2). There is an easy way to solve this problem: one can create and update array sum[], such that sum[i] = k[0] + k[1] + … + k[i - 1], by another words, sum[0] = 0, sum[i + 1] = sum[i] + k[i].
Then number of ways to come to stop ti using bus i is equal to sum[ti] - sum[s<sub>i</sub>].
So time complexity is O(m logm) , memory complexity is O(m).
AUTHOR’S SOLUTION:
Author’s solution can be found here