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