Great solution by setter in O(N), an O(N log N) solution to the (almost) exact problem is unfortunately also available on GFG https://www.geeksforgeeks.org/find-all-unique-pairs-of-maximum-and-second-maximum-elements-over-all-sub-arrays-in-onlogn/
8 Likes
Now I understand how these many AC solutions for the problem in Div2.
11 Likes
ohhh this was the solution , i was thinking it seems a little bit standard 
lol
2 Likes
Well if you look closely both the solution are almost same , the authors one and the GFG one , there also the Complexity is O(NlogN) only because of using set , using unordered set can get it down to O(N)
1 Like
I solved it using a constructive algo in O(NLOGN). Sort in descending the values along with their indexes and iterate this array to find the left and right greater elements incrementally. Here is my solution - CodeChef: Practical coding for everyone
I was astonished to see everyone using stack all other solutions!
6 Likes
#include <iostream>
#include <vector>
#include<stack>
#include<set>
#include<cmath>
using namespace std;
int main()
{int t;
cin>>t;
while(t--){
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{cin>>a[i];}
stack<int>s;set<int>u;
for(int i=0;i<n;i++){
if(s.size()==0){
s.push(a[i]);
}
else if(s.size()==1){
u.insert(abs(s.top()-a[i]));
s.push(a[i]);
}
else if(s.top()>=a[i])
{
u.insert(abs(s.top()-a[i]));
s.push(a[i]);
}
else{
while( s.size()>0 && s.top()<a[i]){
u.insert(abs(s.top()-a[i]));
s.pop();
}
if(s.size()>0)
u.insert(abs(s.top()-a[i]));
s.push(a[i]);
}}
cout<<(int)u.size()<<endl;}}
Can someone please help me figure out the flaw in this implementation? If possible, please provide a test case that would fail on this.
Will you please explain how you reached upto this conclusion …
Thanks in advance
1 Like
next level
I did exactly same.
@aniket_0206 The concept is basically the same (fixing the second max). You can sort descending order the values and iteratively fix the second max element. Meanwhile, you have an indices array of elements greater than the current element (because you are iterating descending thats possible, initially that array is empty). You can do a binary search and find the indices greater and smaller than the element in iteration and that would produce new diffs needed. Update the current element’s index in the indices array (in sorted order) and proceed for the next iteration.
explain with eg?
Tester is writing the shittiest code possible.
3 Likes
This is not a easy-medium level problem. It is at least medium level problem as we first have to observe that every element can be second maximum at most 2 times and then know the trick to find the two maximum elements of each element in O(N) time.
1 Like
#include<bits/stdc++.h>
#define line cout<<endl;
#define space cout<<" ";
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define PI 3.141592653589793238
typedef long long int ll;
using namespace std;
const ll N = 1e9+7;
ll nextgreater[100000+5];
ll previousgreater[100000+5];
void solve()
{
memset(nextgreater,-1,sizeof(nextgreater));
memset(previousgreater,-1,sizeof(previousgreater));
ll n;
cin>>n;
vector<ll> v(n);
for(int i=0;i<n;i++){
cin>>v[i];
}
stack<ll> selement;
stack<ll> sindex;
for(int i=0;i<n;i++){
if(selement.empty()){
selement.push(v[i]);
sindex.push(i);
}
else{
if(v[i] > selement.top()){
while(!selement.empty() && v[i] >= selement.top()){
ll index = sindex.top();
nextgreater[index] = v[i];
selement.pop();
sindex.pop();
}
selement.push(v[i]);
sindex.push(i);
}
else{
selement.push(v[i]);
sindex.push(i);
}
}
}
while(!selement.empty()){
selement.pop();
}
while(!sindex.empty()){
sindex.pop();
}
for(int i=n-1;i>=0;i--){
if(selement.empty()){
selement.push(v[i]);
sindex.push(i);
}
else{
if(v[i] > selement.top()){
while(!selement.empty() && v[i] >= selement.top()){
ll index = sindex.top();
previousgreater[index] = v[i];
selement.pop();
sindex.pop();
}
selement.push(v[i]);
sindex.push(i);
}
else{
selement.push(v[i]);
sindex.push(i);
}
}
}
set<ll> ansset;
for(int i=0;i<n;i++){
if(nextgreater[i] != -1){
ansset.insert(nextgreater[i] - v[i]);
}
if(previousgreater[i] != -1){
ansset.insert(previousgreater[i] - v[i]);
}
}
cout<<ansset.size();
}
int main()
{
fast;
ll t;
// t = 1;
cin>>t;
while(t--)
{
solve();
cout<<endl;
}
}
Can someone tell what is wrong in my solution plz
Consider
tc
2
1 1
1 Like
#include<bits/stdc++.h>
#define line cout<<endl;
#define space cout<<" ";
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define PI 3.141592653589793238
typedef long long int ll;
using namespace std;
const ll N = 1e9+7;
ll nextgreater[100000+5];
ll previousgreater[100000+5];
void solve()
{
memset(nextgreater,-1,sizeof(nextgreater));
memset(previousgreater,-1,sizeof(previousgreater));
ll n;
cin>>n;
vector<ll> v(n);
for(int i=0;i<n;i++){
cin>>v[i];
}
// cout<<"hello world"; line;
stack<ll> selement;
stack<ll> sindex;
for(int i=0;i<n;i++){
if((int)selement.size() == 0){
selement.push(v[i]);
sindex.push(i);
}
else{
if(v[i] >= selement.top()){
while((int)selement.size() > 0 && v[i] >= selement.top()){
nextgreater[sindex.top()] = v[i];
selement.pop();
sindex.pop();
}
}
selement.push(v[i]);
sindex.push(i);
}
}
// cout<<"next greater is done: "; line;
while((int)selement.size() > 0){
selement.pop();
}
while((int)selement.size() > 0){
sindex.pop();
}
// cout<<"made empty: "; line;
for(int i=n-1;i>=0;i--){
if((int)selement.size() == 0){
selement.push(v[i]);
sindex.push(i);
}
else{
if(v[i] >= selement.top()){
while((int)selement.size() > 0 && v[i] >= selement.top()){
previousgreater[sindex.top()] = v[i];
selement.pop();
sindex.pop();
}
}
selement.push(v[i]);
sindex.push(i);
}
}
// cout<<"previous greater id one: ";line;
unordered_set<ll> ansset;
for(int i=0;i<n;i++){
if(nextgreater[i] != -1){
ansset.insert(nextgreater[i] - v[i]);
}
if(previousgreater[i] != -1){
ansset.insert(previousgreater[i] - v[i]);
}
}
cout<<ansset.size();
}
int main()
{
fast;
ll t;
// t = 1;
cin>>t;
while(t--)
{
solve();
cout<<endl;
}
}
I have modified the soluntion just a bit
2
1 1
this test I’m getting ans 1
this is also getting TLE on some case in subtask 2, but the solution is almost identical to author’s solution
That’s what the correct solution supposed to get.
1 Like
Yes for the test case you suggested I’m getting correct ans for above solution , but after submitting it m getting TLE on 1 testcase of subtask 2
memset(nextgreater,-1,sizeof(nextgreater));
memset(previousgreater,-1,sizeof(previousgreater));
consider T= 10^5
1 Like