I was trying to solve SLAEL using Segment Tree. I built the segment tree in which every node contains largest and second largest element in the segment. But I was not able to figure out how to query this segment tree for a particular k.
Is it not possible to apply segment tree here
Initial solution of setter was binary search +Segment tree. But we noticed a simple solution based of difference of indices where A_i>k
Can you please help me with Segment tree approach. And please tell me whether my approach is correct or wrong.
I solved using Segment Tree but got an WA .
Code Seems to work right .
Anybody can help me with the mistakes ?
#include <iostream>
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<ll,ll>
#define vi vector<ll>
#define all(a) (a).begin(),(a).end()
#define endl '\n'
#define rep(i,a,b) for(long long i=a;i<b;i++)
#define repr(i,a,b) for(long long i=a;i>=b;i--)
using namespace std;
long long getMid(long long s, long long e)
{
return s + (e - s) / 2;
}
/* A recursive function to get the sum of
values in given range of the array.
The following are parameters for this
function.
st -> Polong longer to segment tree
node -> Index of current node in
the segment tree .
ss & se -> Starting and ending indexes
of the segment represented
by current node, i.e., st[node]
l & r -> Starting and ending indexes
of range query */
long long MaxUtil(long long* st, long long ss, long long se, long long l,
long long r, long long node)
{
// If segment of this node is completely
// part of given range, then return
// the max of segment
if (l <= ss && r >= se)
return st[node];
// If segment of this node does not
// belong to given range
if (se < l || ss > r)
return -1;
// If segment of this node is partially
// the part of given range
long long mid = getMid(ss, se);
return max(MaxUtil(st, ss, mid, l, r,
2 * node + 1),
MaxUtil(st, mid + 1, se, l,
r, 2 * node + 2));
}
long long getMax(long long* st, long long n, long long l, long long r)
{
// Check for erroneous input values
if (l < 0 || r > n - 1 || l > r)
{
printf("Invalid Input");
return -1;
}
return MaxUtil(st, 0, n - 1, l, r, 0);
}
// A recursive function that constructs Segment
// Tree for array[ss..se]. si is index of
// current node in segment tree st
void updateValue(long long arr[], long long* st, long long ss, long long se,
long long index, long long value, long long node)
{
if (index < ss || index > se)
{
cout << "Invalid Input" << endl;
return;
}
if (ss == se)
{
// update value in array and in segment tree
arr[index] = value;
st[node] = value;
}
else {
long long mid = getMid(ss, se);
if (index >= ss && index <= mid)
updateValue(arr, st, ss, mid, index,
value, 2 * node + 1);
else
updateValue(arr, st, mid + 1, se,
index, value, 2 * node + 2);
st[node] = max(st[2 * node + 1],
st[2 * node + 2]);
}
return;
}
long long constructSTUtil(long long arr[], long long ss, long long se,
long long* st, long long si)
{
// If there is one element in array, store
// it in current node of segment tree and return
if (ss == se)
{
st[si] = arr[ss];
return arr[ss];
}
// If there are more than one elements, then
// recur for left and right subtrees and
// store the max of values in this node
long long mid = getMid(ss, se);
st[si] = max(constructSTUtil(arr, ss, mid, st,
si * 2 + 1),
constructSTUtil(arr, mid + 1, se,
st, si * 2 + 2));
return st[si];
}
/* Function to construct segment tree from given array.
This function allocates memory for segment tree.*/
long long* constructST(long long arr[], long long n)
{
// Height of segment tree
long long x = (long long)(ceil(log2(n)));
// Maximum size of segment tree
long long max_size = 2 * (long long)pow(2, x) - 1;
// Allocate memory
long long* st = new long long[max_size];
// Fill the allocated memory st
constructSTUtil(arr, 0, n - 1, st, 0);
// Return the constructed segment tree
return st;
}
int main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
long long tc;
cin>>tc;
while(tc--)
{
long long n,k;
cin>>n>>k;
long long arr[n];
long long arrc[n];
for(long long i=0;i<n;i++)
{
cin>>arr[i];
arrc[i]=arr[i];
}
long long* st = constructST(arr, n);
long long max_size=0;
for(long long a=0;a<n;a++)
{
//arr=arrc;
copy(arrc, arrc + n, arr);
long long* st = constructST(arr, n);
for(long long b=a;b<n;b++)
{
copy(arrc, arrc + n, arr);
long long* st = constructST(arr, n);
long long val =getMax(st, n, a, b) ;
if(val>k)
{
for(long long i=a;i<=b;i++)
{
if(arr[i]==val)
{
updateValue(arr, st, 0, n - 1, i, -1, 0);
}
}
long long val1 =getMax(st, n, a, b) ;
if(val1<=k && val1!=-1)
{
// cout<<"yeyeye"<<endl;
// cout<<a+1<<" "<<b+1<<endl;
// cout<<val<<" "<<val1<<endl;
max_size=max(max_size,(b-a+1));
// cout<<max_size<<endl;
}
}
}
}
cout<<max_size<<endl;
}
}Your code fails at:
1
3 3
78 11 80
Ans: 1
Your output: 0
(All credits to ‘Bug Finder’ available at https://github.com/sarthakmanna/Bug-Finder for free). XD XD
I solved it using Binary Search + Segment tree ,link text
But it is giving me tle ,may be because in the worst case the time complexity would be N*log(N)*log(N).Can some one look into my code and give some tips to reduce the time complexity.Any help is highly appreciated.Thanks in advance.
#HERE is a neat segment tree + binary search approach
#which is O(n*log^2(n)) and it is giving TLE.
What i did is finding all the contiguous sub sequences and then comparing its largest and second largest element with k.
But unfortunately its giving TLE.
Can Someone help me with some other way
My Solution : https://www.codechef.com/viewsolution/21221508
For those who are unable to access:
num1=int(input())
for _ in range(num1):
num2=map(int,raw_input().strip().split())
num3=map(int,raw_input().strip().split())
m=[num3[i:i+j] for i in range(0,num2[0]) for j in range(1,num2[0]-i+1)]
m=sorted(m, key=len)[::-1]
for k in m:
p=sorted(list(set(k)))
if len(p)>1:
if num2[1]<p[-1] and num2[1]>=p[-2]:
print len(k)
break
elif len(p)==1:
if num2[1]<p[-1]:
print 1
break
</pre>
you just need to mark index whose value>k and then a simple logical approach will give you O(n) solution. You can have a look at my optimized soln which is O(n).
I have implemented both of them XD
you just need to mark index whose value>k and then a simple logical approach will give you O(n) solution. You can have a look at my optimized soln which is O(n).
you just need all triplets of marked indices such that their(all three marked index’s ) value is >k and no element except these three is >k in range [1st index , 3rd index]
and you find a segment which is excluding 1st and 3rd index.
check all such segments and output maximum size segment.
So basically solutions including Binary search and Segment tree were not intended.
In the worst case there would be about 400 * 1000000=4*10^8 operations.Shouldn’t it pass in 2 sec time limit?
Hey i have also done this question using Segment Tree + Binary Search and i know that it is an overkill but still i am getting wrong answer and not TLE . So if can anyone plzz provide me any case where it may be failing .
Solution link : https://ideone.com/fFD7cM
Plzz help!!
I thought the same thing and wrote the code but as you can see merging two nodes of segment tree is O(1) but then too it’s a complex logic so I think it will multiply it by maybe by 2 so it would be 8*10^8 iterations so it won’t pass…
In short basic problem is constant associated with Big-O notation.
welcome 
If I recall, initially the constraints were lower when segment tree+Binary search solution was proposed. I think they were raised so that SegTree+Binary search gets TLE.