SORTRRAY-Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

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

DIFFICULTY:

2509

PREREQUISITES:

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 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,' ');
}
 
 
/*
------------------------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(){
    
    int n = readIntLn(2, 1e5);
    sum_n+=n;
    int a[n];

    rep(i,n){
        if(i<n-1) a[i] = readIntSp(1,1e5);
        else a[i] = readIntLn(1,1e5);
    }

    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;
    
    t = readIntLn(1,5e4);
    
    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); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
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
A possible answer for your test case
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 :confused:
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!