PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: negativecode
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
None
PROBLEM:
You’re given an array P. You can do the following:
- Choose indices i, j and set P_i := P_j.
After this, all elements at even indices will increase by 1 every second.
Find a sequence of at most 3N + 5 operations that will result in all the elements of A becoming equal, or claim that no such sequence exists.
EXPLANATION:
Since N \geq 3, it is in fact always possible to make all the elements of P equal.
The idea here is that even-indexed elements keep increasing, so if we’re able to make all the odd-indexed elements equal, all the even-indexed ones equal, and the even elements are \leq the odd ones (with the difference being not too large), we can “wait” a while to let the even elements increase and equal the odd ones.
Here’s one solution that uses about \frac{3N}{2} moves, and doesn’t care about the initial values of P at all.
First, perform the operation (2, 1). After the increase, we’ll have P_2 = P_1 + 1.
Now, “wait” for \frac{N}{2} + c seconds (where c is some small constant like 2 or so) by repeatedly performing the operation (1, 1), which will cause A_2 to increase to P_1 + 1 + \frac{N}{2} + c.
Next, perform the operation (3, 2) to store this ‘large’ value of P_2 somewhere where it won’t change. This value is what all elements will equal in the end.
After this, set all odd-index elements except P_1 to be this target value, by performing (5, 3), (7, 3), (9, 3), \ldots
Next, perform (2, 1) again. This resets P_2 to P_1 + 1.
Now, repeatedly propagate this value among the even indices, by doing (4, 2), (6, 2), (8, 2), \ldots
This uses \frac{N}{2} - 1 moves to make all the even-index elements equal. Note that as we make them equal, they’re still all increasing, so by the end of this process all the even-index elements will be around P_1 + 1 + \frac{N}{2} or so.
After this, perform operation (1, 3) to set P_1 to be equal to the target value.
At this point, we’ve reached the situation we want: all odd-index elements are equal, all even-index elements are equal, and the even-index elements are smaller (but not by much: the difference is around c which we chose to be small).
So, simply wait for a few more moves by performing (1, 1) till everything becomes equal, and we’re done!
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include<bits/stdc++.h>
using namespace std;
#define INF 1e17
#define FOR(a, b, c) for (int a = b; a < c; a++)
#define int long long
#define pb push_back
#define endl '\n'
typedef vector <int> vint;
//----------------------DEBUGGER----------------------------------------------------------
#define dbg(x) cout << #x <<" "; _print(x); cout << endl;
void _print(int t) {cout << t;}
void _print(string t) {cout << t;}
void _print(char t) {cout << t;}
void _print(long double t) {cout << t;}
void _print(double t) {cout << t;}
void _print(unsigned int t) {cout << t;}
template <class T> void _print(vector<vector<T>> v) {for(int j =0;j<v.size();j++){cout <<endl<<"[ "; for (T i : v[j]){_print(i); cout << " ";} cout << "]";};}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cout << "{"; _print(p.first); cout << ","; _print(p.second); cout << "}";}
template <class T> void _print(vector <T> v) {cout << "[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
template <class T> void _print(set <T> v) {cout << "[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
template <class T> void _print(multiset <T> v) {cout << "[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
template <class T, class V> void _print(map <T, V> v) {cout << "[ "; for (auto i : v) {_print(i); cout << " ";} cout << "]";}
template <class T> void _print(vector<vector<vector<T>>> v){for(int k =0;k<v.size();k++){_print(v[k]);}}
//----------------------------------------------------------------------------------------
void solve(){
int n; cin >> n;
vint v(n);
FOR(i,0,n){
cin >> v[i];
}
vector <pair<int,int>> seq;
seq.pb({2, 1});
FOR(i,0,n/2-1){
seq.pb({1,1}); // wait for n/2-1 time
}
seq.pb({3, 2});
if(n%2) seq.pb({1,1});
int prev = 1;
for(int i = 4; i <= n ; i += 2){
seq.pb({i, prev});
prev = i;
}
seq.pb({1, 2});
seq.pb({2, 3});
for(int i = 3 ; i <= n ; i += 2){
seq.pb({i, 1});
}
cout << seq.size() << endl;
for(auto [i, j] : seq){
cout << i << " " << j << endl;
}
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout << fixed << setprecision(10);
int t;
cin >> t;
FOR(i,1,t+1){
solve();
}
}
Tester's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
void solve(int test_case){
ll n; cin >> n;
vector<ll> a(n+5);
rep1(i,n) cin >> a[i];
vector<pll> ans;
// a[1] to all evens
for(int i = 2; i <= n; i += 2){
if(i == 2){
ans.pb({2,1});
}
else{
ans.pb({i,i-2});
}
}
// 1 idle op
ans.pb({1,1});
// a[2] to all odds except a[1]
for(int i = 3; i <= n; i += 2){
if(i == 3){
ans.pb({3,2});
}
else{
ans.pb({i,i-2});
}
}
// a[1] to all evens
for(int i = 2; i <= n; i += 2){
if(i == 2){
ans.pb({2,1});
}
else{
ans.pb({i,i-2});
}
}
// a[1] = a[3]
ans.pb({1,3});
assert(sz(ans) <= 3*n/2+5);
cout << sz(ans) << endl;
for(auto [i,j] : ans){
cout << i << " " << j << endl;
}
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
vector<array<int, 2>> ops;
auto op = [&] (int i, int j) {
ops.push_back({i, j});
};
op(1, 2);
for (int i = 0; i < n/2 + 1; ++i) op(1, 1);
op(2, 3);
int target = a[0] + 1 + n/2 + 1;
for (int i = 5; i <= n; i += 2) op(i-2, i);
op(1, 2); // a[1] + 1
a[1] = a[0] + 1;
for (int i = 4; i <= n; i += 2) op(i-2, i), ++a[1];
op(3, 1); ++a[1];
while (a[1] != target) {
op(1, 1);
++a[1];
}
cout << size(ops) << '\n';
for (auto [x, y] : ops) cout << y << ' ' << x << '\n';
}
}