PLAYFIT - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

This was one of the simple problems of this month. A lot of you were able to solve it easily. The constraints of the problem were such that only O(n) solution could pass. The problem could be stated simply as: Find 2 numbers ai and aj such that aj-ai is maximum. (1 <= i < j <= N) A couple of approaches to this problem: Approach 1: Store the numbers in an array a. Take 2 additional arrays b & c. b[i]=maximum over all ax (for all x such that i<=x<=n) c[i]=minimum over all ax (for all x such that 1<=x<=i) Both these arrays can be computed in O(n) time and space. Clearly, answer will be max(b[i]-c[i]) for all i. This can be found in O(n) too. Approach 2: Take a variable ‘minm’ which denotes the minimum value encountered so far. Let ‘ans’ denote the maximum difference achieved so far. Read the numbers one by one. Let current value be cur. ans=max(ans,cur-minm) minm=min(minm,cur); Finally, the answer would be in ‘ans’.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

2 Likes

how can the given two arrays can be computed in O(n) time complexity will u please explain it a bit more i am not in hurry to look into the solution…

Approach 1: Store the numbers in an array a. Take 2 additional arrays b & c. b[i]=maximum over all ax (for all x such that i<=x<=n) c[i]=minimum over all ax (for all x such that 1<=x<=i)
What does this paragraph mean?

Why am I getting TLE for this solution ?

And also why is minm initialized with 100000007 ?

P.S. - I know why we get TLE in a code , I just want to know if it due to my approach or if any changes can be done to this code.

Thanks IN Advance

Why kadane algorithm is giving WA in this problem? Thanks in advance.

https://discuss.codechef.com/questions/112763/how-do-i-find-the-first-element-in-an-unsorted-array-which-is-greater-than-or-equal-to-a-given-value-x-in-olog-n

https://www.codechef.com/viewsolution/16695987
Can anyone point out the problem in this solution.
Thanks in advance.

can someone please tell me whats the problem in this solution
https://www.codechef.com/viewsolution/21224696

Ive used same approach as Approach 1. But It is giving me TLE.

^use faster i/o methods.

easily…try it yourself.

@shubham99 Reduce the complexity of your solution. It is n^2.
As it is pointed above “The constraints of the problem were such that only O(n) solution could pass.”

No need of taking any extra array.
we can do it by taking two extra variable and swap the values when necessary.
check code for clarity.

#include<bits/stdc++.h>
using namespace std;
int main()
{
int T,N;
cin>>T;
while(T–)
{
cin>>N;
int a,b,sum=0;
cin>>a;
for(int i=1;i<N;i++)
{
cin>>b;
if(b<a)
a=b;
else if(b>a)
{
sum=max(sum,b-a);
}

    }
    if(sum)
    cout<<sum<<endl;
    else
    cout<<"UNFIT"<<endl;
}

}

https://www.codechef.com/viewsolution/33868321
what is the problem with this solution can anyone point out?
Thanks:)

can some tell me whats wrong in this code :smile:
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
int a[n+1],mx=INT_MIN;
int ans=0,cnt=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<n-1;i++)
{
if(a[i+1]>a[i])
{
ans=a[i+1]-a[i];
// cout<<ans<<" ";
mx=max(mx,ans);
cnt++;
}
}
if(cnt>0)
{
cout<<mx<<endl;
}
else if(cnt==0)
{
cout<<“UNFIT”<<endl;
}
}
}

For a nested loop, the time complexity is n^2 as there are n^2 iterations.
For, say 3 independent loops, the number of iterations are 3n. We ignore constants when calculating time complexity. Hence independent loops will have linear or O(n) time complexity.