PROBLEM LINK:
Setter: Pritom Kundu
Tester: Teja Vardhan Reddy
Editorialist: Teja Vardhan Reddy
DIFFICULTY:
Simple
PREREQUISITES:
Math
PROBLEM:
Given a sequence A of size \geq 4, find a sequence B which differs with A in atmost one position and is Arithmetic progression (AP).
EXPLANATION
If two consecutive terms of an arithmetic progression are known, then all the terms of an AP can be found uniquely.
Proof: We can find the common difference of the AP from the consecutive terms and we can find any term of the AP using an element and common difference of the AP.
Case 1: When the element changed in A is not among first two positions.
Since now first two terms of B are fixed and B is an AP, complete sequence B can be fixed uniquely. So now we can check if obtained B and A differ in atmost one position.
Case 2: When one of first two elements are changed, then last two elements must be unchanged. So we know last two terms of B. And we can do a similar procedure as in case1 and check.
Since, B is guaranteed to exist. we must find a valid B in one of the two cases.
The above solution only works for n \geq 4 because only then first two and last elements are disjoint. For example, take n=3 , then above algorithm makes second element always unchanged. But in this question, we are given n \geq 4, hence above algorithm works fine.
TIME COMPLEXITY
In both cases, generating B will take O(n) time. Hence complexity is O(n).
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+7;
int a[N];
int b[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
while (t--) {
int n;
cin>>n;
for (int i=1; i<=n; i++) cin>>a[i];
b[1] = a[1];
int d = a[2] - a[1];
int cnt = 0;
for (int i=2; i<=n; i++) {
b[i] = b[i-1] + d;
if (b[i] != a[i]) cnt++;
if (cnt == 2) break;
}
if (cnt <= 1) {
for (int i=1; i<=n; i++) cout<<b[i]<<" ";
cout<<"\n";
continue;
}
b[n] = a[n];
d = a[n-1] - a[n];
cnt = 0;
for (int i=n-1; i>=1; i--) {
b[i] = b[i+1] + d;
if (b[i] != a[i]) cnt++;
if (cnt == 2) break;
}
if (cnt <= 1) {
for (int i=1; i<=n; i++) cout<<b[i]<<" ";
cout<<"\n";
continue;
}
assert(false);
}
}
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// find_by_order() // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
#define int ll
int a[123456],b[123456];
int check(int n){
int gg=0,i;
rep(i,n){
if(a[i]!=b[i])
gg++;
}
return (gg<=1);
}
main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int i;
rep(i,n){
cin>>a[i];
}
rep(i,n){
b[i]=a[i];
}
int diff=a[1]-a[0];
f(i,1,n){
b[i]=b[i-1]+diff;
}
if(check(n)){
rep(i,n){
cout<<b[i]<<" ";
}
cout<<endl;
continue;
}
rep(i,n){
b[i]=a[i];
}
diff=a[n-1]-a[n-2];
fd(i,n-2,0){
b[i]=b[i+1]-diff;
}
if(check(n)){
rep(i,n){
cout<<b[i]<<" ";
}
cout<<endl;
continue;
}
assert(0);
}
return 0;
}
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 