PROBLEM LINK:
Practice
Contest: Division 2
Contest: Division 3
Author: Pranav Rajagopalan
Tester: Rahul Dugar
Editorialist: Aman Dwivedi
DIFFICULTY:
Easy
PREREQUISITES:
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.
- Now, we assign this average as our new x
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.
- Now, we assign this average as our new 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}.
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:
such that:
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,
- 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,
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.
Adding A_x on every element, we get since all elements on the left array are almost equal to A_x. We get,
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.
Multiplying by -1 on every element, we get:
Adding A_y on every element, we get since all elements on the right array are almost equal to A_y. We get,
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) {
return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
return readString(l,r,' ');
}
int sum_n=0;
int a[100005];
void solve() {
int n=readIntLn(2,100000);
sum_n+=n;
assert(sum_n<=1000'000);
fr(i,1,n) {
if(i!=n)
a[i]=readIntSp(1,1'000'000'000);
else
a[i]=readIntLn(1,1'000'000'000);
}
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=readIntLn(1,50000);
// 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;
}
but still nice catch 
