# AVGSORT - Editorial

Author: Pranav Rajagopalan
Tester: Rahul Dugar
Editorialist: Aman Dwivedi

Easy

Observation

# PROBLEM:

You are given a sequence A of N numbers. You can perform the following operation any number of times:

• Select any two adjacent elements A_i and A_{i+1} of the sequence and replace one of them with \large\frac{A_i+A_{i+1}}{2} . Do not round the resulting value.

You can select the same position in different operations.

Your task is to find whether the given sequence can be made strictly increasing in zero or more operations.

# QUICK EXPLANATION:

• If the given sequence is in decreasing order, then it is never possible to make a sequence in strictly increasing order.

• In all other cases, it is always possible.

# EXPLANATION:

We were given a sequence A of N numbers. Our task is to find whether the given sequence can be made strictly increasing in zero or more operations.

Claim: If x>y, then it will remain x>y no matter how many times we perform the operation.

Proof

Let us suppose we have two numbers, say x and y such that x>y. Our operation is nothing but just replacing any one of these numbers with the average of these two numbers. The left bound for the average is y whereas the right bound for the average is x.

What happens when we replace x with average ?

• As average will always be greater than y. It means that if we replace x with average, then also the condition won’t change.
average>y
• Now, we assign this average as our new x
x>y

What happens when we replace y with average ?

• As average will always be less than x. It means that if we replace y with average, then also the condition won’t change.
x>average
• Now, we assign this average as our new y
x>y

It means that if x>y, then it will remain x>y.

However, by repeatedly doing the operation many times, the values can be made very close to each other. Now if we observe that if there exists any pair A_i<A_{i+1}, then it is always possible to make the given sequence strictly increasing. Let’s see how:

Suppose we have a given sequence A of N numbers such that there exists a pair A_i<A_{i+1}.

A_1,A_2,....,A_{x-1},A_x<A_y,A_{y+1},....A_{N-1},A_N

Now by repeatedly performing the operations, all the elements on the left side of the A_x can be made almost equal to A_x. Similarly by repeatedly performing the operations on the right side of the A_y can be made almost equal to A_y.

How ?

Suppose that we have two numbers say x and y such that x>y. Our average is nothing but just the midpoint of number x and y. If every time we replace x with the midpoint then the midpoint will keep shifting towards y. After performing operations an infinite number of times the value of x will be very close to y.

Now, our sequence will be as:

A_1,A_2,....,A_{x-1},A_x<A_y,A_{y+1},....A_{N-1},A_N \\ ---------\hspace{0.5cm} --------- \\ \downarrow \hspace{3cm} \downarrow \\ \approx A_x \hspace{2.35cm} \approx A_y

such that:

max(A_1,A_2,....,,A_x,A_y)= A_y \\ min( A_x,A_y,A_{y+1},....A_{N-1},A_N)=A_x

Since A_x and A_y are adjacent elements such that A_x<A_y. Let the difference between these elements be defined as diff i.e

• a) We will apply the operation on indices x and y, replacing A_x with the average of A_x and A_y i.e. setting A_x=(A_x+A_y)/2. More formally, its like adding diff/2 to A_x, hence our new A_x is A_x+diff/2. So we get,
A_1,A_2,....,A_{x-1}<A_x<A_y,A_{y+1},....A_{N-1},A_N
• b) We will repeat the same procedure again but this time we will be replacing A_y with the average of A_x and A_y i.e. setting A_y=(A_x+A_y)/2. More formally, its like subtracting diff/4 to A_y, hence our new A_y is A_y-diff/4. This time we get,
A_1<A_2<....<A_{x-1}<A_x<A_y<A_{y+1},....A_{N-1},A_N

Left part of the Array:

We will apply the operation on indices x-1 and x, replacing A_{x-1} with the average of A_x and A_{x-1} i.e. setting A_{x-1}=(A_{x-1}+A_x)/2. Its like adding diff/4 to A_{x-1}, hence our new A_{x-1} is A_{x-1}+diff/4. We will repeat the procedure till we reach the leftmost end of an array. This will make our left part of the array sorted in strictly increasing order.

