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;
}
When you found in your code arr[j]>high1, then you are making both high1 and high2 equal to arr[j]
1 Like
Thank you for helping me.
Such silly mistakes waste a lot of time.
I am getting this verdict, I have spent over 5 hours trying to figure out what’s wrong with my code. I have also compared my code with editorialist’s code and his output on different cases and I cant find anything wrong. Please please help me find out what I am doing wrong.
My code: click here
Please help me out.