CT27 - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: ansh_321
Tester: mridulahi
Editorialist: iceknight1093

DIFFICULTY:

2700

PREREQUISITES:

Binary search

PROBLEM:

You’re given two arrays A and B. You also have an array C, initially empty.
You can perform the following moves:

  • Append A to C; or
  • Increase an element of C by 1.

Find the minimum number of moves to make B a subsequence of C.

EXPLANATION:

The only elements we can possibly obtain in C are those that are \geq some A_i, since we can only append a copy of A and then increment some of its elements.
In particular, if some element of B is strictly less than all the elements of A, it can never appear in C: and hence B can’t appear as a subsequence of C.
Putting it another way, if \min(B) \lt \min(A), the answer is -1. In all other cases, an answer exists - we just need to find it.

Let’s attempt to construct array B in C.
The process to do that is as follows:

  • Let \text{ptr} be a pointer denoting our current position in array C.
  • For each i = 1, 2, 3, \ldots, we’ll try to make B_i appear at a position \gt \text{ptr}, but using as few moves as possible.
  • That leaves us with two cases:
    • One way is to try to find a j \gt ptr such that C_j \leq B_i, then move to this position and increment C_j till it reaches B_i.
    • Alternately, we can append a new copy of A to C, and then go back to the first step (which gives us more elements to work with, for a cost of one move).

Now, we must decide which of the two choices we want to take (that is, to append a new copy of A or not).
It turns that that decision follows from the result of a greedy decision.

Claim: When choosing an element to turn into B_i, it’s always optimal to choose A_j such that A_j is as close as possible to B_i.
That is, A_j will be the largest element of A that’s \leq B_i.

Proof

Let A_j be as described. Consider some A_k \lt A_j; and say we use A_k instead.
In the first case, our cost is at most 1 + (B_i - A_j), since we might need to append an extra copy of A.
In the second case, our cost is (B_i - A_k), which is \geq B_i - A_j + 1, since A_j - 1 \geq A_k.

So, if we can use A_j without having to append a new copy of A, it’s strictly better to do so.

Next, consider the case when we have to append a new copy of A. Note that this means A_j is only ‘reachable’ in the new copy of A.
Here,

  • If A_k is also only reachable in the new copy of A, clearly it’s strictly better to choose A_j.
  • If A_k is reachable earlier; moving to A_j in the new copy doesn’t lose us anything (as noted earlier, the costs at least match).
    Further, we’ll be at a ‘better’ (i.e more leftward in A) index in the new copy, so the cost of future operations isn’t increased either.

So, it’s never worst to choose A_j rather than A_k; hence we might as well always do so.

With this in mind, let’s go back to our earlier cases.

  • For a fixed B_i, let x be the element in A that’s closest to it (but doesn’t exceed it).
    x can be found by binary searching on A.
  • Now, if there exists an occurrence of x after \text{ptr}, simply move to the closest such occurrence.
    Finding the closest occurrence of x isn’t too hard: keep a list of all occurrences of x in A, and binary search on it.
    Note that while \text{ptr} is technically a pointer to C, it’s also implicitly a pointer to some index of A (after all, C is formed by joining several copies of A); so it’s enough to maintain \text{ptr} modulo N.
  • If no such occurrence exists, append a copy of A and then move to the first occurrence of x.

TIME COMPLEXITY

\mathcal{O}(N\log N + M\log N) per testcase.

CODE:

Tester's code (C++) 
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")


#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;


struct custom_hash {
        static uint64_t splitmix64(uint64_t x) {
                // http://xorshift.di.unimi.it/splitmix64.c
                x += 0x9e3779b97f4a7c15;
                x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
                x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
                return x ^ (x >> 31);
        }

        size_t operator()(uint64_t x) const {
                static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
                return splitmix64(x + FIXED_RANDOM);
        }
};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T>
T rand(T a, T b){
    return uniform_int_distribution<T>(a, b)(rng);
}

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<int> vi;


#define rep(i, a, b) for(int i = a; i < b; i++)
#define all(x) begin(x), end(x)
#define sz(x) static_cast<int>((x).size())
#define int long long

const ll mod = 998244353;
const ll INF = 1e18;

/* ----------------------------------------------------- GO DOWN ---------------------------------------------------------------------- */




signed main() {

        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);

        int t;
        cin >> t;

        while (t--) {

                int n, m;
                cin >> n >> m;
                int a[n];
                int b[m];
                vector<int> v;
                map<int, vector<int>> pos;
                for (int i = 0; i < n; i++) {
                        cin >> a[i];
                        pos[a[i]].push_back(i);
                        v.push_back(a[i]);
                }
                for (int i = 0; i < m; i++) cin >> b[i];

                sort(all(v));
                v.erase(unique(all(v)), v.end());

                int cur = 0;
                int ans = 1;
                bool ps = 1;
                for (int i = 0; i < m; i++) {
                        int j = upper_bound(all(v), b[i]) - v.begin();
                        if (j == 0) {
                                ps = 0;
                                break;
                        }
                        j--;
                        int val = v[j];
                        ans += b[i] - val;
                        int k = lower_bound(all(pos[val]), cur) - pos[val].begin();
                        if (k == sz(pos[val])) {
                                ans++;
                                cur = pos[val][0] + 1;
                        }
                        else cur = pos[val][k] + 1;
                }
                if (!ps) cout << -1 << "\n";
                else cout << ans << "\n";


        }

        
       
}
Editorialist's code (Python) 
import bisect
def solve(a, b):
    n = len(a)
    if min(b) < min(a):
        print(-1)
        return
    
    pos = {}
    for i in range(n):
        if a[i] not in pos: pos[a[i]] = []
        pos[a[i]].append(i)
    ptr, ans = n, 0
    a.sort()
    for x in b:
        val = a[bisect.bisect_right(a, x) - 1]
        ans += x - val
        if pos[val][-1] <= ptr:
            ans += 1
            ptr = pos[val][0]
        else:
            ptr = pos[val][bisect.bisect_right(pos[val], ptr)]
    print(ans)

for _ in range(int(input())):
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    solve(a, b)