• Suppose,the left part of our array is A_1, A_2,\dots,.A_x. Initially, we made all the elements of this left array almost equal to A_x.After that when we are performing operations then we are just adding \Large\frac{diff}{2^i} to the elements, where diff=A_y-A_x and i=x-index+1.
\frac{diff}{2^x} < \frac{diff}{2^{x-1}} < \dots <\frac{diff}{2^2} < \frac{diff}{2^1}

Adding A_x on every element, we get since all elements on the left array are almost equal to A_x. We get,

A_x+\frac{diff}{2^x} < A_x+\frac{diff}{2^{x-1}} < \dots <A_x+\frac{diff}{2^2} < A_x+\frac{diff}{2^1} \\ ----\hspace{0.7cm} ----\hspace{1.8cm}----\hspace{0.7cm}---- \\ \downarrow \hspace{2cm} \downarrow \hspace{3cm} \downarrow \hspace{2cm} \downarrow \\ A_1 \hspace{1.6cm} A_2 \hspace{2.7cm} A_{x-1} \hspace{1.6cm} A_x \\

Hence, the left part of the array is sorted in strictly increasing order.

Right part of the Array:

We will apply the operation on indices y and y+1, replacing A_{y+1} with the average of A_y and A_{y+1} i.e. setting A_{y+1}=(A_{y+1}+A_y)/2. Its like subtracting diff/8 to A_{y+1}, hence our new A_{y+1} is A_{y+1}-diff/8. We will repeat the procedure till we reach the rightmost end of an array. This will make our right part of the array sorted in strictly increasing order.

• Suppose,the right part of our array is A_y, A_{y+1},\dots,.A_N. Initially, we made all the elements of this right array almost equal to A_y.After that when we are performing operations then we are just subtracting \Large\frac{diff}{2^i} to the elements, where diff=A_y-A_x and i=index-y+2.
\frac{diff}{2^2} > \frac{diff}{2^3} > \dots > \frac{diff}{2^{N-y+1}} > \frac{diff}{2^{N-y+2}}

Multiplying by -1 on every element, we get:

- \frac{diff}{2^2} < - \frac{diff}{2^3} < \dots < - \frac{diff}{2^{N-y+1}} < - \frac{diff}{2^{N-y+2}}

Adding A_y on every element, we get since all elements on the right array are almost equal to A_y. We get,

A_y-\frac{diff}{2^2} < A_y-\frac{diff}{2^3} < \dots <A_y-\frac{diff}{2^{N-y+1}} < A_y-\frac{diff}{2^{N-y+2}} \\ ----\hspace{0.7cm} ----\hspace{1.8cm}----\hspace{0.7cm}---- \\ \downarrow \hspace{2cm} \downarrow \hspace{3cm} \downarrow \hspace{2cm} \downarrow \\ A_y \hspace{1.6cm} A_{y+1} \hspace{2.7cm} A_{N-1} \hspace{1.6cm} A_N \\

Hence, the right part of the array is sorted in strictly increasing order.

Finally, merge the left and right array, since A_x<A_y, our new array will be sorted in increasing order.

Hence, if there exists any pair A_i<A_{i+1}, then it is always possible to make the given sequence strictly increasing.

So when in the sequence there exists no pair (A_i,A_{i+1}) such that A_i<A_{i+1}. When the array is in decreasing order. Hence when the array is in decreasing order, it will be never possible to make the sequence in strictly increasing order.

# TIME COMPLEXITY:

O(N) per test case

# SOLUTIONS:

Setter
#include <bits/stdc++.h>
#define int long long
using pii=std::pair<int,int>;
using namespace std;

const int maxn = 3e5 + 5;

int t, n, a[maxn];
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> t;
for(int cases = 0; cases < t; cases++)
{
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i];
int good = 0;
for(int i = 1; i < n; i++)
if(a[i] > a[i - 1])
good = 1;
if(good)
cout << "Yes\n";
else
cout << "No\n";
}
return 0;
}

