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
Yes ,but it is given that sum of N will not exceed 10^6 over all test cases
The sum of N over all test cases does not exceed 10^6 is not equivalent to the sum of 100000+5 over all test cases does not exceed 10^6
In short, size of both the arrays is set to 100000+5 globally thus complexity of your code becomes (100000+5 ) \cdot T where T<=10^5.
1 Like
Oh shit , I get it now. I totally didn’t see that and was trying to find any logical from last 2 hrs.
thanks a lot for help XD
1 Like
import itertools
def difmax(l):
diff=abs(l[0]-l[1])
return diff
n=int(input())
for i in range(n):
w=[]
m=int(input())
h=list(map(int,input().split()))
p=list(set(h))
c=itertools.combinations(p,2)
for k in c:
g=list(k)
w.append(difmax(g))
print(len(set(w)))
please help me find the mistake
Please explain to me why my code is not even passing subtask1
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef ll type;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef pair<char, int> pci;
typedef pair<int, int> pii;
#define mod 1000000007;
#define frz(i, k, n) for (type i = k; i > n; i--)
#define fr(i, k, n) for (type i = k; i < n; i++)
#define _sort(v) sort(v.begin(), v.end())
#define rsort(v) sort(v.rbegin(), v.rend())
#define l_b(v, c) lower_bound(v.begin(), v.end(), c)
#define u_b(v, c) upper_bound(v.begin(), v.end(), c)
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define dbg(x) cout << #x << " = " << x << "\n"
const ll inf = 0x3f3f3f3f3f3f3f3fll;
//Print any set
template <class class_name>
void print_set(set<class_name> vec)
{
cout << endl;
for (auto item : vec)
{
cout << item << " ";
}
cout << endl;
}
void solve()
{
ll n;
cin >> n;
vl arr(n);
set<ll> cost;
fr(i, 0, n) cin >> arr[i];
fr(i, 0, n-1)
{
ll high1 = max(arr[i], arr[i + 1]);
ll high2 = min(arr[i], arr[i + 1]);
cost.insert(high1-high2);
fr(j, i + 2, n)
{
if (arr[j] > high1)
{
high1 = arr[j];
high2 = high1;
}
else if (arr[j] > high2)
high2 = arr[j];
cost.insert(high1 - high2);
}
}
// print_set(cost);
cout << cost.size() << endl;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll t;
cin >> t;
for (int it = 1; it <= t; it++)
{
solve();
}
return 0;
}