PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Jeevan Jyot Singh
Testers: Hriday, Utkarsh Gupta
Editorialist: Nishank Suresh
DIFFICULTY:
1540
PREREQUISITES:
Two pointers or deques
PROBLEM:
Given an array A, in one move you can pick any A_i and split it into X and Y such that X+Y=A_i.
Find the minimum number of moves to make A a palindrome.
EXPLANATION:
Let’s look at the two end elements, i.e, A_1 and A_N.
If A_1 = A_N, we can ignore them and continue on with the rest of the array: we now deal with N-2 elements.
Otherwise, suppose A_1 \lt A_N. Note that we have to perform at least one move on A_N to make the endpoints equal.
So, let’s perform this move: split A_N into (A_N - A_1) and A_1.
Now the endpoints of the array are equal, so we can continue on with the rest of the array. However, notice that we added the new element A_N - A_1 to the array, which we also need to take care of. So, we deal with N-1 elements now.
The A_1 \gt A_N case can be handled similarly: we just need to insert A_1 - A_N at the start of the array instead.
In either case, the array length decreases by at least 1, so the process will be done at most N times before we end. If we can simulate this algorithm fast enough, we are done.
Implementing this by deleting from arrays/vectors/etc will lead to a solution in \mathcal{O}(N^2) because it’s simply not possible to easily insert/delete elements at the beginning.
However, there are a couple of ways to overcome this:
- Perhaps the simplest way is to just use a data structure that does allow for quick insertion/deletion at both ends: a deque.
- With a deque, implementation becomes extremely easy: while there is more than one element, compare the front and back elements, then insert the appropriate new element to either the front or back.
- It’s also possible to implement this using two pointers (which really just simulates a deque on an array anyway):
- Start with L = 1, R = N.
- At each step, compare A_L and A_R.
- Deleting elements can be simulated by increasing L/decreasing R
- Adding a new element at the front/back can be done by decreasing L/increasing R and then setting A_L or A_R appropriately.
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, 1e5);
sumN += n;
vector<int> a = readVectorInt(n, 1, 1e5);
int L = 0, R = n - 1, ans = 0;
while(L < R)
{
if(a[L] == a[R])
L++, R--;
else if(a[L] < a[R])
a[R] -= a[L], L++, ans++;
else
a[L] -= a[R], R--, ans++;
}
cout << ans << endl;
}
int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T = readIntLn(1, 1e5);
for(int tc = 1; tc <= T; tc++)
{
solve();
}
readEOF();
assert(sumN <= 2e5);
return 0;
}
Editorialist's code (C++, deque)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t; cin >> t;
while (t--) {
int n; cin >> n;
deque<int> dq;
for (int i = 0; i < n; ++i) {
int x; cin >> x;
dq.push_back(x);
}
int ans = 0;
while (dq.size() > 1) {
int x = dq.front(), y = dq.back();
dq.pop_front(); dq.pop_back();
if (x == y) continue;
++ans;
if (x < y) dq.push_back(y-x);
else dq.push_front(x-y);
}
cout << ans << '\n';
}
return 0;
}
Editorialist's code (Python, 2-pointers)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
L, R = 0, n-1
ans = 0
while L < R:
if a[L] == a[R]:
L += 1
R -= 1
elif a[L] < a[R]:
a[R] -= a[L]
L += 1
ans += 1
else:
a[L] -= a[R]
R -= 1
ans += 1
print(ans)