Tester
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
uniform_int_distribution<int> uid(0,lim-1);
return uid(rang);
}
int powm(int a, int b) {
int res=1;
while(b) {
if(b&1)
res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}

long long readInt(long long l, long long r, char endd) {
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true) {
char g=getchar();
if(g=='-') {
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g&&g<='9') {
x*=10;
x+=g-'0';
if(cnt==0) {
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd) {
if(is_neg) {
x=-x;
}
assert(l<=x&&x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret="";
int cnt=0;
while(true) {
char g=getchar();
assert(g!=-1);
if(g==endd) {
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt&&cnt<=r);
return ret;
}
long long readIntSp(long long l, long long r) {
}
long long readIntLn(long long l, long long r) {
}
string readStringLn(int l, int r) {
}
string readStringSp(int l, int r) {
}
int sum_n=0;
int a;
void solve() {
sum_n+=n;
assert(sum_n<=1000'000);
fr(i,1,n) {
if(i!=n)
else
}
int mi=1000'000'000;
fr(i,1,n) {
mi=min(mi,a[i]);
if(a[i]>mi) {
cout<<"yEs"<<endl;
return;
}
}
cout<<"No"<<endl;
}

signed main() {
ios_base::sync_with_stdio(0),cin.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
cout<<fixed<<setprecision(10);
//	int t;
//	cin>>t;
fr(i,1,t)
solve();
#ifdef rd
cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}


Editorialist
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int mxN=1e5+5;
int n;
int arr[mxN];

int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);

int t;
cin>>t;

while(t--)
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>arr[i];
}

int flag=0;

for(int i=2;i<=n;i++)
{
if(arr[i]>arr[i-1])
{
flag=1;
}
}

if(flag)
{
cout<<"YES"<<"\n";
}
else
{
cout<<"NO"<<"\n";
}
}

return 0;
}



# VIDEO EDITORIAL:

8 Likes

don’t mind the question
but how much time it took for you to prove this solution when you tried doing it first.

2 Likes

Bit tricky to say for sure, I originally came up with an incorrect idea (using prefix min and suffix max). After that I was just trying some small cases to verify, and realized that idea was wrong. Once I got that counter case it was fairly intuitive to reach the a_i < a_(i + 1) condition and realize that we can make a range really close to a value then increase / decrease it.

So I’d say around 30-40 mins to come up with the actual soln (not too sure since I was toying around with the general idea, not 100% fixed on just this variant), and maybe another 15 mins or so to roughly formalize a proof.

Still working out the finer details and formalizing a proper construction took me another 15-20 mins to think and write out when I was proposing the problem.

6 Likes

Still it is exploding speed.

Actually I was able to do this question instantly with a very nice proof. Ig it is definitely shorter then the editorial.

First some observations :

1. Observe that if you have 2 numbers A and B then you can make A to B or B to A.
2. So you can basically make a chain of same numbers.
3. So if you are able to make a chain like this : [m,m,m,m,…m,x] and x>m where m is the minimum element then you will definitely be able to make a strictly increasing sequence out of this. Just keep updating m=(right_element+m)/2 starting from the last m.

Here is the outline :

1. If array is already SI then print YES.
else
2)If the last element is greater then the minimum element then print YES
else
3)Now the last element is the minimum element, so our job now is to find an element that is greater then the last element and also has a some smaller element to the left of it.
It can easily be done by maintaining prefix_minimas.
4)Also check for case of all equal elements.
6 Likes

I solved it using prefix mins can you verify my idea of proof above thanks!!

Simple even if you find one such pair such that Ai < Ai+1 then we will always be able to convert the whole sequence into the strictly increasing one
It took very much time because i was thinking the problem can’t be that simple so did’t submitted but still nice catch CodeChef: Practical coding for everyone solution

3 Likes

Yes, it uses prefix mins, but mostly just replicates the same condition as the intended solution (a_i < a_(i + 1)).

My original idea with prefix min and suffix maxs was actually really different and would fail on cases like these:

3
10 4 8

Fun fact, that’s actually the counter case I found that led me to realizing the actual solution during the early stages of thinking about this idea.

Also the editorial is a bit on the long side only because it does an excellent job breaking down each and every observation and its proof, even if it might be trivial for a lot of participants. Additionally it also shows an explicit construction to make it clearer, kudos to the editorialist for doing a brilliant job with it.

