how to optimze this code ?

[sc7]

Prob:
Shreya is currently the top rated programmer of the college. She loves to solve problems which are based on range query.
But this time she wants to check the problem solving skills of her friend Komal. Thus she gives her the following equation :
X + Y = 10^9
She also gives her an array(A) of N distinct integers denoting the X coordinate in the above equation. Now she asks Q queries. In each query she gives a range[L,R] and an integer K and asks to find the X coordinate in the range[L,R] such that the corresponding Y coordinate is closest to K. If there exists more than one such X coordinate then print the smallest among them.
Since Komal is busy in organsing the contest, she asks you for help. Can you solve this problem for her?
NOTE : All indexing are 1 based.

INPUT :
First line contains two space seperated integers N [size of the array(A)] and Q (number of queries to ask).
Second line contains N space separated integers of array(A).
Next Q lines contain three space sepereted integers L , R and K.
OUTPUT :
For each Q, print a single integer in new line denoting the answer to the query.

CONSTRAINTS :
1<=N<=10^5
1<=A[i]<=10^9
1<=Q<=10^4
1<=L<=R<=N
1<=K<=10^9

Example
Input :
7 4
3 2 4 1 5 12 6
2 6 10
1 4 3
2 5 3
5 6 2
Output :
12
4
5
12
Explanation :
Testcase 1 :
For first query in range[2,6] the X coordinate having corresponding Y coordinate closest to K(10) is 12.

problem semed pretty straightforward, but its giving TLE, can anybody help me with some hint to optimize this ?

int n,q;cin>>n>>q;
	int arr[n];
	for(int i=0;i<n;i++)
	{
		cin>>arr[i];
	}

	while(q--)
	{
		int l,r,k;cin>>l>>r>>k;

		int temp[r-l+1];

		for(int i=l-1,j=0;i<=r;i++,j++)
			{temp[j]=arr[i];}

		sort(temp,temp+r-l+1);
			int val1=*lower_bound(temp,temp+r-l,1e9-k);
			int val2=*upper_bound(temp,temp+r-l,1e9-k);

			//cout<<val1<<" "<<val2<<"\n";
			if(abs(1e9-k-val1) <= abs(1e9-k-val2))
				cout<<val1<<"\n";
			else
				cout<<val2<<"\n";
	}

I was thinking of using Mo's algo, is that needed here ?

[Thomas1965]

Normally before trying to optimize code you need to do some profiling to find out where the bottleneck is.
What is the time limit?
What's ti current running time?

[sc7]

@Thomas time limit is 1s, my time complexity is O(n + q*(r-l+1)*log(r-l+1)) , I think, bottleneck is making temp array for each l and r q times ? ..because if q is 10^4 and r-l+1 could be 10^5 then we will need to do 10^9 operations which could lead to TLE maybe ??

[jonnin]

what happens if you write your own version of code that combines lower_bound and upper_bound and returns the answer. It looks to me that its cheaper to do an O(N) iteration over all the items than to do an N*lg(N) sort and then add on that a pair of lg(n) binary search or whatever to it? Can't you just iterate once (and quickly) to get the upper/lower both in one loop? Can you find a way to do that, and avoid the excessive copies, sorting, and double looping to find both upper and lower? val1 and val2 are also totally not necessary, an extra variable creation and copy into for ... what? 1e9-k is a constant, can you factor it out (4 times in the code).

you have an illegal variable length array. Where is the source of these similar chunks of code with the same language violations coming from?

None of this helps if there is a better algorithm.
Echoing Thomas,
step 1) understand the problem
step 2) find the best algorithm for it
step 3) get it working
step 4) simple hand optimize pass
step 5) profile
step 6) deep tweaks

Im jumping in on step 4 here assuming you did 1-3 already.

[Thomas1965]

@jonnin,
I think this is a codechef.com challenge. They use GCC to check the solution and GCC supports VLAs.

[ne555]

