PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Smit Mandavia
Tester: Rahul Dugar
Editorialist: Aman Dwivedi
DIFFICULTY:
Easy - Medium
PREREQUISITES:
Constructive, XOR-properties
PROBLEM
You are given an array of A of N elements. Your task is to make the array sorted in non-decreasing order by applying operations at most \lfloor N/2 \rfloor times. There are 4 types of operations possible which are defined as follows:
- Choose an integer K such that 0 \lt K \lt 2^{30} .
- Choose an integer P such that 1 \leq P \leq N
- Choose the type of the operation and apply the operation on the array A
Types of operations:
- Type 1: Add K to A_1, A_2, \ldots, A_P
- Type 2: Add K to A_P, A_{P+1}, \ldots, A_N
- Type 3: Xor A_1, A_2, \ldots, A_P with K
- Type 4: Xor A_P, A_{P+1}, \ldots, A_N with K
QUICK EXPLANATION
If the pairs of consecutive elements in the array such that A_{i-1}>A_i are less than or equal to N/2, then starting from the end of the array each time we encounter such a pair, we could add a number X\geq A_{i-1}-A_i to elements from A_i to A_N, so that the problematic pair would become A_{i-1}\leq A_i and the relative ordering of the elements to their right would also not be hindered. If such pairs are greater than N/2 then we can turn them into A_{i-1}\lt A_i by XOR-ing all elements of the array with a greater number having all set bits. In this process all pairs that were A_{i-1}\lt A_i would also become A_{i-1}\gt A_i, thus reducing the problematic pairs to less than N/2.
EXPLANATION
We are given an array A of N elements. Our task is to make the array sorted in non-decreasing order by applying operations at most \lfloor N/2 \rfloor times. We know that if array is sorted in non-decreasing order, then there exists no pair of consecutive indices (i,i+1) such that A[i]>A[i+1].
We can draw an observation here, that after applying an operation of Type 2 on any index P, the relative ordering of A_P, A_{P+1}, \ldots, A_N remains the same as we are adding the same integer on every element.
Claim: It is always possible to have A_{P-1} \le A_P after applying operation of Type 2 on index P.
Proof
The maximum difference between any two elements of an array is 2^{30}-1, as the minimum and maximum number that can exist in the array are 0 and 2^{30}-1 respectively.
Let us suppose we have an array as:
Since A_2 > A_3, we will apply an operation of Type 2 on index 3 choosing such a K which is greater than or equal to the difference between A_3 and A_2.
Hence,
Hence we can apply the operation of Type 2 on every index i such that A[i-1]>A[i]. Once all these operations are done, there exists no consecutive pair of indices (i-1,i) such that A[i-1]>A[i], that means our array is sorted in non-decreasing order now.
The number of operations that will be required will be the number of consecutive pairs in the array (i-1,i) such that A[i-1]>A[i].
What happens when the number of such pairs is greater than \lfloor N/2 \rfloor ?
Claim: It is always possible to reverse the relative order between A_i and A_{i+1} by applying an operation of Type 3.
Proof
Let us suppose that if we have two numbers a and b in binary representation. Can you tell which number is greater without finding their decimal form?
The first bit where they differ is deciding bit. The number whose deciding bit is set is greater than the other number. Since,
Now, if A_{i} > A_{i+1} it means the deciding bit of A_{i} is set whereas the deciding bit of A_{i+1} is unset. To make A_{i} < A_{i+1}, all we have to do is to unset the deciding bit of A_{i} and set the deciding bit A_{i+1}. It is quite easy to do since,
Since if we xor both A_i and A_{i+1} with such a number which is greater than or equal to the maximum of A_i and A_{i+1} and all the bits are set (since we don’t know the deciding bit), then the order will be reversed.
Suppose we have an array A as:
If we apply the Type 3 operation by choosing P=N and choosing such a K which is greater than or equal to the maximum element of an array and all the bits should be set of K as we don’t know the deciding bits. Then the relative order of the whole array will be reversed i.e
Let us now calculate the number of consecutive pair of indices (i-1,i) such that A[i-1]>A[i].
Suppose the number of pairs before applying the operation Type 3 is \lfloor N/2 \rfloor + X. There are a total of (N-1) pairs, hence after applying the operation the number of pairs will be:
The minimum value that X can have in cases that need us to apply operation of Type 3 is 1, also we require one operation of Type 3 to reverse the order. Hence the number of operations that can be performed at most is \lfloor N/2 \rfloor.
Once the order is reversed apply the Type 2 operation as discussed above.
TIME COMPLEXITY:
O(N) per test case
SOLUTIONS:
Setter
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007
int main(){
FIO;
ll t,n,k,i,j;
ll sum_n=0,sum_n_2=0;
cin >> t;
while(t--){
cin >> n ;
sum_n+=n;
sum_n_2+=n*n;
ll a[n];
for(i=0;i<n;i++)
cin >> a[i];
j=0;
k=0;
for(i=1;i<n;i++)
if(a[i-1]<a[i])
k++;
else if(a[i-1]>a[i])
j++;
cout << min(k+1,j) << "\n";
assert(min(k+1,j)<=n/2);
if(k+1<j){
cout << 3 << " " << n << " " << (1<<30)-1 << "\n";
for(i=0;i<n;i++)
a[i]^=(1<<30)-1;
}
for(i=1;i<n;i++)
if(a[i]<a[i-1])
cout << 2 << " " << i+1 << " " << a[i-1]-a[i] << "\n";
}
assert(sum_n_2<=1000'000'0);
return 0;
}
Tester
#pragma GCC optimize("Ofast")
#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;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
//#define double long double
#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 int infi=0x3f3f3f3f;
const ll infl=0x3f3f3f3f3f3f3f3fLL;
//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 sun=0;
int a[1005];
void solve() {
int n=readIntLn(3,1000);
sun+=n*n;
assert(sun<=10'000'000);
fr(i,1,n)
if(i!=n)
a[i]=readIntSp(0,(1<<30)-1);
else
a[i]=readIntLn(0,(1<<30)-1);
int req=0;
rep(i,1,n)
if(a[i]>a[i+1])
req++;
vector<vi> ops;
if(2*req>n) {
ops.pb({3,n,(1<<30)-1});
fr(i,1,n)
a[i]^=(1<<30)-1;
req=0;
rep(i,1,n)
if(a[i]>a[i+1])
req++;
}
for(int i=n-1; i>0; i--)
if(a[i]>a[i+1])
ops.pb({2,i+1,a[i]-a[i+1]});
cout<<sz(ops)<<endl;
for(auto i:ops)
cout<<i[0]<<" "<<i[1]<<" "<<i[2]<<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,100000);
// int t=1;
// cin>>t;
fr(i,1,t)
solve();
assert(getchar()==EOF);
#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
void solve()
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int op=0,eq=0;
for(int i=n-1;i>0;i--)
{
if(a[i]<a[i-1])
op++;
else if(a[i]==a[i-1])
eq++;
}
int ans=op;
if(ans>n/2)
{
ans=n-ans;
ans-=eq;
}
cout<<ans<<"\n";
if(op>n/2)
{
cout<<3<<" "<<n<<" "<<(1ll<<30)-1<<"\n";
for(int i=0;i<n;i++)
a[i]^=(1ll<<30)-1;
}
for(int i=n-1;i>0;i--)
{
if(a[i]<a[i-1])
{
cout<<2<<" "<<i+1<<" "<<(1ll<<30)-1<<"\n";
}
}
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
while(t--)
solve();
return 0;
}