PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pvtr
Preparation: iceknight1093
Tester: wasd2401
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
For two arrays A and B and an integer M, define f(A, B, M) as the minimum cost required to make A equal B using the following moves:
- Choose an index i and set B_i := (B_i + 1)\bmod M with cost 2.
- Choose indices j \lt i and set B_i := B_j with cost 1.
Given A and M, find the minimum possible value of f(A, C, M) across all arrays C such that A_i \neq C_i for all i.
EXPLANATION:
All array values below are implicitly taken modulo M.
The key to solving this task is to attempt to compute f(A, C, M) for a fixed C, and then decide how to choose values to “optimize” that process (i.e have minimum cost).
So, let’s fix an array C.
Suppose there’s some sequence of operations that converts it to A.
There are then two possibilities:
- No move of type 2 is ever used (so all moves are increment moves); or
- At least one move of type 2 is used.
Let’s look at them separately.
Case 1
This is the simple case: if no moves of type 1 are used, we definitely need a cost of at least 2 on each index since A_i \neq C_i.
It’s fairly easy to achieve a cost of exactly 2 on each index: just set C_i = A_i - 1.
So, this case gives us an upper bound of 2N on the answer.
Case 2
Now, suppose at least one move of type 2 is used.
Let k denote the leftmost index such that a type 2 move was used on it at some point of time.
Then,
- By definition of k, everything to its left uses only type 1 moves (and so must have a cost of at least 2).
- We can always ensure that everything to the right of k requires only a single type 2 move, which is clearly optimal.
How?
For each index j (k \leq j \lt N), set C_j = A_{j+1} (it doesn’t matter what C_N is).
Then, we can set C_N to C_{N-1}, C_{N-1} to C_{N-2}, and so on.
The only issue here is that if A_j = A_{j+1}, we’ll have C_j = A_j which isn’t allowed.
However, this isn’t an issue:
- If k = j, we’re using a transformation move on index k anyway, by assumption.
Simply use this transformation move on index k+1 as well; and set C_k to be any value. - If j \gt k, then by construction there exists an index i \lt j such that C_i = A_{j}.
Once again, we just use this i to set C_{j+1} as well (so C_j can be anything).
That fixes everything at indices \geq k, now we only need to think about indices \lt k.
As noted earlier, all of them will use only type 2 moves, so ideally C_i should be relatively close to A_i.
In particular, there will exist some index i_0 \lt k such that we set C_k := C_{i_0} at some point of time.
For every index other than i_0, it’s optimal to choose C_i = A_i - 1, with cost 2.
We’re left with two decisions now: what should i_0 be, and what C_{i_0} should be.
Let’s fix some index i_0, and try to figure out what the optimal value of C_{i_0} will be.
Since we can only perform increment moves on this index, it will take every value from C_{i_0} to A_{i_0}.
There are two possibilities: either this range includes the value A_k, or it doesn’t.
If the range includes A_k, it’s clearly optimal to choose C_{i_0} = A_k itself: that way, no ‘useless’ increments at index i_0 are needed.
The only exception is if A_{i_0} = A_k, in which case we must choose A_k - 1 instead.
In this case, to minimize the overall number of increments, it’s of course best to choose an index i_0 such that A_{i_0} is as close to A_{k} as possible (while being after it).
If the range doesn’t include A_k, it’s clearly optimal to choose C_{i_0} = A_{i_0} - 1, and then use the transformation move to set C_k := A_{i_0} (after incrementing index i_0 once).
After this, we’ll need to perform several increment operations at index k - to minimize these, it’s best if A_{i_0} is as close to A_k as possible, though less than it.
Notice that we only need to find the closest A_{i_0} that’s \geq or \leq A_k.
This can be done quickly by storing the values in a set and binary searching on it, for instance.
A single index k can thus be processed in \mathcal{O}(\log N) time, so simply try every index as a candidate for k and take the best among them.
The final answer is the minimum between both cases.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Tester's code (C++)
/*
* * * *** * *****
* * * * * * * *
* * * *** ***** *
* * * * * * * * *
* * * * * * **
*
* *
*****
* *
***** * *
_* *_
| * * * * | ***
|_* _ *_| * *
* * *
***** * **
* * ***
{===* *===}
* IS * ***
* IT * * *
* RATED?* *
* * * **
* * ***
* *
***** * *
* *
* *
* *
***
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define osl tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define ll long long
#define ld long double
#define forl(i, a, b) for(ll i = a; i < b; i++)
#define rofl(i, a, b) for(ll i = a; i > b; i--)
#define fors(i, a, b, c) for(ll i = a; i < b; i += c)
#define fora(x, v) for(auto x : v)
#define vl vector<ll>
#define vb vector<bool>
#define pub push_back
#define pob pop_back
#define fbo find_by_order
#define ook order_of_key
#define yesno(x) cout << ((x) ? "YES" : "NO")
#define all(v) v.begin(), v.end()
const ll N = 2e5 + 4;
const ll mod = 1e9 + 7;
// const ll mod = 998244353;
ll modinverse(ll a) {
ll m = mod, y = 0, x = 1;
while (a > 1) {
ll q = a / m;
ll t = m;
m = a % m;
a = t;
t = y;
y = x - q * y;
x = t;
}
if (x < 0) x += mod;
return x;
}
ll gcd(ll a, ll b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
return (a / gcd(a, b)) * b;
}
bool poweroftwo(ll n) {
return !(n & (n - 1));
}
ll power(ll a, ll b, ll md = mod) {
ll product = 1;
a %= md;
while (b) {
if (b & 1) product = (product * a) % md;
a = (a * a) % md;
b /= 2;
}
return product % md;
}
void panipuri() {
ll n, m = 0, k = -1, c = 0, sum = 0, q = 0, ans = 0, p = 1;
string s;
bool ch = true;
cin >> n>>m;
vl a(n);
set<ll> t,t1;
ans=2*n;
forl(i, 0, n) {
cin >> a[i];
}
forl(i,1,n){
t1.insert(a[i-1]);
t1.insert((a[i-1]-1+m)%m);
t.insert(a[i-1]);
if(t1.count(a[i])){
ans=min(ans,n+i);
}
else{
auto it=t.lower_bound(a[i]);
if(it==t.end()) it=t.begin();
ll x=*it;
p=(x-a[i]+m)%m;
ans=min(ans,n+i-2+p*2);
it=t.lower_bound(a[i]);
if(it==t.begin()) it=t.end();
it--;
x=*it;
p=(a[i]-x+m)%m;
ans=min(ans,n+i+p*2);
}
}
cout<<ans;
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int laddu = 1;
cin >> laddu;
forl(i, 1, laddu + 1) {
// cout << "Case #" << i << ": ";
panipuri();
cout << '\n';
}
}
Editorialist's code (C++)
// #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;
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n, m; cin >> n >> m;
vector<int> a(n);
for (int &x : a) cin >> x;
auto dist = [&] (int x, int y) {
// x -> y
if (x <= y) return y-x;
return m-x + y;
};
int ans = 2*n;
set<int> have = {a[0]};
for (int i = 1; i < n; ++i) {
int cur = n-1 - i;
cur += 2*(i-1);
int add = INT_MAX;
{
auto it = have.lower_bound(a[i]);
if (it == end(have)) it = begin(have);
if (*it != a[i]) add = 1 + 2*dist(a[i], *it);
}
{
auto it = have.upper_bound(a[i]);
if (it == begin(have)) it = end(have);
it = prev(it);
add = min(add, 3 + 2*dist(*it, a[i]));
}
ans = min(ans, cur + add);
have.insert(a[i]);
}
cout << ans << '\n';
}
}