> O(n + q*(r-l+1)*log(r-l+1))
O(q n lg n)

> I was thinking of using Mo's algo
https://www.hackerearth.com/practice/notes/mos-algorithm/
sorting fails condition 1
as K changes in each query, it fails condition 3

I'll suggest a segment tree

[jonnin]

true, k is only a constant per iteration, but you can still factor it out.

if you do a tree consider lifting pointers (or just indices) from a vector instead of a hand-rolled tree data structure.

[sc7]

@ ne555 ,

O(q n lg n)

sorry forgot, l and r have same constraints as n :P , can you please elaborate on how to use segment tree here, coz I have never used it before?

[ne555]

first, the construction

for K=1; K<n; K*=2 //1, 2, 4, 8, 16, ..., dyadic ranges
   temp = array
   for L=0; L<n; L+=K
      sort(temp+L, temp+L+K) //sort each segment
   segment_tree.add(temp)

the idea is that you'll have several copies of your original array, each copy is segmented and each segment is sorted.
the size of the segments duplicate each time, need O(n lg n) memory and O (n lg^2 n) time (I think)

for your example input

3 | 2 | 4 | 1 | 5 | 12 | 6
2   3 | 1   4 | 5   12 | 6
1   2   3   4 | 5   6   12
1   2   3   4   5   6   12