6 Likes

This how I proved (sadly after the contest had ended) that the presence a single A_i < A_{i+1} is sufficient and necessary for the sequence to be sortable. It looks long but there are just a few main ideas (those that I have bolded) that solve the problems. Rest is just to maintain rigor. Once you get the bolded ideas, getting the rest part is much easier.

Firstly like the official solution says, by the averaging we can bring any two adjacent numbers arbitrarily close to each other (but the ordering between them remains same). Like if two adjacent elements are (1,2) and we apply averaging again and again we get (1,2) \longrightarrow (1, 1.5) \longrightarrow (1, 1.25) and so on. The second term keeps coming closer to 1 but is always larger than 1. We cannot make it equal to 1 in a finite number of steps.

The main proposition is that if you can find a contiguous part of the sequence that is strictly increasing, then you can always apply averaging such that the elements just adjacent to this sub-sequence also become a part of it, increasing its length.

To make myself clear, if the sequence was 14, 25, 11, 15, 17, 19, 21, 10, 9 (where the part in bold is the sub-sequence I’ve been talking about). The 10 present on right side and 25 on the left side of this are breaking the chain of increasing numbers. I claim that we can do averaging such that these 10 and 25 also become a part of the chain. I’ll call 25 and 10 the border numbers, and 11 and 21 as the guard numbers.
We do two steps.
Step 1:
Bring the border numbers very close to the guardian numbers by doing average on the (border, guardian) pair and changing the value of the border number. At the end of this step our sequence would look like 14, 11.001, 11, 15, 17, 19, 21, 20.999, 9

Step 2:
Now change the values of the guardian numbers by averaging the border number and the number adjacent to it in the chain (like 15 is adjacent to 11 and 19 is adjacent to 21).
After this the sequence would look like 14, 11.001, 13, 15, 17, 19, 20, 20.999, 9

Note how the length of the bold sequence has been increased. This is a general algorithm that I can apply to any sequence, not just the one I took in the example

So when we have a single adjacent pair such that A_i < A_{i+1} (i.e. increasing), we can always increase the length of this increasing sub-sequence successively and the full sequence will eventually be fully sorted.

This proves that the condition is sufficient. Now let’s prove it’s necessary.

Suppose there are no two elements such that A_i < A_{i+1} . This means that the sequence is non-increasing. It seems obvious why this should not be sortable, but we can prove it easily by induction (which is probably the uncoolest way, but everything else I think of seems to be hand-waving over some things.)

18 Likes

Bro step 1,did not understand it how did you change 2 to 11.001. Could you explain it once again

I dont think this question was easy in any way. Even I had found the result at end but the proving the result is quite tedious I would say.

3 Likes

Noice! I also thought of this but I was not sure at that time

1 Like

Yeah sorry about that, it was a typo. Instead of 2 it should have been 25 (or anything greater than 11). I hope you see now how I made 25 to 11.001

9 9 9 7 9 8.99
9 9 7.01 7 7.01 8.99
9 7.02 7.01 7 7.01 8.99
7.03 7.02 7.01 7 7.01 8.99
8.94 8.95 8.96 8.97 8.98 8.99

2 Likes

I have one doubt that how is it possible to convert
7 2 4 1 6 8 3 9 into strictly increasing sequence as 7 > 2 and it will always remain greater than 2.

How can we make a chain of same numbers in this case 7 2 4 1 6 8 3 9 ?
7 > 2 how can this pair be made strictly increasing ?
Please can you explain this test case step wise using your method.
Thanks

We can still decrease 7.
We have (a,b) = 7,2.
a = (a+b)/2; //a now is 3.5 which was earlier 7
Again, a = (a+b)/2; //now a is 2.75
we will keep doing this infinite times and eventually a which once was 7 will now be shrinked to almost 2 (not exactly 2, but a value just greater than 2).

Still it will remain greater than 2 so how this sequence will become strictly increasing?
In that case, 4 will make 2 to be 3.5 after some operations and you know how to proceed further. 