CHEFSORT - Editorial

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:

A_1 < A_2 > A_3 < A_4 > A_5,\dots,A_{N-1} = A_{N}

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,

A_1 < A_2 \le (A_3 + K) < (A_4 + K) > (A_5+ K), \dots (A_{N-1} + K) = (A_{N} + K)

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,

2^x > \displaystyle\sum_{i=0}^{x-1} 2^i

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,

0 \oplus 1 = 1 \\ 1 \oplus 1 = 0

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:

A_1 < A_2 > A_3 < A_4 > A_5,\dots,A_{N-1} > A_{N}

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

A_1 > A_2 < A_3 > A_4 < A_5,\dots,A_{N-1} < A_{N}

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:

(N-1) - ( \lfloor N/2 \rfloor + X )
\lfloor N/2 \rfloor - X

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;
}

14 Likes

Explained very well!

Just wanted to know, is there no code in testers solution dropdown? (as a heading is there, but it opens up with nothing, just as a blank toggler). Also, if anyone can refer to their quality implementation for this problem in Python 3, it’ll help me further. :slight_smile:

3 Likes

Fixed

3 Likes

Instead of finding “a greater number having all set bits”, you can simply bitwise or all the numbers, that would have all the needed bits set to revert the inversions. Makes it easier to understand and implement. CodeChef: Practical coding for everyone

3 Likes

Thanks @cherry0697 for your timely action!

Awesome observation and editorial !!

3 Likes

Nice question…and thanks for this crystal clear explanation…

2 Likes

Thanks for so good explanation

1 Like

Really cool problem and solution. Loved it!

2 Likes

Glad !! You liked it.

Let cnt denote the count of elements such that a[i] > a[i+1] , for 0 <= i < n -1
In the case when cnt > [n/2]
We can print, the number of operations = (n-1 - cnt) + 1 = n-cnt

Because we would have (n-1 - cnt) elements such that a[i] < a[i+1]
and this inequality would be reversed to a[i] > a[i+1] after performing XOR .

And 1 operation would be required for XOR.

But I’m getting WA on printing n-cnt as required number of operations in this case.

Here is my solution:
https://www.codechef.com/viewsolution/44063371

While the same solution gives AC on just recalculating the number of elements such that a[i] > a[i+1] after performing the XOR.

You can check this solution here:
https://www.codechef.com/viewsolution/44062572

Please Help!
@cherry0697 @harshit_0 @akash333 @dgupta0812 @pandakkkk @gopi_018 @better_sleep

1 Like

Actually (n-1-cnt) are the number of pairs of a[i ]>=a[i+1]… not only a[i]>a[i+1]. So we have to add the difference in next term. But ,acc. to constraints k>0 ,so we have to neglect the count of those equality condition… Hope this will resolve your doubt.

1 Like

I have used the same logic in the editorial and the my code is also similar, but still I am getting a WA.
Here is my code solution.
Where am I wrong. Are there any corner cases?

The sample input and output for this problem also do not match. The last two inputs test cases are same, but there corresponding outputs are different.

Thank you so much for replying.
I get it now.
This time I also considered count of elements such that a[i] == a[i+1] , and got an AC.
CodeChef: Practical coding for everyone

Yes I get it now. Thanks :+1:

I missed that point. Thanks :+1:

Very nice approach. The Editorial is also well written.

2 Likes

nicely explained!!

1 Like