(you'll end with a (n x lg n) matrix)

now, the queries.
start at the bottom:
- say that your [l; r] interval coincides with one segment, then you simply do binary search on it. O(lg n)
- if the segment is too big for your interval, then you ascend one step (at most you'll travel lg n levels)
- if you are between two segments, then you split your interval. solve each part and then merge the result
again, not sure about the complexity, but the searchs are lg n and at most you travel lg n levels, so it can't be worse than lg^2 n

for example, the query l=2 r=5 value=3
first segment is [1; 7], go up
here we split the interval, so we have [2; 4] and [5]
- with [5] go up to the last level, and the result is '5'
- with [2; 4] you go up and split again: [2] and [3; 4]
--- [2] ends giving '2'
--- [3; 4] gives '4'
-- between '2' and '4', wins '2'
- betwee '2' and '5', wins '2'

so the "closest" element to '3' in the range [2; 5] was '2'



edit: notice that each segment may be constructed merging the two above it
that's the basis of mergesort, so it can be done in only O(n lg n)

[sc7]

@ne555 So, I learned a little bit about this data structure, just want few things clarified, So basically you want me to create nodes as sorted subarrays of ranges [0...n-1](root node) [0...n/2],[n/2+1....n-1]...and so on decreasing by 2 times till we reach one? What DS will you use to represent this tree, 2d vector?
finding the value seems pretty straight forward. thank you

how about if I make the segment tree with finding the closest to k as nodes ?? and those nodes represent the ranges?
like root be like closest to k from [0..n-1], its sons as closest to k from [0..n/2],[n/2+1....n-1] and so on, and the leaves are closest to k from [0,0],[1,1][2,2][3,3]...[n-1,n-1] ??

If the range is exactlt like we made nodes of return the value, else if range is inbetween two sons, then find from the son where l lies till the maximum of that son's range, and from maximum of that son's range till r for right son, basically merging my answer from two subtrees?
..
Will this work ?

[ne555]

> you want me to create nodes as sorted subarrays of ranges (...) decreasing by
> 2 times till we reach one?
yes, that's it
you may represent it with a 2d vector

> how about if I make the segment tree with finding the closest to k as nodes
not sure if I follow you
`k' may change on each query, you can't affort to construct the tree for each query.

> If the range is exactlt like we made nodes of return the value, else if range
> is inbetween two sons, then find from the son where l lies(...)
that's how you'll perform the query
notice that you won't check all the segments ranges

[sc7]

@ne555 gotcha.

[closed account 3UohqMoL]

Hi anyone got MCQ answer correct please help me if so?

[sc7]

@ne555

about `findClosest()', it should be similar to lower_bound() upper_bound()
not going to bother to debug it.

Yes, What I used was binary search, it has O(Logn) complexity, lower_bound and upper_bound also works on the same principle, I checked, it works fine.

by the way, ¿is it safe to return 0 when the range is outside the segment? ¿is not going to bother your "merge"?

Didn't understood this line tho..am only returning 0 when l is greater than r (range in the query) or when I merge , and I get the range [l;r] before checking whole[l;tm] ??please explain this, am not understanding it properly

[ne555]

op's code

vector<vector<int> > t;

int getClosest(int, int, int);
int findClosest(vector<int> arr,int n,int k);

//Finding the closest in Seg tree Segments
int closest_to_k(int v,int tl,int tr,int l,int r,int val)
{
	if(l>r) return 0;
	else if(l==tl && r==tr) {return findClosest(t[v],r-l+1,val);}

	int tm=(tl+tr)/2;

	int val1=closest_to_k(2*v,tl,tm,l,min(r,tm),val);
	int val2=closest_to_k(2*v+1,tm+1,tr,max(l,tm+1),r,val);

	if(abs(val-val1)<=abs(val-val2)) return val1;
	else return val2;
}

//This is all using binary search
int findClosest(vector<int> arr, int n, int target)
{

    if (target <= arr[0])
        return arr[0];
    if (target >= arr[n - 1])
        return arr[n - 1];
 

    int i = 0, j = n, mid = 0;
    while (i < j) {
        mid = (i + j) / 2;
 
        if (arr[mid] == target)
            return arr[mid];
 

        if (target < arr[mid]) {
 

            if (mid > 0 && target > arr[mid - 1])
                return getClosest(arr[mid - 1],
                                  arr[mid], target);
 
            j = mid;
        }
 
        else {
            if (mid < n - 1 && target < arr[mid + 1])
                return getClosest(arr[mid],
                                  arr[mid + 1], target);
         

            i = mid + 1; 
        }
    }
 

    return arr[mid];
}
 //fetches the binary searched value to get the closest
int getClosest(int val1, int val2,
               int target)
{
    if (target - val1 >= val2 - target)
        return val2;
    else
        return val1;
}


int main() {
	#ifndef ONLINE_JUDGE
		freopen("inp.txt", "r", stdin);
		freopen("output.txt","w", stdout);
	#endif

	int n,q;cin>>n>>q;
	vector<int> arr;
	for(int i=0;i<n;i++)
		{int a;cin>>a;arr.push_back(a);}

	//SegTree consstruction
	for(int i=1;i<n;i*=2)
	{
		vector<int> temp;
		temp=arr;
		for(int j=0;j<n;j+=i)
		{       //i+j would go upto 8 , right ??(out of bounds ??)
			sort(temp.begin()+j,temp.begin()+j+i);

			t.push_back(temp);
		}
	}

	while(q--)
	{
		int l,r,k;cin>>l>>r>>k;
		int val=1e9-k;
		cout<<closest_to_k(1,0,n-1,l-1,r-1,val)<<"\n";//l-1 and r-1 , since it is 1-indexed based
	}
	// cout<<"Execution time : "<<tick()<<"\n";
	return 0;
}

I'm talking about lines 14--18

	int val1=closest_to_k(2*v,tl,tm,l,min(r,tm),val); //suppose this returns 0
	int val2=closest_to_k(2*v+1,tm+1,tr,max(l,tm+1),r,val);

	if(abs(val-val1)<=abs(val-val2)) return val1; //and if 0 is near val, you return 0
	else return val2;

0 is an invalid value that may never be on the array, yet you are giving it out as an answer.

[sc7]

oh , ok yes I get it now, so what if, when l> r I return 10^18 ? I think that has to solve the problem, right ??

I did return 10^18, still getting WA even in sample TC tho, I think there is something else wrong too..

[ne555]

	//SegTree consstruction
	for(int i=1;i<n;i*=2)
	{
		vector<int> temp;
		temp=arr;
		for(int j=0;j<n;j+=i)
		{
			sort(temp.begin()+j,temp.begin()+j+i);

			t.push_back(temp);//this shouldn't be here
		}
	//but here
	}

looking at the segment tree after construction you have

{3, 2, 4, 1, 5, 12, 6}
{3, 2, 4, 1, 5, 12, 6}
{3, 2, 4, 1, 5, 12, 6}
{3, 2, 4, 1, 5, 12, 6}
{3, 2, 4, 1, 5, 12, 6}
{3, 2, 4, 1, 5, 12, 6}
{3, 2, 4, 1, 5, 12, 6}
{2, 3, 4, 1, 5, 12, 6}
{2, 3, 1, 4, 5, 12, 6}
{2, 3, 1, 4, 5, 12, 6}
{2, 3, 1, 4, 5, 12, 0} //`0' appears
{1, 2, 3, 4, 5, 12, 6}
{1, 2, 3, 4, 5, 6, 6} //`12' disappears 

where you should have

{3, 2, 4, 1, 5, 12, 6}
{2, 3, 1, 4, 5, 12, 6}
{1, 2, 3, 4, 5, 6, 12}
{1, 2, 3, 4, 5, 6, 12}

note, only 4 rows, not 13
there are also issues because of out of bounds access on the sort

in `closest_to_k()' you say that the children are 2*v and 2*v+1, that's wrong they are in v-1
the root is on row .size()-1, not on 0
2**row gives you the size of the segment, size*index will give you the starting point

use descriptive names on your variables

[sc7]

Ok, I got the segment tree constructution

//SegTree consstruction
	int cnt=1;
	int val=pow(2,(round)(log(n)/log(2)));
	//cout<<val<<"\n";
	for(int i=1;i<=val;i*=2)
	{

		vector<int> temp;
		temp=arr;

		for(int j=0;j<n;j+=i)
		{	
			if(j+i >= n)
				sort(temp.begin()+j,temp.begin()+n);
			else
				sort(temp.begin()+j,temp.begin()+j+i);

		}

			t[cnt++]=temp;
	}

But I can't seem to understand the closest_to_k() func, what do you mean by

root is on row .size()-1, not on 0

, isn't the root from 1 ? and row.size()-1 ? thats n-1 right ?Size of segment is 2^row, ok,got that, and I din't get size*index as starting point ??

[ne555]

3 | 2 | 4 | 1 | 5 | 12 | 6
2   3 | 1   4 | 5   12 | 6
1   2   3   4 | 5   6   12
1   2   3   4   5   6   12 //this one is root 

by construction the last segment to be added encompass the whole array
and there is where you start the search, that's the root.

> and row.size()-1 ? thats n-1 right ?
yes, the last element
t.back(), t[3] in the example

> I din't get size*index as starting point ??

2   3 | 1   4 | 5   12 | 6

those are 4 segments of size 2 (the last one is missing an element)
they are all inside one array, in the example t[1]
the first segment (index 0) starts at 0
the second segment (index 1) starts at 2
the third segment (index 2) starts at 4
the fourth segment (index 3) starts at 6

def closest_to_k(segment_tree, value, range, row, index):
   size = 2**row
   segment_range = (size*index, size*(index+1)-1)
   if range == segment_range:
      return find_closest(segment_tree[row][segment_range], value)
   if outside(range, segment_range):
      return infinite

   midpoint = (segment_range.start + segment_range.end)/2
   
   left = closest_to_k(segment_tree, value, (range.start, midpoint), row-1, 2*index)
   right = closest_to_k(segment_tree, value, (midpoint+1, range.end), row-1, 2*index+1)
   return nearest({left, right}, value)

[Thomas1965]

There is a much simpler solution than the ones proposed here.
I don't want to spoil the fun but solutions were published...
https://www.codechef.com/problems/T26 just click ob successful submissions.