PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Jeevan Jyot Singh
Tester: Tejas Pandey
Editorialist: Nishank Suresh
DIFFICULTY:
1594
PREREQUISITES:
Observation
PROBLEM:
You are given an array A. In one move, you can add 1 to any prefix of A. Find the minimum number of moves needed to make A a palindrome, or report that it is impossible to do so.
EXPLANATION:
Consider a second array B, where B_i denotes the number of times 1 was added to A_i during our operations. That is, the i-th element of the final array is A_i + B_i.
It’s obvious that B is a decreasing array (B_i \geq B_{i-1} for every i \gt 1), and the number of operations performed is exactly B_1. Our aim is to minimize B_1.
The final array should be a palindrome. So, if we consider some index i (1 \leq i \leq N/2), we want
Now, note that performing a move on a prefix larger than N/2 is pointless and can always be replaced by a shorter move that achieves the same result (do you see how?).
So, we can assume B_i = 0 for i \gt N/2. In particular, our equation above for a fixed index i changes to
Notice that this fixes the value of B_i, so we just need to check whether the B_i we obtain this way is a valid array or not.
Hence, the final solution is as follows:
- For each 1 \leq i \leq N/2, compute B_i = A_{N+1-i} - A_i.
- If B is not a decreasing array, or any element of B is \lt 0, then it is impossible to make A a palindrome and the answer is -1.
- Otherwise, the answer is simply B_1.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Setter's code (C++)
#ifdef WTSH
#include <wtsh.h>
#else
#include <bits/stdc++.h>
using namespace std;
#define dbg(...)
#endif
#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;
// -------------------- Input Checker Start --------------------
long long readInt(long long l, long long r, char endd)
{
long long x = 0;
int cnt = 0, 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: " << l << ", R: " << r << ", Value Found: " << x << '\n';
assert(false);
}
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 readStringSp(int l, int r) { return readString(l, r, ' '); }
string readStringLn(int l, int r) { return readString(l, r, '\n'); }
void readEOF() { assert(getchar() == EOF); }
vector<int> readVectorInt(int n, long long l, long long r)
{
vector<int> a(n);
for(int i = 0; i < n - 1; i++)
a[i] = readIntSp(l, r);
a[n - 1] = readIntLn(l, r);
return a;
}
// -------------------- Input Checker End --------------------
int sumN = 0;
void solve()
{
int n = readIntLn(1, 3e5);
sumN += n;
vector<int> a = readVectorInt(n, 1, 1e9);
vector<int> d;
for(int i = 0; i <= n / 2 - 1; i++)
d.push_back(a[n - 1 - i] - a[i]);
if(*min_element(d.begin(), d.end()) >= 0 and is_sorted(d.rbegin(), d.rend()))
cout << d[0] << endl;
else
cout << -1 << endl;
}
int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T = readIntLn(1, 1e5);
for(int tc = 1; tc <= T; tc++)
{
// cout << "Case #" << tc << ": ";
solve();
}
assert(sumN <= 3e5);
readEOF();
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
int a[n];
for(int i = 0; i < n; i++) cin >> a[i];
int b[n];
memset(b, 0, sizeof(b));
for(int i = 0; i < n/2; i++) b[i] = a[n - 1 - i] - a[i];
int bad = 0;
if(b[0] < 0) bad = 1;
for(int i = 1; i < n; i++)
if(b[i] > b[i - 1] || b[i] < 0) bad = 1;
if(bad) cout << "-1\n";
else cout << a[n - 1] - a[0] << "\n";
}
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in reversed(range(n//2)):
a[i] += ans
if a[i] > a[n-1-i]:
ans = -1
break
ans += a[n-1-i] - a[i]
print(ans)