# RECVSEQ - EDITORIAL

Practice

Contest: Division 1

Contest: Division 2

Setter: Pritom Kundu

Tester: Teja Vardhan Reddy

Editorialist: Teja Vardhan Reddy

Simple

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 = a;
int d = a - a;
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

// 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,b;
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-a;
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. 3 Likes

#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 = a;
int d = a - a;
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);
}
``````

}

The code will never reach cnt==2 if cnt has already reached 2 with d = a-a
Hence you can comment the line // if (cnt == 2) break;

Please Can somebody help me, most of time, i could not submit my solution, because of SIGCONT error, i tried searching for the reason and followed their instruction. But i still didn’t make it to work. Can you please help me, what is causing this error in the following code:
Code link: Online Compiler and IDE - GeeksforGeeks

Can someone help me

``````indent preformatted text by 4 spaces
``````

#include<bits/stdc++.h>
using namespace std;
#define LL long long
typedef vector< LL > vi;

int main()
{
LL t;
cin>>t;
while(t–)
{
LL n;
cin>>n;
vi vect;
vect.resize(n);
for(int i=0;i<n;i++)
{
cin>>vect[i];
}
mii check;
LL max_d=0,max_ele=0;
for(int i=1;i<n;i++)
{
//cout<<max_d<<endl;
LL k=vect[i]-vect[i-1];
check[k]++;

``````	}

for(int i=0;i<n;i++)
{
LL k=vect[i]-vect[i-1];
if(max_ele<check[k]){
max_ele=check[k];
max_d=k;
}
}
//cout<<max_d<<endl;
if(vect-vect!=max_d && vect-vect==max_d)
{
vect=(vect-max_d);
}
for(int i=1;i<n;i++)
{
if(vect[i]-vect[i-1]==max_d)
continue;

else
{
vect[i]=vect[i-1]+max_d;
break;
}

}
for(auto x:vect)
cout<<x<<" ";
cout<<endl;

}
``````

}

mii check ;
for map<LL,LL> check;