PROBLEM LINK:
Author: Leo Lee
Tester: Daanish Mahajan
Editorialist: Leo Lee
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
You are given an array A of size N and an array B of size M. While B is not empty, you perform the following operations:
- Remove and store the leftmost element off of B (let’s call this element X).
- Place X at the start of A.
- Keep swapping X and the element to the right of it repeatedly until X is at the rightmost position of A or X is greater or equal to the element to the right of it.
Before performing the operations, you can rearrange both A and B in any order once. Determine the minimum possible amount of operations.
Subtask 1 [15 points]: A[i] = B[i] = 1 for all i
Subtask 2 [30 points]: N, M \le 10^3
Subtask 3 [55 points]: N, M \le 2*10^5
QUICK EXPLANATION:
The answer is equal to the number of elements in B that are smaller than the smallest element in A, times N.
EXPLANATION:
Subtask 1:
If all A[i], B[i] are equal, there won’t be any swaps since X will always be equal to the element to the right of it. Note that rearranging A or B won’t do anything. Since there are no swaps, the answer is always 0.
Subtask 2:
We can observe that the most optimal arrangement for A and B is to sort both in ascending order.
For A, the most important thing is for the smallest element in A to be at the front. If it isn’t, there is a possibility of an element to exist that are between the smallest element and the first element, causing extra swaps. Also note that, if a swap is required with the smallest element in A, that means a swap is required for every element in A as it will all be greater than or equal to the smallest element.
For B, notice that if it is in ascending order, any element X that is put into A won’t end up at a position farther than the one previously, which is optimal. On the contrary, assume there are two adjacent elements which are not in sorted order. This means that there is a possibility of the two elements meeting after being merged into A. If they meet, it will cause an extra swap, which is undesired.
Therefore, we can sort both in ascending order and simulate the process. This has a time complexity of O(NM), which is enough to pass this subtask.
Subtask 3:
From the previous subtask, we can observe that, when elements are sorted in optimal order, the only elements in B being swapped are the ones that are smaller than the smallest element of A. Also, note that since no element in B will be swapped with any other element in B and will be swapped with every element in A, it will cost N swaps each.
This means that we can calculate the total number of swaps easily by getting the product of N and the number of elements in B that are smaller than the smallest element in A. This gives us a time complexity of O(N + M).
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m, a, mini = INT_MAX, ans;
signed main() {
cin >> n >> m;
for (int i=0; i<n; i++) {
cin >> a;
mini = min(mini, a);
}
for (int i=0; i<m; i++) {
cin >> a;
if (a < mini) ans++;
}
cout << ans*n << endl;
}
Tester's Solution
import java.util.*;
import java.io.*;
public class Main{
static PrintWriter out;
static InputReader in;
public static void main(String args[]){
out = new PrintWriter(System.out);
in = new InputReader();
new Main();
out.flush(); out.close();
}
Main(){
solve();
}
void solve(){
int n = in.nextInt(), m = in.nextInt();
int a[] = new int[n], b[] = new int[m];
for(int i = 0; i < n; i++)a[i] = in.nextInt();
for(int i = 0; i < m; i++)b[i] = in.nextInt();
Arrays.sort(a); //Arrays.sort(b);
long ans = 0;
for(int i = 0; i < m; i++){
if(b[i] < a[0])
ans += n;
}
out.println(ans);
}
public static class InputReader{
BufferedReader br;
StringTokenizer st;
InputReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public int nextInt(){
return Integer.parseInt(next());
}
public long nextLong(){
return Long.parseLong(next());
}
public double nextDouble(){
return Double.parseDouble(next());
}
public String next(){
while(st == null || !st.hasMoreTokens()){
try{
st = new StringTokenizer(br.readLine());
}catch(IOException e){}
}
return st.nextToken();
}
}
}
