Help Needed to solve a Problem

help
1

Here’s the Problem Statement.

Consider a line segment of length L. Its left end is the Origin and the right end is (L,0). You are supposed to answer Q Queries. In i^{th} query, a vertical line is drawn at (x_i, 0), cutting the line segment at (x_i, 0). Find the length of the largest segment after the query.

Example Input
L = 100
Q = 3
x_i = [30, 20, 60]

Example Output
[70, 70, 40]

Explanation
For the first query, we divide the line at (30, 0). Now the line segment is divided into 2 segments, (0, 30) and (30, 100). The length of the largest segment is 70.

For the second query, we divide the line at (20, 0). Now the line segment is divided into 3 segments, (0, 20), (20, 30) and (30, 100). The length of the largest segment is still 70.

For the third query, we divide the line at (60, 0). Now the line segment is divided into 4 segments, (0, 20), (20, 30), (30, 60) and (60, 100). The length of the largest segment is 40.

Any help is greatly appreciated.

PS: A variant of this problem is asked in Hackerrank Certification test long back. So, it is impossible to provide the link of the actual problem.

2

I think blindly simulating what the question says should work.

SAMPLE INPUT 
100
3 
30 20 60
CODE 
#include "bits/stdc++.h"
using namespace std ;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); 		
	int l,q ;
	cin >> l >> q  ;
	multiset<int>b={l},a={0,l};
	while(q--){
		int x  ;
		cin >> x  ;
		int L = (*--a.lower_bound(x)) ;
		int R = (*a.lower_bound(x)) ;
		int D = R-L ;
		b.erase(b.find(D)) ; a.insert(x) ;
		b.insert(x-L),b.insert(R-x) ;
		cout << (*--b.end()) << '\n' ; 
	}
}

NOTE: I’ve assumed that same x_i won’t be repeated in the queries, if it is the case then we can just ignore such queries as they won’t make any difference.

1 Like
3

So, you are using multiset and its methods (erase, find and insert). What is the time complexity of the solution?
Because, the desired time complexity is O(Q\log{Q}).

1 Like
4

Yeah all these operations work in \mathcal{O(logN)}. Hence overall complexity would just be \mathcal{O(QlogQ)}

1 Like
5

Thank you once again. But what is the data structure called?
I want to know because, if at all I want to implement the same in another language or share the approach to anyone, it may help.

6

You can use Sorted List in replacement of multi-set if you’re using python. Not sure about the time complexity of operations though but should be less than O(n).
There is some discussion about complexity of operations in this blog. Also, there are other ideas.

3 Likes
7

Thank you very much.

1 Like
8

You can implement multisets using any sort of a threaded balanced tree, AVL Tree, B Tree, B+ tree etc.

3 Likes
9

Yeah, I thought of exactly the same data structure. AVL tree, or OBST something like that. Was just curious about easier solution. Thank you!

1 Like
10

https://cses.fi/problemset/task/1163/
Same problem

2 Likes
11

The following is my map-based C++ solution of the similar CSES Traffic Lights problem.

https://ideone.com/6TBrAE

12

I already solved it. I posted the link so that others can submit.

1 Like
13

I think we can do it by using two data structures
one set another map
for every xi just find its upper and lower bound in set
and map the values of xi-lower_boune of xi and upper_bound of xi - xi
and just print the last element of the map for every input

1 Like