# SORTRRAY-Editorial

Setter: Satyam
Tester: Nishank Suresh, Abhinav sharma
Editorialist: Devendra Singh

2509

None

# PROBLEM:

Given an array A of length N.

You are allowed to perform the following operation on the array A atmost 20 times:

• Select a non-empty subset S of the array [1,2,3,\ldots,N] and an integer X (0 \leq X \leq 10^6);
• Change A_i to A_i+X for all i \in S.

You have to sort the array A in strictly increasing order by performing atmost 20 operations.

It is guaranteed that we can always sort the array A under given constraints.

# EXPLANATION:

Let array B=[10^5,10^5+1,...,10^5+N-1]. Array B is strictly increasing . No matter what the initial array A is we can always change it to B in \leq 20 steps. Construct a new array Diff of length N such that Diff_i=B[i]-A[i]. It is obvious we need to add Diff_i to each A_i to make it equal to B_i. The maximum value of Diff_i does not exceed 2*10^5. This means only bits till 0 to 17 can be set to 1 in the binary representation of any number Diff_i. In each operation from i= 0 to 17 choose all indices j in Diff such that i^{th} bit is set to 1 in Diff_j and add 2^i to all such indices in A. By the end of 18^{th} operation array A is transformed to array B.

# TIME COMPLEXITY:

O(N) for each test case.

# SOLUTION:

Setter's solution
#include <bits/stdc++.h>
using namespace std;

/*
------------------------Input Checker----------------------------------
*/

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

if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}

return x;
} else {
assert(false);
}
}
}
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){
}
}
}

/*
------------------------Main code starts here----------------------------------
*/

const int MAX_T = 1e5;
const int MAX_N = 1e5;
const int MAX_SUM_LEN = 1e5;

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define mp make_pair
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
#define pb push_back

int sum_n = 0, sum_m = 0;
int max_n = 0, max_m = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll mod = 1000000007;

using ii = pair<ll,ll>;

void solve(){

sum_n+=n;
int a[n];

rep(i,n){
}

int b[n];

rep(i,n){
b[i] = 1e5+i-a[i];
}

vector<vector<int> > v(20);

int q = 0;

rep(i,20){
rep(j,n){
if((b[j]>>i)&1) v[i].pb(j);
}
if(!v[i].empty()) q++;
}

cout<<q<<'\n';
rep(i,20){
if(!v[i].empty()){
cout<<v[i].size()<<" "<<(1<<i)<<'\n';
for(auto h:v[i]) cout<<h+1<<" ";
cout<<'\n';
}
}

}

signed main()
{

#ifndef ONLINE_JUDGE
freopen("input.txt", "r" , stdin);
freopen("output.txt", "w" , stdout);
#endif
fast;

int t = 1;

for(int i=1;i<=t;i++)
{
solve();
}

assert(getchar() == -1);
assert(sum_n<=1e5);

cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
cerr<<"Sum of lengths : " << sum_n <<" "<<sum_m<<'\n';
// cerr<<"Maximum length : " << max_n <<'\n';
// // cerr<<"Total operations : " << total_ops << '\n';
// cerr<<"Answered yes : " << yess << '\n';
// cerr<<"Answered no : " << nos << '\n';

cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
void sol(void)
{
int n;
cin >> n;
vll v(n);
for (int i = 0; i < n; i++)
{
cin >> v[i];
v[i] = 1e5 + i - v[i];
}
vector<vector<int>> ans;
for (int i = 0; i < 20; i++)
{
vector<int> ids;
for (int j = 0; j < n; j++)
{
if ((1 << i) & (v[j]))
ids.pb(j + 1);
}
if (ids.size() == 0)
continue;
vector<int> tempans;
tempans.pb(ids.size());
tempans.pb(1 << i);
ans.pb(tempans);
ans.pb(ids);
}
cout << ans.size()/2 << '\n';
for (auto x : ans)
{
for (auto y : x)
cout << y << ' ';
cout << '\n';
}
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int test = 1;
cin >> test;
while (test--)
sol();
}

8 Likes

We can convert it to array B in \leq 20 steps. All the elements in the difference array will be positive and we are 2^i to the numbers where i^{th} bit is active in the difference array B as mentioned in the editorial.

3 Likes

Suppose array is
25
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
How can we make it strictly increasing in less than 20 moves ?

1 Like
11
13 1
1 3 5 7 9 11 13 15 17 19 21 23 25
13 2
1 4 5 8 9 12 13 16 17 20 21 24 25
13 4
1 6 7 8 9 14 15 16 17 22 23 24 25
9 8
1 10 11 12 13 14 15 16 17
9 16
1 18 19 20 21 22 23 24 25
24 32
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
25 128
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
25 512
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
25 1024
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
25 32768
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
25 65536
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25


This answer takes 11(\leq 20) moves.

1 Like

ohh, I apparently misread the problem statement
a subsequence of “hello” can be “ho”. Thanks for the example.

this is a very good problem!

I was getting WA for overflow in this test
1
100000
100000 0 100000 0 100000 0 100000 0 100000 0 …

Good problem, Thanks!